I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the neighbourhood of $u$. Clearly, I got that $d(u) = \left | \Gamma(u) \right |$, where $d(u)$ is the degree of $u$.

I now want to split $\Gamma(u)$ into two sets of nodes

$$\Gamma_{\text{low}}(u) = \{ v \in V : v \in \Gamma(u) \text{ and } v < u \}$$ $$\Gamma_{\text{high}}(u) = \{ v \in V : v \in \Gamma(u) \text{ and } v > u \}$$

i.e. $\Gamma_{\text{low}}(u)$ and $\Gamma_{\text{high}}(u)$ contain neighbours of $u$ whose key is less than or greater than $u$'s, respectively.

Assuming that the graph has got $m$ edges, is there a way to obtain an upper bound for $d_{\text{low}}(u) = \left | \Gamma_{\text{low}}(u) \right |$ and $d_{\text{high}}(u) = \left | \Gamma_{\text{high}}(u) \right |$ for varying $m$? I just can obtain the following relationship

$$\sum_{u \in V} d_{\text{low}}(u) + \sum_{u \in V} d_{\text{high}}(u) = 2m,$$

because the graph is undirected. I read somewhere that $d(u) = O\left ( \sqrt{m} \right )$ is a good bound for social networks, but how do I prove it?

  • 2
    $\begingroup$ In order to prove such a bound, you need a generative model for social networks, and then you might be able to prove that the bound holds with high probability. But most likely this bound is just an experimental fact, and so doesn't have any proof. $\endgroup$ – Yuval Filmus Jan 30 '14 at 14:31
  • $\begingroup$ @YuvalFilmus Does that mean I can suppose that the $O \left ( \sqrt{m} \right )$ bound certainly holds? EDIT: Well, not certainly, but with high probability, since I can't prove it, right? $\endgroup$ – Dree Jan 30 '14 at 14:41
  • 2
    $\begingroup$ @Dree You can use the fact that it holds with high probability if and only if you (or, of course, sombody else) can prove that it happens with high probability! Anything you derive as a certain consequence of this fact would also be true with high probability. $\endgroup$ – David Richerby Jan 30 '14 at 15:08
  • $\begingroup$ @DavidRicherby The matter is that I don't even know where to start. Is there some paper related to this topic? $\endgroup$ – Dree Jan 30 '14 at 15:31
  • 2
    $\begingroup$ If you want to prove something rigorously, then the fact that it is a social network is irrelevant. If you want some estimations that will hold in the context of social networks but not in general graphs, then it will be experimental or dependant of some model describing social networks that you need to explicit. $\endgroup$ – Denis Jan 30 '14 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.