IDEAS home Printed from https://ideas.repec.org/a/igg/joris0/v9y2018i3p27-51.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Luis E. Castro & Nazrul I. Shaikh, 2018. "Random Node Pair Sampling-Based Estimation of Average Path Lengths in Networks," International Journal of Operations Research and Information Systems (IJORIS), IGI Global, vol. 9(3), pages 27-51, July.
    • Handle: RePEc:igg:joris0:v:9:y:2018:i:3:p:27-51
    as

    Download full text from publisher

    File URL: http://services.igi-global.com/resolvedoi/resolve.aspx?doi=10.4018/IJORIS.2018070102
    Download Restriction: no
    ---><---

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:igg:joris0:v:9:y:2018:i:3:p:27-51. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Journal Editor (email available below). General contact details of provider: https://www.igi-global.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.