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

Impact of initial lattice structures on networks generated by traces of random walks

Author

Listed:
  • Ikeda, Nobutoshi

Abstract

We show that the platform stage of network evolution plays a principal role in the topology of resulting networks generated by short-cuts stimulated by the movements of a random walker, the mechanism of which tends to produce power-law degree distributions. To examine the numerical results, we have developed a statistical method which relates the power-law exponent γ to random properties of the subgraph developed in the platform stage. As a result, we find that an important exponent in the network evolution is α, which characterizes the size of the subgraph in the form V∼tα, where V and t denote the number of vertices in the subgraph and the time variable, respectively. 2D lattices can impose specific limitations on the walker’s diffusion, which keeps the value of α within a moderate range and provides typical properties of complex networks. 1D and 3D cases correspond to different ends of the spectrum for α, with 2D cases in between. Especially for 2D square lattices, a discontinuous change of the network structure is observed, which varies according to whether γ is greater or less than 2. For 1D cases, we show that emergence of nearly complete subgraphs is guaranteed by α<1/2, although the transient power-law is permitted at low increase rates of edges. Additionally, the model exhibits a spontaneous emergence of highly clustered structures regardless of its initial structure.

Suggested Citation

  • Ikeda, Nobutoshi, 2010. "Impact of initial lattice structures on networks generated by traces of random walks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(16), pages 3336-3347.
  • Handle: RePEc:eee:phsmap:v:389:y:2010:i:16:p:3336-3347
    DOI: 10.1016/j.physa.2010.03.027
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437110002712
    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.2010.03.027?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. Ikeda, N., 2007. "Network formed by traces of random walks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 379(2), pages 701-713.
    2. Tsonis, A.A. & Roebber, P.J., 2004. "The architecture of the climate network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 333(C), pages 497-504.
    3. Toivonen, Riitta & Onnela, Jukka-Pekka & Saramäki, Jari & Hyvönen, Jörkki & Kaski, Kimmo, 2006. "A model for social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 851-860.
    4. Réka Albert & Hawoong Jeong & Albert-László Barabási, 2000. "Error and attack tolerance of complex networks," Nature, Nature, vol. 406(6794), pages 378-382, July.
    5. M. T. Gastner & M. E.J. Newman, 2006. "The spatial structure of networks," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 49(2), pages 247-252, January.
    6. Aleksiejuk, Agata & Hołyst, Janusz A. & Stauffer, Dietrich, 2002. "Ferromagnetic phase transition in Barabási–Albert networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 310(1), pages 260-266.
    7. Emily M. Jin & Michelle Girvan & M. E. J. Newman, 2001. "The Structure of Growing Social Networks," Working Papers 01-06-032, Santa Fe Institute.
    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. Ikeda, Nobutoshi, 2021. "Stratified structure of fractal scale-free networks generated by local rules," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    2. Ikeda, Nobutoshi, 2019. "Growth model for fractal scale-free networks generated by a random walk," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 521(C), pages 424-434.
    3. Ikeda, Nobutoshi, 2017. "Topology of growing networks accelerated by intermediary process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 484(C), pages 378-393.
    4. Ikeda, Nobutoshi, 2020. "Fractal networks induced by movements of random walkers on a tree graph," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 537(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. Johansson, Tobias, 2017. "Gossip spread in social network Models," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 126-134.
    2. Huang, Chung-Yuan & Tsai, Yu-Shiuan, 2010. "Effects of friend-making resources/costs and remembering on acquaintance networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 389(3), pages 604-622.
    3. Xia, Yongxiang & Liu, Nianjun & Iu, Herbert H.C., 2009. "Oscillation and chaos in a deterministic traffic network," Chaos, Solitons & Fractals, Elsevier, vol. 42(3), pages 1700-1704.
    4. P.B., Divya & Lekha, Divya Sindhu & Johnson, T.P. & Balakrishnan, Kannan, 2022. "Vulnerability of link-weighted complex networks in central attacks and fallback strategy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 590(C).
    5. Ikeda, Nobutoshi, 2015. "Effects of triad formations stimulated by intermediaries on network topology," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 897-908.
    6. Perc, Matjaž, 2010. "Growth and structure of Slovenia’s scientific collaboration network," Journal of Informetrics, Elsevier, vol. 4(4), pages 475-482.
    7. Suhyung Yoo & Hwasoo Yeo, 2016. "Evaluation of the resilience of air transportation network with adaptive capacity," International Journal of Urban Sciences, Taylor & Francis Journals, vol. 20(sup1), pages 38-49, July.
    8. Ikeda, Nobutoshi, 2021. "Stratified structure of fractal scale-free networks generated by local rules," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    9. Guo, Shengmin & Wu, Ruoqian & Tong, Qingfeng & Zeng, Guanwen & Yang, Jian & Chen, Long & Zhu, Tongyu & Lv, Weifeng & Li, Daqing, 2018. "Is city traffic damaged by torrential rain?," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 1073-1080.
    10. Sean Wilkinson & Sarah Dunn & Shu Ma, 2012. "The vulnerability of the European air traffic network to spatial hazards," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 60(3), pages 1027-1036, February.
    11. Nazli Yonca Aydin & H. Sebnem Duzgun & Friedemann Wenzel & Hans Rudolf Heinimann, 2018. "Integration of stress testing with graph theory to assess the resilience of urban road networks under seismic hazards," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 91(1), pages 37-68, March.
    12. Rui Ding & Norsidah Ujang & Hussain Bin Hamid & Mohd Shahrudin Abd Manan & Rong Li & Safwan Subhi Mousa Albadareen & Ashkan Nochian & Jianjun Wu, 2019. "Application of Complex Networks Theory in Urban Traffic Network Researches," Networks and Spatial Economics, Springer, vol. 19(4), pages 1281-1317, December.
    13. Dunn, Sarah & Wilkinson, Sean, 2017. "Hazard tolerance of spatially distributed complex networks," Reliability Engineering and System Safety, Elsevier, vol. 157(C), pages 1-12.
    14. Braha, Dan & Stacey, Blake & Bar-Yam, Yaneer, 2011. "Corporate competition: A self-organized network," MPRA Paper 32142, University Library of Munich, Germany.
    15. Sanjeev Goyal & Fernando Vega-Redondo, 2000. "Learning, Network Formation and Coordination," Econometric Society World Congress 2000 Contributed Papers 0113, Econometric Society.
    16. Quayle, A.P. & Siddiqui, A.S. & Jones, S.J.M., 2006. "Preferential network perturbation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 823-840.
    17. 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.
    18. Xiao‐Bing Hu & Hang Li & XiaoMei Guo & Pieter H. A. J. M. van Gelder & Peijun Shi, 2019. "Spatial Vulnerability of Network Systems under Spatially Local Hazards," Risk Analysis, John Wiley & Sons, vol. 39(1), pages 162-179, January.
    19. Bálint Mészáros & István Simon & Zsuzsanna Dosztányi, 2009. "Prediction of Protein Binding Regions in Disordered Proteins," PLOS Computational Biology, Public Library of Science, vol. 5(5), pages 1-18, May.
    20. Irina Rish & Guillermo Cecchi & Benjamin Thyreau & Bertrand Thirion & Marion Plaze & Marie Laure Paillere-Martinot & Catherine Martelli & Jean-Luc Martinot & Jean-Baptiste Poline, 2013. "Schizophrenia as a Network Disease: Disruption of Emergent Brain Function in Patients with Auditory Hallucinations," PLOS ONE, Public Library of Science, vol. 8(1), pages 1-15, January.

    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:389:y:2010:i:16:p:3336-3347. 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.