Width of the World Wide Web
At the turn of the 21st century, several research groups independently studied the concept of interconnectedness popularized by ‘six degrees of separation’ in the context of the World Wide Web. In this post, I will take a look at a specific study done by Albert, Jeong & Barabási at the University of Notre Dame.
The study was carried about by a computer program that recursively followed links present on a page, adding to the database at each step the number of links present on the current page. While at one level this program accurately reconstructed the network structure of this portion of the web, the raw data was analyzed further to make predictions about the properties of the World Wide Web.
The first finding was a probability distribution of the number of links to and from a webpage. This law—the power law—was then used to predict what the shortest path between a pair of randomly picked nodes in the network will be. The result showed a logarithmic relation between the number of webpages and this average degree of separation.
In 1999, this average degree of separation between two nodes, or ‘width’ of the internet was estimated to be 19. Today, even though the number of webpages has increased exponentially, the diameter is expected to be around 21 or so.
It is interesting to compare these conclusions to similar figures about the social network. Even though the internet has fewer nodes than the social network (about 4.8 billion as compared to 7 billion), the internet has a significantly higher degree of separation.
From what we studied in class, this may be caused by two facts. First, the internet is a directed graph—a hyperlink from one page to another doesn’t imply a link back. Second, and perhaps more importantly, the average number of links in a webpage are fewer than the average number of acquaintances a human has. This perspective is helpful in making sense of the conclusions of this study.
Article in the Scientific American:
http://www.americanscientist.org/issues/pub/graph-theory-in-practice-part-i/99999
Original Study Published in Nature:
http://www.nature.com/nature/journal/v401/n6749/full/401130a0.html