Random Node Pair Sampling-Based Estimation of Average Path Lengths in Networks

Luis E. Castro and Nazrul I. Shaikh
Additional contact information
Luis E. Castro: Department of Industrial Engineering, University of Miami, Coral Gables, USA
Nazrul I. Shaikh: Department of Industrial Engineering, University of Miami, Coral Gables, USA

International Journal of Operations Research and Information Systems (IJORIS), 2018, vol. 9, issue 3, 27-51

Abstract: This article describes how the average path length (APL) of a network is an important metric that provides insights on the interconnectivity in a network and how much time and effort would be required for search and navigation on that network. However, the estimation of APL is time-consuming as its computational complexity scales nonlinearly with the network size. In this article, the authors develop a computationally efficient random node pair sampling algorithm that enables the estimation of APL with a specified precision and confidence. The proposed sampling algorithms provide a speed-up factor ranging from 240-750 for networks with more than 100,000 nodes. The authors also find that the computational time required for estimation APL does not necessarily increase with the network size; it shows an inverted U shape instead.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 18/IJORIS.2018070102 (application/pdf)

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:igg:joris0:v:9:y:2018:i:3:p:27-51

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().