How Not to be a Network-Theory n00b

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().