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. 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).
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Ouyang, Bo & Teng, Zhaosheng & Tang, Qiu, 2016. "Dynamics in local influence cascading models," Chaos, Solitons & Fractals, Elsevier, vol. 93(C), pages 182-186.
    7. 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.
    8. 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.
    9. Zhou, Bin & Xie, Jia-Rong & Yan, Xiao-Yong & Wang, Nianxin & Wang, Bing-Hong, 2017. "A model of task-deletion mechanism based on the priority queueing system of Barabási," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 466(C), pages 415-421.
    10. Chen, Ning & Zhu, Xuzhen & Chen, Yanyan, 2019. "Information spreading on complex networks with general group distribution," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 671-676.
    11. Zhenpeng Li & Xijin Tang & Zhenjie Hong, 2022. "Collective attention dynamic induced by novelty decay," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 95(8), pages 1-11, August.
    12. Huo, Liang’an & Jiang, Jiehui & Gong, Sixing & He, Bing, 2016. "Dynamical behavior of a rumor transmission model with Holling-type II functional response in emergency event," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 450(C), pages 228-240.
    13. Keshri, Ajit Kumar & Mishra, Bimal Kumar & Rukhaiyar, Bansidhar Prasad, 2020. "When rumors create chaos in e-commerce," Chaos, Solitons & Fractals, Elsevier, vol. 131(C).
    14. Nizamani, Sarwat & Memon, Nasrullah & Galam, Serge, 2014. "From public outrage to the burst of public violence: An epidemic-like model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 416(C), pages 620-630.
    15. Koen Zwet & Ana I. Barros & Tom M. Engers & Peter M. A. Sloot, 2022. "Emergence of protests during the COVID-19 pandemic: quantitative models to explore the contributions of societal conditions," Palgrave Communications, Palgrave Macmillan, vol. 9(1), pages 1-11, December.
    16. Cui, Zhenyu & Kirkby, J. Lars & Nguyen, Duy, 2021. "Efficient simulation of generalized SABR and stochastic local volatility models based on Markov chain approximations," European Journal of Operational Research, Elsevier, vol. 290(3), pages 1046-1062.
    17. Qianqian Liu & Qun Wang, 2017. "A comparative study on uncooperative search models in survivor search and rescue," 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. 89(2), pages 843-857, November.
    18. Kota Yamada & Atsunori Kanemura, 2020. "Simulating bout-and-pause patterns with reinforcement learning," PLOS ONE, Public Library of Science, vol. 15(11), pages 1-21, November.
    19. Muaz Niazi & Amir Hussain, 2011. "Agent-based computing from multi-agent systems to agent-based models: a visual survey," Scientometrics, Springer;Akadémiai Kiadó, vol. 89(2), pages 479-499, November.
    20. Bent Flyvbjerg & Alexander Budzier & Daniel Lunn, 2021. "Regression to the tail: Why the Olympics blow up," Environment and Planning A, , vol. 53(2), pages 233-260, March.

    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.