All scale free networks are sparse

Scale free networks have a degree distribution which follows a power law, P(k) \sim k^{-\gamma} This letter explains why \leq < \gamma \leq 2 cannot occur (for large networks).

Note that \gamma <0 implies a very dense network (and hence not really “scale free” in the traditional sense), and \gamma >2 implies a sparse network.

The core of their argument comes from looking at the scaling of the largest and the lowest degree nodes. For \gamma \leq 2, the number of nodes with the largest and second largest degree is \O(N), while for \gamma >2, the number of such nodes grows sublinearly with N. Also, the number of nodes with degree 1 (or order 1) grows linearly with N. Thus, if \gamma \leq 2, one needs \O(N) degree one nodes to associate with the highest degree node, leaving no way to place edges for the second highest degree node.

Note these results are asymptotic. One could have a finite network with 0 \leq \gamma \leq 2. To grow such networks, however, requires either a cutoff on the allowed node degree, or that \gamma must increase over 2.

http://prl.aps.org/abstract/PRL/v107/i17/e178701

Charo I. Del Genio, Thilo Gross, and Kevin E. Bassler
Phys. Rev. Lett. 107, 178701 (2011)
All Scale-Free Networks Are Sparse

Advertisements

Posted on June 14, 2012, in networks, papers and tagged , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: