IDEAS home Printed from https://ideas.repec.org/a/spr/eurphb/v92y2019i6d10.1140_epjb_e2019-100139-5.html
   My bibliography  Save this article

Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication

Author

Listed:
  • Chanania Steinbock

    (Racah Institute of Physics, The Hebrew University)

  • Ofer Biham

    (Racah Institute of Physics, The Hebrew University)

  • Eytan Katzav

    (Racah Institute of Physics, The Hebrew University)

Abstract

We present exact analytical results for the distribution of shortest path lengths (DSPL) in a directed network model that grows by node duplication. Such models are useful in the study of the structure and growth dynamics of gene regulatory networks and scientific citation networks. Starting from an initial seed network, at each time step a random node, referred to as a mother node, is selected for duplication. Its daughter node is added to the network and duplicates each outgoing link of the mother node with probability p. In addition, the daughter node forms a directed link to the mother node itself. Thus, the model is referred to as the corded directed-node-duplication (DND) model. In this network not all pairs of nodes are connected by directed paths, in spite of the fact that the corresponding undirected network consists of a single connected component. More specifically, in the large network limit only a diminishing fraction of pairs of nodes are connected by directed paths. To calculate the DSPL between those pairs of nodes that are connected by directed paths we derive a master equation for the time evolution of the probability Pt(L = ℓ), ℓ = 1, 2, … , where ℓ is the length of the shortest directed path. Solving the master equation, we obtain a closed form expression for Pt(L = ℓ). It is found that the DSPL at time t consists of a convolution of the initial DSPL P0(L = ℓ), with a Poisson distribution and a sum of Poisson distributions. The mean distance 𝔼t[L|L

Suggested Citation

  • Chanania Steinbock & Ofer Biham & Eytan Katzav, 2019. "Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 92(6), pages 1-16, June.
    • Handle: RePEc:spr:eurphb:v:92:y:2019:i:6:d:10.1140_epjb_e2019-100139-5
    DOI: 10.1140/epjb/e2019-100139-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1140/epjb/e2019-100139-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1140/epjb/e2019-100139-5?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. Caldarelli, Guido, 2007. "Scale-Free Networks: Complex Webs in Nature and Technology," OUP Catalogue, Oxford University Press, number 9780199211517.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Siudem, Grzegorz & Nowak, Przemysław & Gagolewski, Marek, 2022. "Power laws, the Price model, and the Pareto type-2 distribution," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 606(C).

    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. Diego Garlaschelli & Maria I. Loffredo, 2007. "Effects of network topology on wealth distributions," Papers 0711.4710, arXiv.org, revised Jan 2008.
    2. Ya-Chun Gao & Zong-Wen Wei & Bing-Hong Wang, 2013. "Dynamic Evolution Of Financial Network And Its Relation To Economic Crises," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 24(02), pages 1-10.
    3. Hutzler, S. & Sommer, C. & Richmond, P., 2016. "On the relationship between income, fertility rates and the state of democracy in society," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 452(C), pages 9-18.
    4. Andreas Koulouris & Ioannis Katerelos & Theodore Tsekeris, 2013. "Multi-Equilibria Regulation Agent-Based Model of Opinion Dynamics in Social Networks," Interdisciplinary Description of Complex Systems - scientific journal, Croatian Interdisciplinary Society Provider Homepage: http://indecs.eu, vol. 11(1), pages 51-70.
    5. Macon, Kevin T. & Mucha, Peter J. & Porter, Mason A., 2012. "Community structure in the United Nations General Assembly," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(1), pages 343-361.
    6. Tsekeris, Theodore, 2016. "Interregional trade network analysis for road freight transport in Greece," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 132-148.
    7. F. Daolio & M. Tomassini & K. Bitkov, 2011. "The Swiss board directors network in 2009," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 82(3), pages 349-359, August.
    8. Cui, Yaozu & Wang, Xingyuan & Eustace, Justine, 2014. "Detecting community structure via the maximal sub-graphs and belonging degrees in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 416(C), pages 198-207.
    9. Shekhtman, Louis M. & Danziger, Michael M. & Havlin, Shlomo, 2016. "Recent advances on failure and recovery in networks of networks," Chaos, Solitons & Fractals, Elsevier, vol. 90(C), pages 28-36.
    10. Gabriele Ranco & Ilaria Bordino & Giacomo Bormetti & Guido Caldarelli & Fabrizio Lillo & Michele Treccani, 2014. "Coupling news sentiment with web browsing data improves prediction of intra-day price dynamics," Papers 1412.3948, arXiv.org, revised Dec 2015.
    11. Wang, Zhenggang & Szeto, K.Y., 2010. "Structure profile of complex networks by a model of precipitation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(11), pages 2318-2324.
    12. Mohammad Ariapour & Ehsan Nedaaee Oskoee, 2013. "Constructing Scale-Free Networks With A Given Cluster Coefficient," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 24(02), pages 1-14.
    13. Roy Cerqueti & Giulia Rotundo & Marcel Ausloos, 2021. "Tsallis entropy for cross-shareholding network configurations," Papers 2109.04214, arXiv.org.
    14. Danilo Delpini & Stefano Battiston & Guido Caldarelli & Massimo Riccaboni, 2019. "Systemic risk from investment similarities," PLOS ONE, Public Library of Science, vol. 14(5), pages 1-15, May.
    15. Roberto Antonietti & Giulia De Masi & Giorgio Ricchiuti, 2020. "Linking FDI Network Topology with the Covid-19 Pandemic," Papers in Evolutionary Economic Geography (PEEG) 2054, Utrecht University, Department of Human Geography and Spatial Planning, Group Economic Geography, revised Nov 2020.
    16. Brancaccio, Emiliano & Giammetti, Raffaele & Lopreite, Milena & Puliga, Michelangelo, 2019. "Monetary policy, crisis and capital centralization in corporate ownership and control networks: A B-Var analysis," Structural Change and Economic Dynamics, Elsevier, vol. 51(C), pages 55-66.
    17. Alessandro Chessa & Pierpaolo D’Urso & Livia Giovanni & Vincenzina Vitale & Alfonso Gebbia, 2023. "Complex networks for community detection of basketball players," Annals of Operations Research, Springer, vol. 325(1), pages 363-389, June.
    18. Giorgio Fagiolo & Tiziano Squartini & Diego Garlaschelli, 2013. "Null models of economic networks: the case of the world trade web," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 8(1), pages 75-107, April.
    19. Andrey Sokolov & Rachel Webster & Andrew Melatos & Tien Kieu, 2012. "Loan and nonloan flows in the Australian interbank network," Papers 1202.3182, arXiv.org.
    20. Ding, Jie & Wen, Changyun & Li, Guoqi, 2017. "Key node selection in minimum-cost control of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 486(C), pages 251-261.

    More about this item

    Keywords

    Statistical and Nonlinear Physics;

    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:spr:eurphb:v:92:y:2019:i:6:d:10.1140_epjb_e2019-100139-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.