Hostname: page-component-669899f699-swprf Total loading time: 0 Render date: 2025-04-29T22:10:06.017Z Has data issue: false hasContentIssue false
  • English
  • Français

Dynamics of information networks

Part of: Mathematical sociology Markov processes

Published online by Cambridge University Press:  30 November 2023

Andrei Sontag Open the ORCID record for Andrei Sontag [Opens in a new window] ,
Tim Rogers  and
Christian A Yates
Andrei Sontag*
Affiliation:
University of Bath
Tim Rogers*
Affiliation:
University of Bath
Christian A Yates*
Affiliation:
University of Bath
*
*Postal address: Department of Mathematical Sciences, University of Bath, Bath, BA27AY, UK.
*Postal address: Department of Mathematical Sciences, University of Bath, Bath, BA27AY, UK.
*Postal address: Department of Mathematical Sciences, University of Bath, Bath, BA27AY, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

We explore a simple model of network dynamics which has previously been applied to the study of information flow in the context of epidemic spreading. A random rooted network is constructed that evolves according to the following rule: at a constant rate, pairs of nodes (i, j) are randomly chosen to interact, with an edge drawn from i to j (and any other out-edge from i deleted) if j is strictly closer to the root with respect to graph distance. We characterise the dynamics of this random network in the limit of large size, showing that it instantaneously forms a tree with long branches that immediately collapse to depth two, then it slowly rearranges itself to a star-like configuration. This curious behaviour has consequences for the study of the epidemic models in which this information network was first proposed.

Keywords

Information spreadrandom recursive treespreferential attachment

MSC classification

