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.
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$.