Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
When we meet someone for the first time, we often search for some sort of common ground upon which we can build a conversation and, possibly, a friendship. Often, this common ground is a place, or a type of music, or a friend. If you've ever played the name game with a new acquaintance and found that you have a friend in common, you've experienced what both romantics and network theorists call a "small world." This concept engenders a feeling that our human world is not as cold and random as it might seem on the surface.
The small-world concept implies that we are all connected through chains of acquaintances. This is often expressed in the famous "six degrees of separation" theory—the idea that we are, at most, six handshakes away from anybody on the planet. This is actually a variant of the classic gangster expression, "I know people who know people." The six degrees of separation idea has been made famous in popular culture through a famous play, a movie, and a game based on connecting movie actors to Kevin Bacon. This popular concept suggests that all of us are more interconnected than it may seem.
Where did this idea come from? How true is it? How can it be expressed mathematically? The first person to study small worlds in any sort of scientific way was the Harvard social psychologist Stanley Milgram. Milgram became fairly well known in the field of social theory in 1963 for a series of experiments in which he measured how likely people were to obey an authority figure, even if it meant inflicting pain on another person. He found that the more degrees of separation there were between the victim and the person inflicting the pain, the more likely it was that the inflictor would follow orders resulting in harm—even death—to the victim. This sets up the natural question of how many degrees of separation exist between people in the real world.
To study this question, Milgram sent letters to random people in Omaha and Wichita and asked them to forward the letters to a certain person in Boston, whom they did not know. However, they were given specific direction in how to go about this. The instructions were to send the letter to a person with whom they were on a first-name basis, a friend who they thought would have a better chance of knowing the intended recipient. Most of the letters never arrived at their destinations, but of the ones that did, it took an average of six forwards to get there. This was the origin of the "six degrees of separation" theory.
The accuracy of the six-degrees story is debatable, but the small world that it implies is very real. A small-world network is one in which most nodes are not connected to each other and yet the average path between most nodes is relatively short. It is a sort of middle ground between highly ordered lattice-type networks and the random networks of Erdös and Rényi. Let's look at this idea of a small world a bit more closely.
Imagine that the six billion people of the world are arranged in a giant circle. Furthermore, let's say that each has 1,000 acquaintances, specifically, the 500 people to the left and the 500 people to the right. This idea presents a highly ordered network known as a ring lattice. We can perform a version of Milgram's experiment in this world by selecting one person in the ring and asking that person to send a letter to the person directly opposite them.
To do this, the sender should give the letter to the 500^{th} person on the right, and this person, in turn, should then give it to the 500th person on the right (we must assume that everyone in the circle is facing inward) and so on. Traveling in this manner, in chunks of 500 people, how many connections will it take for the letter to arrive in the hands of the person opposite the sender?
The intended recipient is approximately 3 billion people away from the original sender. The letter traverses 500 people per connection, so it should take , or 6,000,000 connections for the letter to arrive. This sort of world obviously has significantly more than six degrees of separation.
Of course our world is not as structured as this ring-lattice world. We are certainly free, for the most part, to associate with whomever we like. Let's look at the opposite extreme, the completely random world. Now, in the last section, we already reasoned that the world is not completely randomly connected. However, looking at this case in a little more detail will help us come to a better understanding of the small-world idea.
Once again assuming a world population of six billion and that each person has 1,000 acquaintances, we can find out how many steps it would take for a letter to travel from any sender to any other randomly selected recipient. Of course, we could do this by using the formula from the last section—or we can reason our way through it. Recall that the average distance, d, between nodes on a random graph is given by the formula:
where N is the number of nodes, and k is the number of links per node. Substituting our values for N (6,000,000,000) and k (1,000), we have:
which computes to approximately 2.6 connections per person. This implies that it would take almost three connections on average to pass a letter from one person to any other person if our world were randomly connected.
We have seen that an orderly, ring-lattice world would have six million degrees of separation whereas a totally random world would have about three. The six degrees of separation that Milgram found suggests that the real world is randomly connected, though not entirely.
We have seen that an orderly, ring-lattice world would have six million degrees of separation whereas a totally random world would have a little over three. The six degrees of separation that Milgram found suggests that the real world is randomly connected, though not entirely.
This idea of degrees of separation is simply another way to talk about the average path length, also known as the characteristic path length, of a graph. In general, random networks have short characteristic path lengths; ordered networks have relatively long characteristic path lengths (the greater the order, the longer the average path); and the characteristic path lengths of small-world networks tend to fall somewhere in between. The other chief measure that becomes important in studying and classifying these types of networks and their graphs is the clustering coefficient.
The clustering coefficient is a measure of how many nodes share common connections to other nodes. It is defined as the fraction of a particular node's connections, called the "neighborhood," that share connections with each other. In other words, it quantifies how many of one's friends are also friends with each other. The clustering coefficient can be found for a particular node, or an average value can be calculated to give a clustering coefficient for an entire network.
For example:
The clustering coefficient of vertex v is , because there are three possible connections among v's neighbors, but only two of these are realized. Following the same method, the clustering coefficients of vertices w, x, and y are , , and respectively. The average clustering coefficient for this graph would then be:
A clustering coefficient of 1 indicates that all of a node's neighbors are connected to each other. A clustering coefficient of 0 indicates that none of the nodes in the neighborhood share common connections. The ring-lattice world has a large degree of clustering. If we lived in this world, we would share 499 of the same friends as our neighbor. This puts our individual clustering coefficient at close to . Because all nodes are identical in this world, the average clustering coefficient would be equal to the individual value.
Going back to our random world situation, each of your connections would have a one-in-six-million chance of being connected to another one of your connections. This means that the individual clustering coefficient is virtually zero. Consequently, the clustering coefficient of the network (the average clustering coefficient over all nodes) is also close to zero.
A small-world network has both a short characteristic path length and a clustering coefficient somewhat greater than that of a random network. We can imagine creating a small-world network by starting with our ring-lattice world and randomly disconnecting and reconnecting people.
Each random connection connects local clusters, thereby reducing the characteristic path length. The more random connections we make, the shorter the average path length becomes, because, using our mailed-letter example, a letter could take shortcuts and leap far more than the 500 people it was constrained to in the ring-lattice world.
Using the measures of characteristic path length and clustering coefficient as guideposts enables mathematicians to begin to classify and understand the vast range of network structures that lie between the relatively well-understood random and lattice networks. These "middle" types of networks are more representative of the organizational systems found in nature, which tend to be more randomly organized than lattices and more structured than random networks.
Networks in the natural world tend to have a fair amount of clustering, combined with a bit of randomness in their connections. One hypothesis as to why this is so is that random networks are susceptible to adverse consequences caused by random interruptions, such as when a node or edge is removed. This is what happens when a gene mutates or a single power line fails because it comes into contact with an overgrown tree.
In a random network, such interruptions, also called "deletions," tend to increase the characteristic path length, thereby making the network less effective at transmitting signals. This occurrence is related to the fact that random networks transition very quickly from a group of separate connected components, in which the characteristic path length is infinite because the graph is not connected, to a fully connected graph. Remember, this phenomenon was demonstrated in the button example in the previous section. If path length decreases rapidly as we add edges, it makes sense to assume that it will increase just as rapidly as we reverse direction and begin to remove edges.
In a highly clustered network, most nodes are connected in groups, so removing
one node does little to change the characteristic path length of the entire network. Random deletions are more likely to take out inconsequential nodes than ones that are critically connected.
Now that we have been introduced to the basic concepts of random networks, ring-lattices, and small-world networks, we have some idea of the ways in which mathematicians can analyze and say meaningful things about network structures. The story does not end here, however. There are many possible network structures that, organizationally, fall somewhere between order and randomness. To sort these out further, we will have to increase the resolution of the tools that we use to classify them. In the next section we will see how analyzing the distribution of connections among nodes can lead to greater mathematical understanding of networks.
Next: 11.5 Scale-Free Networks