2129. Internet graph

The whole of internet can be seen as a huge graph, in which the nodes are the webages and an edge is a hyperlink from one webpage to another webpage. On can start from a webpage and “hop” to several webpages by just clicking on the hyperlinks present in a webpage. Given a graph representing the internet, we want to know what is the average shortest distance between any two webpages.

Note that this graph will be directed. Consider the graph given below. The length of the shortest path from node 1 to nodes 2, 3, and 4 is 1,1, and 2 respectively. From node 2 to nodes 1, 3 and 4, the shortest paths have lengths of 3, 2, and 1. From node 3 to nodes 1, 2, and 4, the shortest paths have lengths of 1, 2, and 3. Finally, from node 4 to nodes 1, 2, and 3 the shortest paths have lengths of 2, 3, and 1. The sum of these path lengths is 1 + 1 + 2 + 3 + 2 + 1 + 1 + 2 + 3 + 2 + 3 + 1 = 22. Since there are 12 possible pairs of nodes to consider, we obtain an average path length of 22/12, or 1.833 (accurate to three fractional digits).