From Lawn Care to Racial Segregation: Networks
Conspicuous consumption of valuable goods is a means of reputability to the gentleman of leisure.
—Thorstein Veblen, Theory of the Leisure Class
At the heart of any complex system is a set of interacting agents. If we track who interacts with whom, we can uncover a network of connections among the agents. Not too surprisingly, the structure of these networks matters, both in terms of what types of networks exist across various complex systems and in terms of how different network structures influence system-wide behavior.
Consider a lake surrounded by houses. Each house in Lakeland is on the water, so for any given house there is only one neighbor to its left and one to its right. From a bird’s-eye view, each house occupies a bit of space on a circle formed by the lake’s edge (see Figure 8.1).
As in most neighborhoods, the behavior of each resident is influenced by her neighbors. To take just one example, suppose that each resident has to decide how much effort to spend on her lawn—say, whether to mow or not. The amount of effort that one exerts here may depend on the actions of one’s neighbors. If the neighbors keep immaculate, putting-green-like lawns, then you might be inclined to do so as well. If the neighboring lawns resemble weed-infested jungles, then your lawn care efforts might wane.
To explore this world, let’s assume that every Sunday each resident decides whether to mow her lawn. This decision is strongly influenced by her two immediate neighbors (one to the left and one to the right). To keep things simple, we assume that if both neighbors took the action opposite of what she did last week, then she will alter her action this week. Otherwise she will continue to do what she did the prior week.
This rule of behavior is equivalent to a crude form of majority rule. There is a group of three (the resident and her two neighbors) that is “voting” on what to do. If the resident and at least one of her neighbors did the same action last week, then this majority decision dictates what the resident does this week. If, instead, the resident deviated from both of her neighbors last week, then their two votes overrule hers, and she alters her behavior.
We have almost enough elements in place to begin exploring the system-wide behavior inherent in Lakeland. The one remaining piece is what happens during the first week of the lawn care season. The behavior above is predicated on the previous week’s behavior, and obviously there is no previous week at the start of the season. So to initialize the system, we will flip a coin for each resident to determine her initial action.
At first glance you might think that, given majority rule, whatever choice is in the majority the first week will dictate the behavior for the second week, and everyone in Lakeland will either always mow their lawn or never mow it. While this seems intuitive, recall that the behavior of each resident is tied only to that of her immediate neighbors, so there is no way for the global information about the initial majority choice across everyone in Lakeland to be instantly transmitted to each resident during the second week. Given this observation, you might modify your initial intuitions and imagine that over time, as neighbor influences neighbor, the initial majority will slowly flow around the lake in such a way that the system eventually ends up, after a few extra weeks, coordinating on whatever majority decision was initially drawn. Alas, as in most complex systems, such sensible intuitions are wrong.
Suppose, for whatever reason, two next-door neighbors start to take the same action. If this occurs, each of these two residents will always have at least one immediate neighbor taking the same action that she is doing. Given majority rule, this implies that neither of these two neighbors will ever change her action in the future.
Thus, anytime two neighbors take the same action, they will lock themselves into that action for the rest of the season. Since this lock-in depends on the action that is common across the pair, it suggests that as we watch the system over time we will see the formation of islands of neighbors taking a common action (either always or never mowing).
For the moment, focus on the edge of one of these islands. If the nearest neighbor next to the island’s edge ever decides to take the same action as the island, then that neighbor becomes part of the island, since she will always have at least one neighbor (the one next to her on the previous edge of the island) taking the same action as she is, and hence she will never want to change her action for the rest of the season. Over time, we might see the various islands slowly accreting new members as they absorb like-actioned nearest neighbors.
Thus, part of the dynamics of this system is a set of isolated islands of common action being established as pairs of neighbors happen upon the same action. At the start of the season, these islands will be scattered about the circle, with the exact location of, and common action for, each island being tied to the random initial conditions. Once established, these islands are likely to grow in size as they accrete like-actioned neighbors.
Do these growing islands slowly merge into a single, all-encompassing island that takes over the entire shoreline? To answer this question, think about what happens when two islands of opposite actions meet. At the boundary between these islands, we have two nearest neighbors taking different actions, but each one takes the same action as the neighbor on her other side. Thus, each of these nearest neighbors has one neighbor (the island mate) doing the same action and one neighbor (the boundary mate) doing the opposite. Given majority rule, neither one will want to change her chosen action. Thus, when two islands of opposite actions meet up, they both stop growing at the meeting point and a stable border is established.
Given the above, we now have enough insights to understand the dynamics of Lakeland. Whatever the random initial conditions, we will see islands of common action emerging from those spots on the shore where at least two nearest neighbors happen to take the same action.a Each of these islands will lock into having all of the island mates taking the identical action for the rest of the season, though that common action will vary across the different islands. Over time, residents that are not part of any existing island eventually get accreted into an island. When two islands of opposite action meet, a stable boundary is formed. These processes eventually lead Lakeland to a stable state that has contiguous groups of residents all taking the same action, with that action alternating as we go from group to group around the circle (see Figure 8.2).
Thus, Lakeland breaks down into a set of very stable groups pursuing very different actions, even though all of the residents follow the same behavioral rule. Moreover, the formation of these groups is tied to the initial conditions. If we rerun the model with new initial conditions, we might find that one season’s meticulous lawn keeper becomes next season’s cad letting her lawn go to seed.
Models become valuable when their insights can be applied to situations far beyond their initial motivation. So even if focusing on lawn care in Lakeland doesn’t seem of interest in and of itself, there are in fact a number of phenomena, such as lawn care, home maintenance, and what color you paint the exterior of your house, that are similarly influenced by social behavior and that can affect everything from property values to the long-term stability of a neighborhood. Thus, a basic model of lawn care can give us insights into how neighborhoods can fall apart, and perhaps even suggest policies that might put them back together—such as strategically targeting particular residents for behavioral changes that will result in large positive impacts on the overall state of the system.
A variety of other social behaviors may be influenced by neighbors. Consider education. The desire to do your homework (rather than go to a party), participate in class discussions, or even go to college is often influenced by the actions of your friends, and thus a Lakeland-like model may offer insight. Similar forces may influence criminal behavior, as the actions of one’s neighbors may encourage or discourage criminal activities, ranging from selling drugs to joining gangs. Indeed, in some communities, ignoring your lawn is viewed as an offense that is at best antisocial and perhaps even illegal.
Another obvious set of Lakeland-like models might involve religious and political choices. Religious practices, from celebrating particular holidays to decorating your house in lights to the choice of a religion itself, are often influenced by social networks and one’s desire to conform. Similarly, views on political issues and choice of political party can be influenced by social networks.
In Lakeland, we assumed that everyone lived on a circle, and that social influences came only from one’s nearest neighbors. This is a very extreme and sparse social network, and in more realistic models we might incorporate more complicated networks. For example, even in Lakeland, residents might be influenced not only by their nearest neighbors but also by their next-nearest neighbors. Furthermore, perhaps they can see across the lake, so the actions of more remote neighbors might be influential as well.
It has been found that changes to the structure of a network often have a big influence on system-wide behavior. Consider the problem of relaying a message to someone you don’t know via people you do know. Suppose that you want to send a message to a randomly chosen person in the network and that you are only allowed to pass this message to someone you are directly connected to, who in turn must pass it to someone she is directly connected to, and so on, until the message arrives at its destination. What is the smallest number of links (on average) that it will take for you to make the needed connection?
In Lakeland, where everyone lives on a circle and is only connected to her immediate neighbors, a randomly chosen recipient is likely to be one-quarter of the way around the circle from the original sender in one direction or the other (at most, the recipient and sender can be directly opposite each other, which is halfway around, so on average they will be at the one-quarter mark). Since messages can flow only across links in the network, the most direct route to the target will have the sender passing the message to her nearest neighbor in the shortest direction to the target. The neighbor will do the same, and so on. Therefore, the message will be passed through, on average, a quarter of the population of Lakeland before it arrives at the target. Note that as the population gets larger, the length of time to get the message to the target increases linearly. If there are 6 billion people arrayed around the lake, it will take, on average, 1.5 billion steps to deliver the message.
In Lakeland, everyone knows only her two nearest neighbors. In real networks, while we likely have a lot of very local connections, we often have a few more distant ones as well. So let’s modify Lakeland by giving some of the residents a connection to a randomly chosen person. This new network is like our original Lakeland, with everyone still connected to their nearest neighbors, but with the addition of a few new connections randomly spanning the lake. This new type of network (see Figure 8.3) is known as a small world network, for reasons that will become obvious in a moment.
Passing messages in a small world is very different from what we originally did in Lakeland. In Lakeland, we had the tedious process of going around the circle from nearest neighbor to nearest neighbor until we finally arrived at our target. In a small world, you can exploit the new, long-range connections to expedite delivery of the message. A small world resembles something akin to a network of local roads and highways. If you want to go somewhere fast, you take a few local roads to get on the highway, stay on the highway until you can exit near your destination, then proceed to your destination on the local roads.
While it is clear that small world networks should speed up message passing (after all, it can’t take any more steps than before, since you can always revert to the outer-ring, nearest-neighbor approach if need be), it is surprising how much less time it takes. Taking the example of 6 billion residents above, and assuming that each resident knows thirty people, then the expected number of passes is only about 6.6—it’s a small world after all! Recall that for a Lakeland with 6 billion residents we needed 1.5 billion steps if each resident had only two friends. If we assume thirty nearest neighbors, the equivalent calculation would require a message in Lakeland to be passed 100 million times.
Thus, if we are willing to accept the assumptions of small world networks, there is a little more than six degrees of separation between you and someone else on the planet (if we allow for the loss of a billion or so folks given their inability to participate on various grounds). The small world model assumes that random connections are possible between any two people in the world, and this assumption may not hold, so consider the estimate of six degrees of separation as a lower bound. Regardless, the result is remarkable.
Researchers have investigated various networks, including coauthors of scientific papers, people who friend each other on Facebook, the links that make up our electric power grid, biological regulatory networks that control the expression of genes, the connections across neurons in simple brains, and links across web pages, to name just a few. The evidence is slowly accumulating that many of these networks have a deep common structure that may provide a basis for developing some unified theories of how such networks arise and behave.
In 1969 Thomas Schelling created an interesting model similar to the ones discussed above. Schelling was interested in understanding issues surrounding segregation. Instead of people arrayed around a lake, suppose that each resident occupies a square on a checkerboard (where not all of the squares are occupied). Each resident in the interior of the board is surrounded by eight neighboring squares.
Suppose that each resident is either a type X or O. We assume that the two types of residents are tolerant of each other and that as long as at least 30 percent of their neighbors are the same type as they are, they are content to stay in place. However, if the proportion of same-type neighbors drops below 30 percent, that resident will randomly relocate to one of the empty squares.
Given the very weak preference for having neighbors of the same type, one might expect that the world described by this model would quickly settle down to a state with very little segregation between the two types. Unfortunately, the actual behavior confounds such an expectation.
Figure 8.4 shows the arrangement of residents both randomly arrayed on the landscape (top) and after everyone who wants to move has done so (bottom). At the start of the model, since residents are randomly placed on the board, on average 50 percent of a resident’s neighbors are of the same type and 50 percent are different. If you look at the initial configuration of residents, there is little evidence of segregation—whatever patterns you perceive are due to your mind wanting to put order and pattern on the randomness (this is a common phenomenon—for example, random sequences of coin flips look far more like HTHHHTTH . . . than HTHTHTHT . . . ).
Figure 8.4: The Schelling segregation model with 360 agents, where residents move if 30 percent or fewer of their neighbors are of the same type. The two types of residents are shown by the differently shaded cells, with the white cells being unoccupied. Both random starting states (top) lead to the corresponding ending states directly below. In both runs of the model, what begins as a world where on average the likelihood of a similar-type neighbor is around 50 percent transforms into a segregated world with a greater than 70 percent likelihood of similar-type neighbors. (The program that generated this output was created by Robert Hanneman.)
From the initial starting conditions, we allow any resident who has 30 percent or fewer neighbors of the same type to randomly relocate. As can be seen in the figure, such a process quickly leads to large, segregated neighborhoods. Indeed, we find that after the system settles down, each resident, on average, has around 70 percent of her neighbors being of the same type. Thus, a slight preference for having at least 30 percent of your neighbors being like you leads to having 70 percent of your neighbors being like you.
You might at first think that the random mixing we used to initialize the system would be sufficient to keep everyone in place, as on average each resident has 50 percent of her neighbors being similar. Of course, the 50 percent is an overall average, and some residents will live in neighborhoods with a higher or lower percentage of similar residents. Thus, some of the randomly placed residents will find themselves in neighborhoods with an insufficient number of same-type neighbors, and they will move. When a resident moves, each of her eight neighbors loses a neighbor of that type, and this may be sufficient to tip the balance of same-type residents for some of the old neighbors, inducing them to move as well. As the proportion of a given type of resident in a neighborhood goes well above 30 percent, it not only becomes more stable to that particular type but also drives out the opposite type. Similar to what happened in Lakeland, stable configurations of contiguous, same-type-resident islands begin to form, and these slowly grow as they accrete any newly displaced, same-type residents that happen to land nearby.
We have seen before how positive feedback loops can cause a system to rapidly tip into a new, self-reinforcing configuration that is far away from its starting point. Schelling’s system is governed by such feedback loops. Agents with a slight preference to be with same-type neighbors form positive feedback loops, with like begetting like.
If we alter the networks, we may induce very different behavior in the system. For example, the degree of segregation that arises in Schelling’s checkerboard tends to increase with some reasonable alternative network configurations such as Lakeland’s loops. In general, it can be shown that the key driving factor in these segregation systems is the amount of overlap any given resident has with her neighbors’ neighbors.
For the first part of human history, we were embedded in fairly static networks, consisting of some dense connections across a small tribe with occasional, though often transient, connections to outsiders. Over time, these networks have grown far more dense and dynamic as we have developed the ability to easily move and communicate across large distances. In the twentieth century, social networks grew more connected as mass media developed and a small group of people began to broadcast messages to others.
More recently, with the advent of computers, our networks have become even more complex, as we become “friends” with people we have never met in person who live in locations that we have never visited. We now interact with anywhere from a few dedicated friends to thousands of followers through email, blogs, status updates, and 144-character messages. We find ourselves at the nexus of overlapping networks consisting of large groups of friends, coworkers, and various other contacts. We are only beginning to understand the impact of this new, hypernetworked world in terms of complex social dynamics. Posting a picture of your freshly mowed lawn on Facebook may have social impacts far beyond your immediate neighborhood.