Copied from my old ScienceBlogs site to test out the mathcache JavaScript tool.
Ah, complex networks: manufacturing centre for the textbook cardboard of tomorrow!
When you work in the corner of science where I do, you hear a lot of “sales talk” — claims that, thanks to the innovative research of so-and-so, the paradigms are shifting under the feet of the orthodox. It’s sort of a genre convention. To stay sane, it helps to have an antidote at hand (“The paradigm works fast, Dr. Jones!”).
For example, everybody loves “scale-free networks”: collections of nodes and links in which the probability that a node has $k$ connections falls off as a power-law function of $k$. In the jargon, the “degree” of a node is the number of links it has, so a “scale-free” network has a power-law degree distribution.
So, you take your favourite system and boil it down to a set of nodes and links. You count up the node degrees and plot the curve on a log-log plot, because taking the logarithm of both sides of
$$\displaystyle P \propto k^{-a},$$
you realize that
$$\displaystyle \log P = -a\log k + b,$$
so a power-law dependence will show up as a straight line. Unfortunately, you might already be fooling yourself, as other functions can look to the eye — and to linear regression — like straight lines on such a plot. You can hide a multitude of sins on a log-log graph!
Problem number two: The degree distribution does not by itself characterize a network. Two networks can be quite different but have identical degree distributions. For example, consider the “clustering coefficient”, defined as the probability that two neighbours of a node will themselves be directly connected. (It measures the “cliquishness” of the network, in a way.) One can build networks with indistinguishable power-law degree distributions but arbitrarily different clustering coefficients. The NetworkX Python module has a built-in function to do just that: powerlaw_cluster_graph().
FURTHER READING
- A. Clauset, “People v. The scale-free networks hypothesis” (blog entry, 20 April 2010), which cites
- A. L. G. de Lomana, “Statistical Analysis of Global Connectivity and Activity Distributions in Cellular Networks” Journal of Computational Biology; and also
- R. Tanaka, “Scale-Rich Metabolic Networks” Phys. Rev. Lett. 94 (2005): 168101; not to mention
- A. Clauset et al., “Power-law distributions in empirical data” SIAM Review 51 (2009): 661–703, for which the code is available ontube.
- J. Dall and M. Christensen, “Random Geometric Graphs” Phys. Rev. E 66 (2002): 016121.
- C. Herrmann et al., “Connectivity Distribution of Spatial Networks” Phys. Rev. E 68 (2003): 026128.