With hundreds of degrees of separation, the Internet doesn't always resemble a 'small world'
By Bill Steele
Jon Kleinberg with a "life-size" diagram of the path a chain letter follows as it moves from person to person on the Internet. The pattern differs from the well-known "six degrees of separation" rule, showing that different mechanisms can operate in the same network.
While there may be only 6 degrees of separation between individuals, when it comes to spreading information across the Internet, sometimes there are hundreds of degrees of separation.
A study of Internet chain letters by Jon Kleinberg, Cornell professor of computer science, and David Liben-Nowell '99, professor of computer science at Carleton College, shows that such messages do not fan out widely, reaching many people in a short time, but instead travel in long straight lines. On average, they found, the last recipient of a message is several hundred steps away from the originator. The study appears in the online edition of the Proceedings of the National Academy of Sciences.
"That joke you just received from a friend may have gone through a lot more people than you think," Kleinberg said. "The 'six degrees' are still there, but those aren't the paths the chain letters followed; the short paths and the highly roundabout communication routes coexist in the same network."
Kleinberg and Liben-Nowell tracked two Internet chain letters — a 2002-03 petition against the invasion of Iraq and a 1995 effort to support public radio. Each instructed recipients to add their name to a list and forward copies to as many people as possible. Here and there in the propagation of the messages, copies had been sent to e-mail mailing lists, so the researchers were able to obtain copies from mailing list archives.
Closeup of the diagram shows that most nodes have only one child. It's expected that each person would forward the message to a large group of friends, but computer modeling suggests that only one or a few members of a small group would send the message outside the group to create this pattern.
They found 637 copies of the Iraq petition listing nearly 20,000 signers and 316 copies of the NPR petition listing 13,052 people. Using a computer to compare and match the various lists, they reconstructed a tree showing how the messages traveled.
Current theory, the researchers said, is that information spreads through social networks -- on the Internet or in everyday life — quickly and widely: Each person forwards the message to many people, who in turn send it on, and the message spreads far and wide.
But instead of the expected fanning out, they saw many parallel trickles, like rainwater running down a window glass at the beginning of a shower. Surprisingly, 90 percent of the nodes on the tree had just one offspring. In developing a mathematical model that would produce similar results, the researchers found that the key was to assume a variable time between receiving and forwarding a message, and that people belong to highly overlapping circles of friends, causing the message to echo through close-knit social groups before being forwarded.
The results provide insight into such social phenomena as opinion formation and political mobilization, the researchers suggest. The large number of steps also makes it possible for information to be altered or lost along the way. Previous research has shown that social networks — even one as vast as the Internet — have many long cross-connections among small groups, and this creates a "small world" where everyone is only a few steps away from everyone else.
But this study, the researchers said, suggests that even within this small world other natural processes can lead to different patterns.
To refine their study, the researchers are seeking persons who have saved copies of the two chain letters with full or partial lists of signers. For more information go to http://petitions.cs.cornell.edu/.
The work was supported by a MacArthur Foundation Grant, the National Science Foundation, Google and Yahoo.
Note to media: David Liben-Nowell's last name rhymes with "ribbon towel."
Get Cornell news delivered right to your inbox.
Subscribe