small world graph

D.J. Watts and S.H. Strogatz. Colletive dynamics of 'small world' networks.
Nature, 393:440-442,1998

small-world topologies have been extensively applied to model computer networks or social behaviors. They are typically characterized by high clustering co-efficients ( average fraction of pairs of neighbors of a node that are also neighbors of each other) and relatively small path length (average minimal distance between two nodes).