I came across an interesting article while searching for information related to Stanley Milgram’s “small-world” network. Those of you who have read “The Tipping Point” may remember Malcolm Gladwell’s story about Stanley Milgram, the psychologist who in 1967 gave 160 residents of Omaha, Nebraska a letter with the name of a stockbroker who lived in Cambridge, Massachusetts, and asked each of the Nebraskans to send the letter to a friend or acquaintance whom they believed would be able to get the letter closer to the stockbroker. Milgram found that the letters reached the stockbroker in six steps on average. In his paper, “The Small-World Problem,” about the experiment, Milgram coined the phase “six degrees of separation,” and theorized that any two people in the United States are connected through a short path of social acquaintances.

 In 1998, Steven Strogatz and Duncan Watts (the same Watts from the “Empirical Analysis of an Evolving Social Network” article we read) defined a small-world network as a graph with a high clustering coefficient and small mean-shortest path length in their paper, “Collective Dynamics of Small-World Networks.” They also proposed a mathematical model for a small-world network by taking a regular network (meaning a completely structured lattice-type network) and replacing some of structured connections with randomly assigned connection, thus creating a hybrid between a completely regular network and a completely random network. They also showed the neural network of a certain type of worm, the power grid in the Western United States, and “the collaboration graph of film actors” all could be modeled as small-world networks. Since that paper, many others have been published, applying this small-world model (or modified versions of it) to real-life networks.

The interesting article which I came across, “The Diameter of the World Wide Web,” is by Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabasi. The article describes an experiment they conducted to help describe the topology of the internet by modeling its local connectivity. They created “robots” which take a page on the web, search it for any URLs, and then follow those URLs to find related pages, search those pages for URLs and follow those URLs, and so on, recording data all the while. Then they used this data to create the probability function that a page had k  incoming URL links and the probability function that a page had k outgoing URL links. They found that these probability function did not fit those predicted for random graphs, but that they described a small-world network model. They also used these probability functions to create a define “d,“ the average number of URL links from any one page to any other page (or, as they call it, the “diameter” of the web), as a function of the number of pages. Plugging in 800 million for the number of web pages (this article was written in 1999), they found the “diameter” of the internet to be 18.59, so from any page on the web, every other page of the internet is on average about 19 URL links away.

The researchers did mention that were the internet to increase by 1000% (or to 8.8 billion pages, which is around the values that have been thrown around in lecture), the diameter would only change from 19 to 21 due to the “logorithmic dependence” on N.

 There are some important results discussed in this paper which I think are very applicable to our discussion of the internet as a network in lecture. For one, this paper provided insight into the topology of the world wide web: it can be modeled as a small-world network, meaning it is clustered, yet has a small mean-shortest path length. Also, the mean-shortest path length is around 19 (or 21 by now), which means the web is highly connected, relative to its size.

 The URL for the “Diameter of the World Wide Web” article is below:

http://www.cs.cmu.edu/~eairoldi/nets/public/albe.jeon.bara.1999.pdf