The systems you are looking for belong to the class of small-world networks, introduced in 1998 by Watts and Strogatz. Quite generally, a small-world network is defined to be a network where the typical distance between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes in the network. Wikipedia provides a good starting point for exploration: <A HREF="https://en.wikipedia.org/wiki/Small-world_network">Small-world networks</A> <A HREF="https://en.wikipedia.org/wiki/Small-world_experiment">Small-world experiments</A> Specifically related to the Erdős number is this online lecture by John Barrow: <A HREF="http://www.youtube.com/watch?v=F5ZsM5OijYs"> Erdős Numbers: A mathematical example of 'small world' networks</A> Related MO posts dealing with the dynamics of the Erdős number (and suggesting the introduction of a Mathoverflow number): <A HREF="http://mathoverflow.net/questions/100099">How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?</A> <A HREF="http://mathoverflow.net/questions/45586">The diameter of the Erdös component of the collaboration graph</A>