# All scale free networks are sparse

Scale free networks have a degree distribution which follows a power law, This letter explains why cannot occur (for large networks).

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

The core of their argument comes from looking at the scaling of the largest and the lowest degree nodes. For , the number of nodes with the largest and second largest degree is , while for , 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 , one needs 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 . To grow such networks, however, requires either a cutoff on the allowed node degree, or that 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

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

## Leave a comment

## Comments 0