3
$\begingroup$

How to generate a degree sequence of a degree distribution that follows the power-law in which I know $N=10^2$ and $\gamma=2.5$?

The degree distribution of power-law is $p_k \sim k^{-\gamma}$.

I want to generate a power-law network using the configuration model, but to do that I need to know the degree sequence $seq={k_1, k_2, ..., k_N}$.

Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

As you mention, the degree distribution follows a power law if the number of nodes of degree $k$ is roughly $N \times C^{-1} k^{-\gamma}$, where $C = \sum_{k = 1}^\infty k^{-\gamma} = \zeta(\gamma)$ (in your case, $C \approx 1.34$). Plugging in your numbers, we want roughly

  1. 75 vertices of degree 1.
  2. 13 vertices of degree 2.
  3. 5 vertices of degree 3.
  4. 2 vertices of degree 4.
  5. 1 vertices of degree 5.
  6. 1 vertices of degree 6.
  7. 1 vertex of degree 7.

This gives a total of 98 vertices. You can make it exactly 100 vertices in many ways — I'll let you think of one. Don't forget that the sum of degrees should be even.

The (potential) problem is that not every sequence is the degree sequence of a graph. Sequences which are realized by some graphs are known as graphic sequences, and are determined by the Erdős–Gallai criterion. If the resulting sequence doesn't satisfy this criterion, we're in trouble. However, I don't expect it to happen in your case. Indeed, my suggestion above (with 98 vertices) is graphical.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for the reply. I admit I don't understanding a lot. How did you generate the list? And what is $C=\sum_{k = 1}^\infty k^{-\gamma}=\zeta(\gamma)$? Sorry. $\endgroup$
    – sleepwalking
    Commented Apr 2, 2016 at 15:11
  • $\begingroup$ I generated the list by rounding the formula $N \cdot C^{-1} k^{-\gamma}$ for various values of $k$. The value of the constant $C$ is the infinite sum $\sum_{k=1}^ \infty k^{-\gamma}$, which is also the value of the zeta function (which you can look up on the internet) at the point $\gamma$. I computed $C = \zeta(2.5)$ using a computer algebra system (sage in my case). $\endgroup$
    – Yuval Filmus
    Commented Apr 2, 2016 at 15:45
  • $\begingroup$ Ok, doubt: how do I generate 100 vertices instead of 98? $\endgroup$
    – sleepwalking
    Commented Apr 2, 2016 at 17:07
  • $\begingroup$ You'll have to figure that out yourself. $\endgroup$
    – Yuval Filmus
    Commented Apr 2, 2016 at 17:50
  • $\begingroup$ I think a lot about how to generate the exact number of nodes but I couldn't find any solution. If you could help me, do me a big favor. $\endgroup$
    – sleepwalking
    Commented Apr 3, 2016 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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