Average hopcount of the shortest path in tree-like components with finite size

Dongchao Guo, Hao Yin, Cong Li and Xu Zhang

Physica A: Statistical Mechanics and its Applications, 2019, vol. 519, issue C, 295-302

Abstract: An exact formula for computing the average hopcount of the shortest path in finite-size tree-like components of undirected unweighted random networks is proposed. In a tree-like component with size s, there exists virtually only one shortest path between two arbitrary nodes. The summation of hopcounts of all shortest paths can be calculated approximately by the summation of the betweenness of all nodes, and the difference between them is only a constant s(s−1). Therefore, the average hopcount can be calculated by further dividing the summation by the number of all shortest paths. In this paper, we first derive the conditional probability p(k|s) of the degree distribution of finite components with size s and the summation of all nodal betweenness respectively. By means of these results, we obtain the exact formula for calculating the average hopcount. Also, We confirm the proposed formula by simulations for networks with Poisson and power law degree distributions respectively.

Keywords: Random graph; Average shortest path; Finite component; Configuration model (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437118315474
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:519:y:2019:i:c:p:295-302

DOI: 10.1016/j.physa.2018.12.034

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().