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:
Specifically related to the Erdős number is this online lecture by John Barrow:
Erdős Numbers: A mathematical example of 'small world' networks
Related MO posts dealing with the dynamics of the Erdős number (and suggesting the introduction of a Mathoverflow number):
The diameter of the Erdös component of the collaboration graph