IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v556y2020ics0378437120303642.html
   My bibliography  Save this article

On achieving capacity-enhanced small-world networks

Author

Listed:
  • Chakraborty, Abhishek
  • Babu, Sarath
  • Manoj, B.S.

Abstract

Networks, whether it is communication or transportation, often suffer from significant degradation in average network flow capacity (ANFC) due to the presence of one or more bottleneck nodes. Presence of a few long-ranged links, connecting distant nodes in a regular network, enhances ANFC and incorporates small-world characteristics. However, the existing deterministic long-ranged link addition strategies based on minimum average path length, maximum betweenness centrality, or maximum closeness centrality, cannot guarantee significant improvement in ANFC. In this paper, we propose an exhaustive search-based long-ranged link (LL) addition algorithm, maximum flow capacity (MaxCap), which deterministically maximizes ANFC, based on the maximum flow (of information or objects) among node-pairs in the context of weighted undirected networks. Furthermore, based on the observations from MaxCap, we propose a new LL addition heuristic, average network flow capacity enhancement using small-world characteristics (ACES), which significantly enhances ANFC and the LL length-type product, and improves traffic load distribution in a weighted undirected network. We validate the performance of our LL addition method through exhaustive simulations on various arbitrary networks and real-world road transportation networks. ACES can be applied to many real-world applications in communication networks, transportation networks, and tactical networks where ANFC is a critical parameter.

Suggested Citation

  • Chakraborty, Abhishek & Babu, Sarath & Manoj, B.S., 2020. "On achieving capacity-enhanced small-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 556(C).
    • Handle: RePEc:eee:phsmap:v:556:y:2020:i:c:s0378437120303642
    DOI: 10.1016/j.physa.2020.124729
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437120303642
    Download Restriction: 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
    File URL: https://libkey.io/10.1016/j.physa.2020.124729?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. M. E. J. Newman & D. J. Watts, 1999. "Renormalization Group Analysis of the Small-World Network Model," Working Papers 99-04-029, Santa Fe Institute.
    2. Jon M. Kleinberg, 2000. "Navigation in a small world," Nature, Nature, vol. 406(6798), pages 845-845, August.
    3. Richard Steinberg & Willard I. Zangwill, 1983. "The Prevalence of Braess' Paradox," Transportation Science, INFORMS, vol. 17(3), pages 301-318, August.
    4. Yang, Han-Xin & Sun, Lei, 2020. "Heterogeneous donation game in geographical small-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 540(C).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lu, Zhe-Ming & Guo, Shi-Ze, 2012. "A small-world network derived from the deterministic uniform recursive tree," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(1), pages 87-92.
    2. Huang, Wei & Chen, Shengyong & Wang, Wanliang, 2014. "Navigation in spatial networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 393(C), pages 132-154.
    3. Marcus Berliant & Axel H. Watanabe, 2018. "A scale‐free transportation network explains the city‐size distribution," Quantitative Economics, Econometric Society, vol. 9(3), pages 1419-1451, November.
    4. Andrea Avena-Koenigsberger & Xiaoran Yan & Artemy Kolchinsky & Martijn P van den Heuvel & Patric Hagmann & Olaf Sporns, 2019. "A spectrum of routing strategies for brain networks," PLOS Computational Biology, Public Library of Science, vol. 15(3), pages 1-24, March.
    5. An, Sufang & Gao, Xiangyun & An, Haizhong & Liu, Siyao & Sun, Qingru & Jia, Nanfei, 2020. "Dynamic volatility spillovers among bulk mineral commodities: A network method," Resources Policy, Elsevier, vol. 66(C).
    6. Xiangyun Gao & Haizhong An & Weiqiong Zhong, 2013. "Features of the Correlation Structure of Price Indices," PLOS ONE, Public Library of Science, vol. 8(4), pages 1-9, April.
    7. Chung-Yuan Huang & Chuen-Tsai Sun & Hsun-Cheng Lin, 2005. "Influence of Local Information on Social Simulations in Small-World Network Models," Journal of Artificial Societies and Social Simulation, Journal of Artificial Societies and Social Simulation, vol. 8(4), pages 1-8.
    8. Peter Biddle & Paul England & Marcus Peinado & Bryan Willman, 2003. "The Darknet and the Future of Content Distribution," Levine's Working Paper Archive 618897000000000636, David K. Levine.
    9. Xiao Han & Yun Yu & Bin Jia & Zi‐You Gao & Rui Jiang & H. Michael Zhang, 2021. "Coordination Behavior in Mode Choice: Laboratory Study of Equilibrium Transformation and Selection," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3635-3656, October.
    10. Joost Berkhout & Bernd F. Heidergott, 2019. "Analysis of Markov Influence Graphs," Operations Research, INFORMS, vol. 67(3), pages 892-904, May.
    11. Kondor, Dániel & Mátray, Péter & Csabai, István & Vattay, Gábor, 2013. "Measuring the dimension of partially embedded networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(18), pages 4160-4171.
    12. Khalid Bakhshaliyev & Mehmet Hadi Gunes, 2020. "Generation of 2-mode scale-free graphs for link-level internet topology modeling," PLOS ONE, Public Library of Science, vol. 15(11), pages 1-23, November.
    13. Yu, Haitao & Guo, Xinmeng & Wang, Jiang & Deng, Bin & Wei, Xile, 2015. "Vibrational resonance in adaptive small-world neuronal networks with spike-timing-dependent plasticity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 170-179.
    14. Nicolas Jonard & R. Cowan & B. Sanditov, 2009. "Fits and Misfits : Technological Matching and R & D Networks," DEM Discussion Paper Series 09-12, Department of Economics at the University of Luxembourg.
    15. Bittihn, Stefan & Schadschneider, Andreas, 2021. "The effect of modern traffic information on Braess’ paradox," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 571(C).
    16. Mark Newman, 1999. "Small Worlds: The Structure of Social Networks," Working Papers 99-12-080, Santa Fe Institute.
    17. An, Haizhong & Gao, Xiangyun & Fang, Wei & Ding, Yinghui & Zhong, Weiqiong, 2014. "Research on patterns in the fluctuation of the co-movement between crude oil futures and spot prices: A complex network approach," Applied Energy, Elsevier, vol. 136(C), pages 1067-1075.
    18. Àlex Arenas & Antonio Cabrales & Leon Danon & Albert Díaz-Guilera & Roger Guimerà & Fernando Vega-Redondo, 2010. "Optimal information transmission in organizations: search and congestion," Review of Economic Design, Springer;Society for Economic Design, vol. 14(1), pages 75-93, March.
    19. Yu, Haitao & Guo, Xinmeng & Wang, Jiang & Deng, Bin & Wei, Xile, 2015. "Spike coherence and synchronization on Newman–Watts small-world neuronal networks modulated by spike-timing-dependent plasticity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 419(C), pages 307-317.
    20. Song, Xiao & Shi, Wen & Ma, Yaofei & Yang, Chen, 2015. "Impact of informal networks on opinion dynamics in hierarchically formal organization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 916-924.

    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:eee:phsmap:v:556:y:2020:i:c:s0378437120303642. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.