As Goes Kevin Bacon, So Goes the Web, Researchers Report

Author: By Vincent Kiernan

Move over, Kevin Bacon.p. Five years ago, college students invented “Six Degrees of Kevin Bacon,” a game based on the premise that any actor could be linked to Mr. Bacon by a chain of five or fewer other actors who had starred with one another. Internet researchers report today that they have found a similar phenomenon on the World-Wide Web: Any two randomly chosen Web pages are, on average, 19 clicks away from one another.p. Despite the enormous size of the Web — it has some 800 million pages — enough pages contain multiple hyperlinks that it is possible to get anywhere on the Web by traversing only a few links, according to a paper in today’s issue of the journal Nature.p. The authors of the paper — Albert-Laszlo Barabasi, an associate professor of physics at University of Notre Dame; Reka Albert, a doctoral student in physics at the university; and Hawoong Jeong, a postdoctoral research associate there — developed a way to measure the average number of links between pages, which they call the “diameter” of the World-Wide Web. They did so by creating a software “robot” that followed hyperlinks between pages in Notre Dame’s “” Internet domain.p. The researchers found that the number of outbound links that each page contained — and the number of pages that were linked into that page — were not random but rather followed a “power-tail law,” a mathematical rule that describes the frequency of various measurements in a population.p. The same power-tail law held true for pages linked from three Internet domains outside Notre Dame’s —,, and That finding means that the same statistical pattern of connections among Web sites existed in those parts of the Web as well, the researchers wrote.p. The researchers measured the exact number of links between individual pages in Notre Dame’s domain and calculated that they were an average of 11.2 links away from one another — very close to the 11.6 links that the power-tail law predicted. The researchers then extrapolated the power-tail law to the entire Web to produce the estimate that any two pages, anywhere on the Web, are an average of 18.59 links away from one another.p. It was surprising that a power-tail law described patterns of Web links, said Mr. Barabasi, because power-tail laws usually are valid only for systems driven by a central organizing principle, such as that which determines the pattern of links among interconnected electrical utilities.p. The existence of a power-tail law for the Web suggests that some still-unknown process is operating on Web authors to shape their work, even though individuals are free to include on their Web pages as many links as they like, he said. “This clearly indicates that the Web is not just random.”p. The game involving Mr. Bacon is based loosely on research by a social psychologist, Stanley Milgram of Yale University, who demonstrated in the 1960s that any two individuals were linked by, at most, five mutual acquaintances.p. Mr. Barabasi said that the number of links between any two Web pages is so much greater than the number of mutual acquaintances between strangers (or co-stars between Mr. Bacon and any other actor) because the average Web page contains only seven links. “But you might know hundreds or thousands of people,” which shortens the chain of acquaintances, he said.p. The three researchers wrote that their findings suggest that a new type of Web search engine could outperform conventional search engines, which index the text of many individual pages and use them to find specified terms. An “intelligent agent,” the researchers wrote, could take advantage of the connectedness of the Web by identifying the 19 correct links to get to the information that a user wants, rather than relying on the brute-force approach of indexing the Web. However, Mr. Barabasi said that he had not designed such an intelligent agent.

TopicID: 375