Universality and Critical Phenomena

So far in class, we have learned about the universal properties of networks found in nature. In doing so, what we have been doing was basically to build simple, convincing models and to find the expected properties from our models. This attempt is good in the sense that we can check that the properties are emerging quite "naturally" from even the simplest of models. We have seen those examples from many of the homework problems. However, it does not really explain the key factor that attributes  to the interesting features of our networks.

As a physics major senior, I wanted to introduce the physicists' approach to explain the related notions called the universality and critical phenomena. Those topics are being studied in the condensed matter theory. From a condensed matter physics perspective, many interesting features of complex system arise from the largeness of the system. (Remember? We were always taking the limit where n goes to infinity.) One important point of the study  (and problems found in web network) is that we are dealing with systems of particles(nodes, pages, etc) that are too large to have all detailed information about individual interactions(links). So, we physicists begin with simple well-known rules, called Hamiltonian, governing the relationships(links) among a few particles(nodes) and then scale it up to a system with a large number of particles. While scaling the system, physicists assume that some of key features of a large system will not be affected by further scaling up to an even larger system. For example, a hand-sized magnet and Earth are both already large  enough from the perspective of atoms. Physicists extract equations from this "scaling invariance" and explain interesting features of the systems. This technique is called Renormalization Group. (Note that in a technical sense, physicists do the inverse of my description: start with a large system, and then scale it down to a smaller one with the same properties.)

This seemingly abstract idea turns out to be very powerful in explaining many of cool things in physical phenomena such as superconductors or phase transitions, and those concepts appear in nature repeatedly.
Some of them are well described in the article linked at the end of this post in easy terms. Here, I address one intuitive example that is the most related to the graph theory we have learned last week.

Consider a large number of small magnets. A pair of magnets are either correlated or not with some probability, p, which depends only on the temperature of the system. Here, "correlated" means that the two magnets are oriented in the same direction, and "not correlated" means their orientations are random. Suppose that theoretical analysis of a simple system containing only two magnets tells us that the probability is decreasing function in temperature. We can consider each magnet as a node in a graph and correlations as edges with probability p. At very large temperature, p goes to zero. According to the theory of random graph, we know we end up with all isolated nodes. This result implies that all magnets are randomly oriented, consequently producing net zero magnetic field. As the temperature goes down, the system reaches a critical point where the graph begins to form many clusters, which means small groups of magnets begin to align parallel each other. Finally, below a certain temperature T_c, where the probability p goes above log(n) /n, we see one giant connected graph: all magnets are oriented in the same direction.  These "phases transitions" are exactly what we find from the process of cooling down a ferromagnetic material: no net magnetization, fragmented local magnetization, and finally the formation of a big magnet. 

The insight we can learn from this example and many more in the reference source is that some of the universal features of large networks are originated not only from their particular graph structures but  also from the largeness of the systems.

Reference Source:
http://www.math.ubc.ca/~slade/pcm0007_final.pdf