Primary: 60J20: Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
Secondary: 91D30: Social networks
Type
Original Article
Information
Journal of Applied Probability , Volume 61 , Issue 3 , September 2024 , pp. 1029 - 1039
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Acemoğlu, D. and Ozdaglar, A. (2010). Opinion dynamics and learning in social networks. Dynamic Games Appl. 1, 3–49.10.1007/s13235-010-0004-1CrossRefGoogle Scholar
Acemoğlu, D., Como, G., Fagnani, F. and Ozdaglar, A. (2013). Opinion fluctuations and disagreement in social networks. Math. Operat. Res. 38, 1–27.10.1287/moor.1120.0570CrossRefGoogle Scholar
Auffinger, A., Damron, M. and Hanson, J. (2017). 50 Years of First-Passage Percolation (Univ. Lect. Ser. 68). American Mathematical Society, Providence, RI.10.1090/ulect/068CrossRefGoogle Scholar
Barabási, A. (2016). Network Science. Cambridge University Press.Google Scholar
Baumgaertner, B. O., Fetros, P. A., Krone, S. M. and Tyson, R. C. (2018). Spatial opinion dynamics and the effects of two types of mixing. Physical Review E 98, 022310.10.1103/PhysRevE.98.022310CrossRefGoogle ScholarPubMed
Brainard, J., Hunter, P. and Hall, I. (2020). An agent-based model about the effects of fake news on a norovirus outbreak. Revue d’Épidémiologie et de Santé Publique 68, 99–107.10.1016/j.respe.2019.12.001CrossRefGoogle ScholarPubMed
Brody, D. C. and Meier, D. M. (2022). Mathematical models for fake news. In Financial Informatics, eds Brody, D., Hughston, L., and Macrina, A.. Scientific, World, Singapore, pp. 405–423.10.1142/9789811246494_0018CrossRefGoogle Scholar
Castellano, C., Fortunato, S. and Loreto, V. (2009). Statistical physics of social dynamics. Rev. Mod. Phys. 81, 591–646.10.1103/RevModPhys.81.591CrossRefGoogle Scholar
Cisneros-Velarde, P., Oliveira, D. F. M. and Chan, K. S. (2019). Spread and control of misinformation with heterogeneous agents. In Complex Networks X, eds Cornelius, S. P., Granell Martorell, C., Gómez-Gardeñes, J., and Gonçalves, B.. Springer, Cham, pp. 75–83.10.1007/978-3-030-14459-3_6CrossRefGoogle Scholar
Davis, J. T. et al. (2020). Phase transitions in information spreading on structured populations. Nature Phys. 16, 590–596.10.1038/s41567-020-0810-3CrossRefGoogle Scholar
Durrett, R. (2006). Random Graph Dynamics. Cambridge University Press.10.1017/CBO9780511546594CrossRefGoogle Scholar
Funk, S., Gilad, E. and Jansen, V. (2010). Endemic disease, awareness, and local behavioural response. J. Theoret. Biol. 264, 501–509.10.1016/j.jtbi.2010.02.032CrossRefGoogle ScholarPubMed
Funk, S., Gilad, E., Watkins, C. and Jansen, V. A. A. (2009). The spread of awareness and its impact on epidemic outbreaks. Proc. Nat. Acad. Sci. 106, 6872–6877.10.1073/pnas.0810762106CrossRefGoogle Scholar
Halbach, P. et al. (2020). Investigating key factors for social network evolution and opinion dynamics in an agent-based simulation. In Digital Human Modeling and Applications in Health, Safety, Ergonomics and Risk Management. Human Communication, Organization and Work, ed Duffy, V. G.. Springer, Cham, pp. 20–39.10.1007/978-3-030-49907-5_2CrossRefGoogle Scholar
Juher, D., Kiss, I. Z. and Saldaña, J. (2015). Analysis of an epidemic model with awareness decay on regular random networks. J. Theoret. Biol. 365, 457–468.10.1016/j.jtbi.2014.10.013CrossRefGoogle ScholarPubMed
Kiss, I. Z., Cassell, J., Recker, M. and Simon, P. L. (2010). The impact of information transmission on epidemic outbreaks. Math. Biosci. 225, 1–10.10.1016/j.mbs.2009.11.009CrossRefGoogle ScholarPubMed
Lyon, M. R. and Mahmoud, H. M. (2020). Trees grown under young-age preferential attachment. J. Appl. Prob. 57, 911–927.10.1017/jpr.2020.49CrossRefGoogle Scholar
Mahmoud, H. M., Smythe, R. T. and Szymański, J. (1993). On the structure of random plane-oriented recursive trees and their branches. Random Structures Algorithms 4, 151–176.10.1002/rsa.3240040204CrossRefGoogle Scholar
Murayama, T., Wakamiya, S., Aramaki, E. and Kobayashi, R. (2021). Modeling the spread of fake news on twitter. PLoS ONE 16, e0250419.10.1371/journal.pone.0250419CrossRefGoogle ScholarPubMed
Pittel, B. (1994). Note on the heights of random recursive trees and random m-ary search trees. Random Structures Algorithms 5, 337–347.10.1002/rsa.3240050207CrossRefGoogle Scholar
Ross, B. et al. (2019). Are social bots a real threat? An agent-based model of the spiral of silence to analyse the impact of manipulative actors in social networks. Europ. J. Inf. Sys. 28, 394–412.10.1080/0960085X.2018.1560920CrossRefGoogle Scholar
Sontag, A., Rogers, T. and Yates, C. A. (2023). Stochastic drift in discrete waves of nonlocally interacting particles. Phys. Rev. E 107, 014128.10.1103/PhysRevE.107.014128CrossRefGoogle ScholarPubMed
Stockmaier, S. et al. (2021). Infectious diseases and social distancing in nature. Science 371, eabc8881.10.1126/science.abc8881CrossRefGoogle Scholar
Tambuscio, M., Oliveira, D. F. M., Ciampaglia, G. L. and Ruffo, G. (2018). Network segregation in a model of misinformation and fact-checking. J. Comp. Social Sci. 1, 261–275.10.1007/s42001-018-0018-9CrossRefGoogle Scholar
Tambuscio, M. and Ruffo, G. (2019). Fact-checking strategies to limit urban legends spreading in a segregated society. Appl. Network Sci. 4, 116.10.1007/s41109-019-0233-1CrossRefGoogle Scholar
Tambuscio, M., Ruffo, G., Flammini, A. and Menczer, F. (2015). Fact-checking effect on viral hoaxes. In Proc. 24th Int. Conf. World Wide Web. ACM, New York.10.1145/2740908.2742572CrossRefGoogle Scholar
Törnberg, P. (2018). Echo chambers and viral misinformation: Modeling fake news as complex contagion. PLoS ONE 13, e0203958.10.1371/journal.pone.0203958CrossRefGoogle Scholar
Vazquez, F., Krapivsky, P. L. and Redner, S. (2003). Constrained opinion dynamics: Freezing and slow evolution. J. Phys. A 36, L61–L68.10.1088/0305-4470/36/3/103CrossRefGoogle Scholar
Xie, J. et al. (2021). Detecting and modelling real percolation and phase transitions of information on social media. Nat. Hum. Behav. 5, 1161–1168.10.1038/s41562-021-01090-zCrossRefGoogle ScholarPubMed