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. Chen, Lei & Yue, Dong & Dou, Chunxia, 2019. "Optimization on vulnerability analysis and redundancy protection in interdependent networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 1216-1226.
    4. À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.
    5. 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.
    6. Boris Salazar & María del Pilar Castillo, 2008. "Pobreza Urbana Y Exclusión Social De Los Desplazados," Documentos de Trabajo 4500, Universidad del Valle, CIDSE.
    7. Wang, Tao & Liao, Peng & Tang, Tie-Qiao & Huang, Hai-Jun, 2022. "Deterministic capacity drop and morning commute in traffic corridor with tandem bottlenecks: A new manifestation of capacity expansion paradox," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    8. 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.
    9. Blagus, Neli & Šubelj, Lovro & Bajec, Marko, 2012. "Self-similar scaling of density in complex real-world networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(8), pages 2794-2802.
    10. Douglas R. White & Jason Owen-Smith & James Moody & Walter W. Powell, 2004. "Networks, Fields and Organizations: Micro-Dynamics, Scale and Cohesive Embeddings," Computational and Mathematical Organization Theory, Springer, vol. 10(1), pages 95-117, May.
    11. 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).
    12. Khalilzadeh, Jalayer, 2022. "It is a small world, or is it? A look into two decades of tourism system," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).
    13. 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.
    14. Cowan, Robin & Jonard, Nicolas & Sanditov, Bulat, 2009. "Fits and Misfits: Technological Matching and R&D Networks," MERIT Working Papers 2009-042, United Nations University - Maastricht Economic and Social Research Institute on Innovation and Technology (MERIT).
    15. Amos Korman & Efrat Greenwald & Ofer Feinerman, 2014. "Confidence Sharing: An Economic Strategy for Efficient Information Flows in Animal Groups," PLOS Computational Biology, Public Library of Science, vol. 10(10), pages 1-10, October.
    16. Xiaoge Zhang & Sankaran Mahadevan & Kai Goebel, 2019. "Network Reconfiguration for Increasing Transportation System Resilience Under Extreme Events," Risk Analysis, John Wiley & Sons, vol. 39(9), pages 2054-2075, September.
    17. 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.
    18. Gao, Xiangyun & An, Haizhong & Fang, Wei & Li, Huajiao & Sun, Xiaoqi, 2014. "The transmission of fluctuant patterns of the forex burden based on international crude oil prices," Energy, Elsevier, vol. 73(C), pages 380-386.
    19. Shi, Xiaolin & Adamic, Lada A. & Strauss, Martin J., 2007. "Networks of strong ties," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 378(1), pages 33-47.
    20. 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.

    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.