Random Graph Theory: Image throwing a box full of buttons on a table and then choosing a pair of buttons at random and connect them with a piece of string. What would the buttons look like over a period of time. "In particular, what features could we prove that all such networks must have?" If you pickup one of the buttons what would be its connected component? "The fraction of the nodes connected in a single component change suddenly when the average number of links per node exceeds one." If we add enough thread so each button has one thread the fraction of the graph that occupied by the largest component suddenly jumps from almost zero to one. A phase transition from unconnected to connected and the point this happens is called the critical point. "Phase transitions of one sort or another occur in many complex systems and have been used to explain phenomena as diver as the onset of magnetization, the explosion of disease epidemics, and the propagation of fads. In the particular case, the phase transition is driven by the addition of a small number of links right near the critical point that have the effect of connecting many very small clusters into a single giant component, which then proceeds to swallow up all the other nodes until everything is connected." "So the presence of a giant component means that whatever happens at one location in the network has the potential to affect any other location." "The line between isolation and connectedness is thus an important threshold for the flow of information, disease, money, innovations, fads, social norms, and pretty much everything else that we care about in the moder society. The global connectivity should arrive not incrementally but in a sudden, dramatic jump tells us something deep and mysterious about the world." Almost everything we know about complex networks tells us that "they are not random." "Nevertheless, if we would like to understand the properties and behavior of real-world networks, the issue of nonrandom structure is one that eventually has to be faced."[Learn More ...]

&Links