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

Publisher: IGI Global_journal

E-ISSN: 1947-9336|9|3|27-51

ISSN: 1947-9328

Source: International Journal of Operations Research and Information Systems (IJORIS), Vol.9, Iss.3, 2018-07, pp. : 27-51

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.