On the Mean Distance in Scale Free Graphs

G. Hooghiemstra () and P. Mieghem ()
Additional contact information
G. Hooghiemstra: Delft University of Technology
P. Mieghem: Delft University of Technology

Methodology and Computing in Applied Probability, 2005, vol. 7, issue 3, 285-306

Abstract: Abstract 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.

Keywords: scale free graphs; mean distance (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-005-4518-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:7:y:2005:i:3:d:10.1007_s11009-005-4518-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-005-4518-8

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().