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