World's most popular travel blog for travel bloggers.

[Solved]: How to generate a degree sequence of a degree distribution

, , No Comments
Problem Detail: 

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

Asked By : marielle

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55342

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback