IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0241394.html
   My bibliography  Save this article

Efficient simulation of non-Markovian dynamics on complex networks

Author

Listed:
  • Gerrit Großmann
  • Luca Bortolussi
  • Verena Wolf

Abstract

We study continuous-time multi-agent models, where agents interact according to a network topology. At any point in time, each agent occupies a specific local node state. Agents change their state at random through interactions with neighboring agents. The time until a transition happens can follow an arbitrary probability density. Stochastic (Monte-Carlo) simulations are often the preferred—sometimes the only feasible—approach to study the complex emerging dynamical patterns of such systems. However, each simulation run comes with high computational costs mostly due to updating the instantaneous rates of interconnected agents after each transition. This work proposes a stochastic rejection-based, event-driven simulation algorithm that scales extremely well with the size and connectivity of the underlying contact network and produces statistically correct samples. We demonstrate the effectiveness of our method on different information spreading models.

Suggested Citation

  • Gerrit Großmann & Luca Bortolussi & Verena Wolf, 2020. "Efficient simulation of non-Markovian dynamics on complex networks," PLOS ONE, Public Library of Science, vol. 15(10), pages 1-18, October.
    • Handle: RePEc:plo:pone00:0241394
    DOI: 10.1371/journal.pone.0241394
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0241394
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0241394&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0241394?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
    ---><---

    References listed on IDEAS

    as
    1. Dassios, Angelos & Zhao, Hongbiao, 2013. "Exact simulation of Hawkes process with exponentially decaying intensity," LSE Research Online Documents on Economics 51370, London School of Economics and Political Science, LSE Library.
    2. Marc Benayoun & Jack D Cowan & Wim van Drongelen & Edward Wallace, 2010. "Avalanches in a Stochastic Model of Spiking Neurons," PLOS Computational Biology, Public Library of Science, vol. 6(7), pages 1-13, July.
    3. Zhao, Laijun & Wang, Jiajia & Chen, Yucheng & Wang, Qin & Cheng, Jingjing & Cui, Hongxin, 2012. "SIHR rumor spreading model in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(7), pages 2444-2453.
    4. Albert-László Barabási, 2005. "The origin of bursts and heavy tails in human dynamics," Nature, Nature, vol. 435(7039), pages 207-211, May.
    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. Li, Dandan & Ma, Jing, 2017. "How the government’s punishment and individual’s sensitivity affect the rumor spreading in online social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 284-292.
    2. Xue Yang & Zhiliang Zhu & Hai Yu & Yuli Zhao & Li Guo, 2019. "Evolutionary Game Dynamics of the Competitive Information Propagation on Social Networks," Complexity, Hindawi, vol. 2019, pages 1-11, December.
    3. Hosni, Adil Imad Eddine & Li, Kan & Ahmad, Sadique, 2020. "Analysis of the impact of online social networks addiction on the propagation of rumors," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 542(C).
    4. Anzhi Sheng & Qi Su & Aming Li & Long Wang & Joshua B. Plotkin, 2023. "Constructing temporal networks with bursty activity patterns," Nature Communications, Nature, vol. 14(1), pages 1-10, December.
    5. He, Yifan & Zhao, Chen & Zeng, An, 2022. "Ranking locations in a city via the collective home-work relations in human mobility data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    6. Lu, Xi & Mo, Hongming & Deng, Yong, 2015. "An evidential opinion dynamics model based on heterogeneous social influential power," Chaos, Solitons & Fractals, Elsevier, vol. 73(C), pages 98-107.
    7. Jia, Pingqi & Wang, Chao & Zhang, Gaoyu & Ma, Jianfeng, 2019. "A rumor spreading model based on two propagation channels in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 524(C), pages 342-353.
    8. Wang, Cheng-Jun & Wu, Lingfei, 2016. "The scaling of attention networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 448(C), pages 196-204.
    9. Zan, Yongli & Wu, Jianliang & Li, Ping & Yu, Qinglin, 2014. "SICR rumor spreading model in complex networks: Counterattack and self-resistance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 159-170.
    10. Simon DeDeo, 2016. "Conflict and Computation on Wikipedia: A Finite-State Machine Analysis of Editor Interactions," Future Internet, MDPI, vol. 8(3), pages 1-23, July.
    11. Ouyang, Bo & Teng, Zhaosheng & Tang, Qiu, 2016. "Dynamics in local influence cascading models," Chaos, Solitons & Fractals, Elsevier, vol. 93(C), pages 182-186.
    12. Zhao, Laijun & Qiu, Xiaoyan & Wang, Xiaoli & Wang, Jiajia, 2013. "Rumor spreading model considering forgetting and remembering mechanisms in inhomogeneous networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(4), pages 987-994.
    13. Jianhong Chen & Hongcai Ma & Shan Yang, 2023. "SEIOR Rumor Propagation Model Considering Hesitating Mechanism and Different Rumor-Refuting Ways in Complex Networks," Mathematics, MDPI, vol. 11(2), pages 1-22, January.
    14. Lu, Peng, 2019. "Heterogeneity, judgment, and social trust of agents in rumor spreading," Applied Mathematics and Computation, Elsevier, vol. 350(C), pages 447-461.
    15. Jing Yang & Yingwu Chen, 2011. "Fast Computing Betweenness Centrality with Virtual Nodes on Large Sparse Networks," PLOS ONE, Public Library of Science, vol. 6(7), pages 1-5, July.
    16. Cavaliere, Giuseppe & Lu, Ye & Rahbek, Anders & Stærk-Østergaard, Jacob, 2023. "Bootstrap inference for Hawkes and general point processes," Journal of Econometrics, Elsevier, vol. 235(1), pages 133-165.
    17. Yao, Yao & Xiao, Xi & Zhang, Chengping & Dou, Changsheng & Xia, Shutao, 2019. "Stability analysis of an SDILR model based on rumor recurrence on social media," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 535(C).
    18. Baltakys, Kęstutis & Kanniainen, Juho & Saramäki, Jari & Kivelä, Mikko, 2023. "Investor trade allocation patterns in stock markets," Journal of Economic Behavior & Organization, Elsevier, vol. 210(C), pages 191-209.
    19. Jinxian Li & Yanping Hu & Zhen Jin, 2019. "Rumor Spreading of an SIHR Model in Heterogeneous Networks Based on Probability Generating Function," Complexity, Hindawi, vol. 2019, pages 1-15, June.
    20. Diao, Su-Meng & Liu, Yun & Zeng, Qing-An & Luo, Gui-Xun & Xiong, Fei, 2014. "A novel opinion dynamics model based on expanded observation ranges and individuals’ social influences in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 415(C), pages 220-228.

    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:plo:pone00:0241394. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.