# does a power law degree distribution imply graphs are sparse?

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.

• 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$ ? – Manuel Lafond Jun 11 '14 at 20:02
• You'd need a normalising constant $P(k)=Ck^{-\gamma}$, but yes, that's right. Thanks for clarifying. – 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$.

• 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... – drevicko Jun 12 '14 at 17:29
• 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. – Manuel Lafond Jun 12 '14 at 18:30
• 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 (: – drevicko Jun 12 '14 at 21:36
• 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... – Manuel Lafond Jun 12 '14 at 23:47
• 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). – drevicko Jun 13 '14 at 14:57