On the Mean Distance in Scale Free Graphs

We consider a graph, where the nodes have a pre-described degree distribution F, and where nodes are randomly connected in accordance to their degree. Based on a recent result (R. van der Hofstad, G. Hooghiemstra and P. Van Mieghem, “Random graphs with finite variance degrees,” Random Structures and Algorithms, vol. 17(5) pp. 76–105, 2005), we improve the approximation of the mean distance between two randomly chosen nodes given by M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Random graphs with arbitrary degree distribution and their application,” Physical Review. E vol. 64, 026118, pp. 1–17, 2001. Our new expression for the mean distance involves the expectation of the logarithm of the limit of a super-critical branching process. We compare simulations of the mean distance with the results of Newman et al. and with our new approach. AMS 2000 Subject Classification: 05C80, 60F05