Lets say I have a random variable with values in the space of square binary matrices from which I can sample (adjacency matrices of) graphs, and lets say that the resulting graphs have a power law degree distribution (in expectation).

Are the sampled graphs 'sparse' (the number the number of edges follows $O(n)$, where $n$ is the number of nodes)?

Similarly, can I say anything about their being 'dense' (the number of edges follows $O(n^2)$ )?

Edit: Following @manuellafond's comment I see the question needs further clarification:

A power law degree distribution means that the probability $P(k)$ of a node having degree $k$ follows $P(k)=Ck^{-\gamma}$ for some $C$ and $\gamma$. If we further stipulate that $\gamma$ is the same for all graph sizes $n$, $C$ must be a function of $n$ as follows:

$C(n) = \frac{1}{\sum^{n-1}_{k=1}k^{-\gamma}}$

To be honest, I'm now not 100% sure that such a setup is at all possible, but I think so. This question is an attempt to formalise the same for social networks, which typically have power law degree distributions.

  • 1
    $\begingroup$ Does power law degree mean that the probability $P(k)$ that a given node is of degree $k$ is $P(k) = k^{-\gamma}$, for some constant $\gamma$ ? $\endgroup$ – Manuel Lafond Jun 11 '14 at 20:02
  • $\begingroup$ You'd need a normalising constant $P(k)=Ck^{-\gamma}$, but yes, that's right. Thanks for clarifying. $\endgroup$ – drevicko Jun 12 '14 at 8:36

Since no one is answerng, here's what I get, assuming $\gamma$ is a constant. As you say then $C = \frac{1}{\sum_{k = 1}^{n - 1} k^{-\gamma}} = \frac{1}{H^{\gamma}_{n - 1}}$, ${H^{\gamma}_{n - 1}}$ being the generalized Harmonic number.

Let $m$ be the number of edges of your graph $G = (V, E)$. We'll treat $m$ as a random variable. Denote the degree of some vertex $v \in V$ by $d(v)$.

We'd like to find out the order of $\mathbb{E}[m]$. Using the handshake lemma,

$$\mathbb{E}[m] = \mathbb{E}[ \frac{1}{2} \sum_{v \in V} d(v)] = \frac{1}{2} \sum_{v \in V} \mathbb{E}[d(v)] = \frac{1}{2} n \mathbb{E}[d(v)]$$ (for some $v \in V$).

So it all comes down to the expected degree. For some $v \in V$, we get $$\mathbb{E}[d(v)] = \sum_{k = 1}^{n - 1} k P(d(v) = k)= \sum_{k = 1}^{n - 1} k C k^{-\gamma} = C \sum_{k = 1}^{n - 1} \frac{1}{k^{\gamma - 1}} = \frac{H_{n-1}^{\gamma - 1}}{H^{\gamma}_{n-1}}$$

Now, ${H^{\gamma}_{n - 1}}$ is $O(n)$ when $\gamma = 0$, $O(\log n)$ when $\gamma = 1$ and $O(1)$ when $\gamma > 1$.

So if $\gamma = 1$, $n \frac{H_{n-1}^{\gamma - 1}}{H^{\gamma}_{n-1}} \in O(n \frac{n}{\log n}) = O(\frac{n^2}{\log n})$.

If $\gamma = 2$, $n \frac{H_{n-1}^{\gamma - 1}}{H^{\gamma}_{n-1}} \in O(n \log n)$.

If $\gamma > 2$, $n \frac{H_{n-1}^{\gamma - 1}}{H^{\gamma}_{n-1}} \in O(n)$.

It remains to find the order for $1 < \gamma < 2$.

  • $\begingroup$ good try, but $C$ or $\gamma$ (or both) must necessarily depend on $n$ in order to make $P(d(v)=k)$ into a probability distribution. If we fix $\gamma$, we end up with $\mathbb{E}[d(v)] = \frac{\sum k^{1-\gamma}}{\sum k^{-\gamma}}$, which I'm not sure what to do with... $\endgroup$ – drevicko Jun 12 '14 at 17:29
  • $\begingroup$ Ah sorry I didn't see your edit. It feels like we can treat $C$ as a constant since it converges as $n$ gets larger. Specifically, $\lim_{n \rightarrow \infty} \sum_{k = 0}^{n - 1} k^{-\gamma} = \zeta(\gamma)$, the Riemann zeta function which is known to converge to some constant $c$ whenever $\gamma > 1$. So $1/\sum_{k = 0}^{n - 1} k^{-\gamma} \rightarrow 1/\zeta(\gamma) $ should converge as well. But this might need details to fill in. $\endgroup$ – Manuel Lafond Jun 12 '14 at 18:30
  • $\begingroup$ Yes, $C(n)$ decreases monotonically, so in the inequality for $\mathbb{E}[d(v)]$, we can replace $C$ by its first term $C(2)=1$. I've edited the answer to accordingly. Thx (: $\endgroup$ – drevicko Jun 12 '14 at 21:36
  • $\begingroup$ Your edit have been rejected it would seem...(not me !) Anyway I still have a little doubt. That $C$ is decreasing does make $O(n log n)$ a correct bound, but it could be less. I mean, let's say for the sake of arguing that $C = 1/\log n$. It's still decreasing, but it cancels out the $\log n$ in $n \log n$, and $C$ can possibly change the order of the number of edges. I'll think about it... $\endgroup$ – Manuel Lafond Jun 12 '14 at 23:47
  • $\begingroup$ For $\gamma>2$, $\mathbb{E}[d(v)]$ converges as $n\rightarrow \infty$, so is in $O(1)$, or have I missed something?? For $\gamma=2$, it's as $H_{n-1}\in O(\log n)$ (I'm guessing we can't do much better there). $\endgroup$ – drevicko Jun 13 '14 at 14:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.