Finding the Shortest Average Path Lengths in Kleinberg’s Small World Model

Abstract

The history of the research published on networks and the small world phenomena in particular is discussed. The Kleinberg small world model is examined and extended to an underlying torus structure as well as the original grid structure. The lengths and number of paths available using the Kleinberg algorithm, which relies only on local knowledge of the network, is determined. An average path length is defined and the network with the smallest average is determined. For small orders, n=3 and n=4, this is calculated exactly. For slightly larger orders of up to n=8, this is estimated. These estimates are then tested by statistical random sampling.