Complexity_ A Guided Tour - Melanie Mitchell [112]
FIGURE 15.3. The degree distribution of the network in figure 15.2. For each degree, a bar is drawn representing the number of nodes with that degree.
High-degree nodes are called hubs; they are major conduits for the flow of activity or information in networks. Figure 15.1 illustrates the hub system that most airlines adopted in the 1980s, after deregulation: each airline designated certain cities as hubs, meaning that most of the airline’s flights go through those cities. If you’ve ever flown from the western United States to the East Coast on Continental Airlines, you probably had to change planes in Houston.
A major discovery to date of network science is that high-clustering, skewed degree distributions, and hub structure seem to be characteristic of the vast majority of all the natural, social, and technological networks that network scientists have studied. The presence of these structures is clearly no accident. If I put together a network by randomly sticking in links between nodes, all nodes would have similar degree, so the degree distribution wouldn’t be skewed the way it is in figure 15.3. Likewise, there would be no hubs and little clustering.
Why do networks in the real world have these characteristics? This is a major question of network science, and has been addressed largely by developing models of networks. Two classes of models that have been studied in depth are known as small-world networks and scale-free networks.
Small-World Networks
Although Milgram’s experiments may not have established that we actually live in a small world, the world of my social network (figure 15.2) is indeed small. That is, it doesn’t take many hops to get from any node to any other node. While they have never met one another (as far as I know), Gar can reach Charlie in only three hops, and John can reach Xiao in only four hops. In fact, in my network people are linked by at most four degrees of separation.
Applied mathematician and sociologist Duncan Watts and applied mathematician Steven Strogatz were the first people to mathematically define the concept of small-world network and to investigate what kinds of network structures have this property. (Their work on abstract networks resulted from an unlikely source: research on how crickets synchronize their chirps.) Watts and Strogatz started by looking at the simplest possible “regular” network: a ring of nodes, such as the network of figure 15.4, which has 60 nodes. Each node is linked to its two nearest neighbors in the ring, reminiscent of an elementary cellular automaton. To determine the degree of “small-worldness” in a network, Watts and Strogatz computed the average path length in the network. The path length between two nodes is simply the number of links on the shortest path between those two nodes. The average path length is simply the average over path lengths between all pairs of nodes in the network. The average path length of the regular network of figure 15.4 turns out to be 15. Thus, as in a children’s game of “telephone,” on average it would take a long time for a node to communicate with another node on the other side of the ring.
FIGURE 15.4. An example of a regular network. This network is a ring of nodes in which each node has a link to its two nearest neighbors.
FIGURE 15.5. A random rewiring of three links turns the regular network of figure 15.4 into a small-world network.
Watts and Strogatz then asked, If we take a regular network like this and rewire it a little bit—that is, change a few of the nearest-neighbor links to long-distance links—how will this affect the average path length? They discovered that the effect is quite dramatic.
As an example, figure 15.5 shows the regular network of figure 15.4 with 5% (here, three) of the links rewired—that is, one end of each of the three links is moved to a randomly chosen node.
This