the small-world phenomenon and the diameter

The small-world phenomenon is the empirical fact, dramatized as 'six degrees of separation', that in large real networks any two nodes are joined by a surprisingly short path. Random graph theory makes this precise through the diameter (the longest shortest-path distance between any two vertices) and the typical distance (the distance between two random vertices). The headline finding is that random graphs are small worlds: distances grow only logarithmically in the number of vertices. The question it answers is: how far apart, in hops, are vertices in a graph that has only a handful of edges per node?

The reason is again the branching heuristic. In G(n,p) with np = c > 1, the number of vertices within distance r of a fixed vertex grows like c^r (each step multiplies the frontier by the average degree), so to reach a constant fraction of the n vertices you need r about log n / log c steps. Made rigorous, this gives typical distance and diameter both of order (log n)/(log(np)) in the supercritical sparse regime — for fixed average degree the diameter is Theta(log n). The dependence on degree is the crucial twist: distances scale as (log n)/(log d) where d is the average degree, so denser graphs are smaller worlds. For networks with heavy-tailed degrees the effect is even more extreme: in a configuration model or preferential-attachment graph with power-law exponent gamma between 2 and 3, the typical distance is only of order log log n — an 'ultra-small world' — because hubs act as shortcuts that almost everyone is one or two steps from. In the dense regime p fixed, the diameter collapses to 2 (whp any two vertices have a common neighbour).

This phenomenon matters because it underlies the speed of information, rumour, and epidemic spread, the efficiency of peer-to-peer and routing networks, and Milgram's famous experiment. The honest subtleties are worth stating. First, 'small diameter' and 'efficient navigation' are different: Kleinberg showed that a graph can have logarithmic diameter yet be impossible to route on with only local information unless the long-range links have exactly the right (inverse-square in 2D) distance distribution — short paths existing is not the same as them being findable. Second, the logarithmic-diameter result needs the graph to be (essentially) connected and supercritical; below the giant threshold there is no notion of a global diameter. Third, the ultra-small log log n scaling is a genuine consequence of heavy tails, not of the small-world property per se, and disappears once gamma exceeds 3 (then it is back to log n).