In discussing very large real networks, such as the internet, analyzing small sets of individual nodes and edges can give interesting insight into some of the structure of the network, but how can we generalize this analysis to formally include all of the nodes and edges in a network where the number of nodes is downright enormous?  The physical network behind the internet itself consists of millions of computers and connections, and the pages and hyperlinks that make up the network of information constitute a network of extremely daunting scale.  The theorems about networks we have discussed so far in the course have primarily focused on the behavior of individual nodes and edges in a network, but for large-scale analysis, we need a different toolbox.

Just such a toolbox exists in physics - the methods of Statistical Mechanics, designed to treat the statistical behavior of enormous numbers of interacting particles.  The number of particles in macroscopic systems is on the order of Avogadro’s number,  about 10^23 particles.  This is just the framework we need to examine the statistical behavior of networks composed of billions of nodes and edges.

Until fairly recently, network theory and physics did not often cross paths.  In the mid-90s, however, interest in network theory among physicists took off.  As it turns out, there are direct analogies between the statistical dynamics of real-world networks, such as the internet, and the statistical behavior of many systems in condensed-matter physics.  A primer on some recent results (including those I mention below) and general ideas of physics on a network ran in Physics Today in November 2008 (see below).

In 2000, Albert-László Barabási and colleagues at the University of Notre Dame discovered that the distribution of the degree of nodes in the internet follows a relation called a power law.  This in itself carries interesting implications, but I’ll skip over those and report one interesting finding from this research, about the resilience of a network when nodes are removed.

Barabási et al found that when nodes are removed at random from a network with a degree distribution that follows a power law, an almost limitless number of nodes can be removed at random without drastically reducing the connectivity of the network as a whole.  The same is not true for a network with a Poisson-distributed degree (the result of a uniformly random distribution of edges) - these networks can be crippled by randomly removing a relatively small number of nodes.  Conveniently for anyone reading this blog, as found by Barabási et al, the internet in fact has a power law distribution in the degree.  Thus, many routers and computers can fail at any given time and the internet as a whole still remains virtually unchanged.

This single result is the tip of an ever-growing iceberg as more physicists begin to study networks and find direct analogy between networks of computer or people and networks of subatomic particles within the same mathematical framework.  As these analogies are further developed, more ideas from statistical mechanics may find their way into the analysis of real-world networks in the future: real networks may very well demonstrate phase transitions, long-range correlations, or other properties characterizing statistical physical systems.  Perhaps it may be wise to make as many friends as possible before your local social network transitions between a fluid and solid state.

The Physics of Networks, Physics Today, November 2008:

http://ptonline.aip.org/journals/doc/PHTOAD-ft/vol_61/iss_11/33_1.shtml