1
|
Badie-Modiri A, Rizi AK, Karsai M, Kivelä M. Directed percolation in random temporal network models with heterogeneities. Phys Rev E 2022; 105:054313. [PMID: 35706217 DOI: 10.1103/physreve.105.054313] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/18/2021] [Accepted: 04/07/2022] [Indexed: 06/15/2023]
Abstract
The event graph representation of temporal networks suggests that the connectivity of temporal structures can be mapped to a directed percolation problem. However, similarly to percolation theory on static networks, this mapping is valid under the approximation that the structure and interaction dynamics of the temporal network are determined by its local properties, and, otherwise, it is maximally random. We challenge these conditions and demonstrate the robustness of this mapping in case of more complicated systems. We systematically analyze random and regular network topologies and heterogeneous link-activation processes driven by bursty renewal or self-exciting processes using numerical simulation and finite-size scaling methods. We find that the critical percolation exponents characterizing the temporal network are not sensitive to many structural and dynamical network heterogeneities, while they recover known scaling exponents characterizing directed percolation on low-dimensional lattices. While it is not possible to demonstrate the validity of this mapping for all temporal network models, our results establish the first batch of evidence supporting the robustness of the scaling relationships in the limited-time reachability of temporal networks.
Collapse
Affiliation(s)
- Arash Badie-Modiri
- Department of Computer Science, School of Science, Aalto University, FI-0007, Finland
| | - Abbas K Rizi
- Department of Computer Science, School of Science, Aalto University, FI-0007, Finland
| | - Márton Karsai
- Department of Network and Data Science Central European University, 1100 Vienna, Austria
- Alfréd Rényi Institute of Mathematics, 1053 Budapest, Hungary
| | - Mikko Kivelä
- Department of Computer Science, School of Science, Aalto University, FI-0007, Finland
| |
Collapse
|
2
|
Williams OE, Mazzarisi P, Lillo F, Latora V. Non-Markovian temporal networks with auto- and cross-correlated link dynamics. Phys Rev E 2022; 105:034301. [PMID: 35428139 DOI: 10.1103/physreve.105.034301] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/18/2021] [Accepted: 02/03/2022] [Indexed: 06/14/2023]
Abstract
Many of the biological, social and man-made networks around us are inherently dynamic, with their links switching on and off over time. The evolution of these networks is often observed to be non-Markovian, and the dynamics of their links are often correlated. Hence, to accurately model these networks, predict their evolution, and understand how information and other relevant quantities propagate over them, the inclusion of both memory and dynamical dependencies between links is key. In this article we introduce a general class of models of temporal networks based on discrete autoregressive processes for link dynamics. As a concrete and useful case study, we then concentrate on a specific model within this class, which allows to generate temporal networks with a specified underlying structural backbone, and with precise control over the dynamical dependencies between links and the strength and length of their memories. In this network model the presence of each link is influenced not only by its past activity, but also by the past activities of other links, as specified by a coupling matrix, which directly controls the causal relations, and hence the correlations, among links. We propose a maximum likelihood method for estimating the model's parameters from data, showing how the model allows a more realistic description of real-world temporal networks and also to predict their evolution. Due to the flexibility of maximum likelihood inference, we illustrate how to deal with heterogeneity and time-varying patterns, possibly including also nonstationary network dynamics. We then use our network model to investigate the role that, both the features of memory and the type of correlations in the dynamics of links have on the properties of processes occurring over a temporal network. Namely, we study the speed of a spreading process, as measured by the time it takes for diffusion to reach equilibrium. Through both numerical simulations and analytical results, we are able to separate the roles of autocorrelations and neighborhood correlations in link dynamics, showing that not only is the speed of diffusion nonmonotonically dependent on the memory length, but also that correlations among neighboring links help to speed up the spreading process, while autocorrelations slow it back down. Our results have implications in the study of opinion formation, the modeling of social networks, and the spreading of epidemics through mobile populations.
Collapse
Affiliation(s)
- Oliver E Williams
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
| | - Piero Mazzarisi
- Scuola Normale Superiore, Piazza dei Cavalieri, 7, 56126 Pisa, Italy
| | - Fabrizio Lillo
- Scuola Normale Superiore, Piazza dei Cavalieri, 7, 56126 Pisa, Italy
- Department of Mathematics, University of Bologna, Piazza di Porta San Donato 5, 40126 Bologna, Italy
| | - Vito Latora
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
- Dipartimento di Fisica ed Astronomia, Università di Catania and INFN, I-95123 Catania, Italy
- Complexity Science Hub Vienna (CSHV), A-1080 Vienna, Austria
| |
Collapse
|
3
|
Abstract
How to best define, detect and characterize network memory, i.e. the dependence of a network’s structure on its past, is currently a matter of debate. Here we show that the memory of a temporal network is inherently multidimensional, and we introduce a mathematical framework for defining and efficiently estimating the microscopic shape of memory, which characterises how the activity of each link intertwines with the activities of all other links. We validate our methodology on a range of synthetic models, and we then study the memory shape of real-world temporal networks spanning social, technological and biological systems, finding that these networks display heterogeneous memory shapes. In particular, online and offline social networks are markedly different, with the latter showing richer memory and memory scales. Our theory also elucidates the phenomenon of emergent virtual loops and provides a novel methodology for exploring the dynamically rich structure of complex systems. The evolution of networks with structure changing in time is dependent on their past states and relevant to diffusion and spreading processes. The authors show that temporal network’s memory is described by multidimensional patterns at a microscopic scale, and cannot be reduced to a scalar quantity.
Collapse
|
4
|
Unicomb S, Iñiguez G, Gleeson JP, Karsai M. Dynamics of cascades on burstiness-controlled temporal networks. Nat Commun 2021; 12:133. [PMID: 33420016 PMCID: PMC7794342 DOI: 10.1038/s41467-020-20398-4] [Citation(s) in RCA: 8] [Impact Index Per Article: 2.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/31/2020] [Accepted: 12/01/2020] [Indexed: 11/16/2022] Open
Abstract
Burstiness, the tendency of interaction events to be heterogeneously distributed in time, is critical to information diffusion in physical and social systems. However, an analytical framework capturing the effect of burstiness on generic dynamics is lacking. Here we develop a master equation formalism to study cascades on temporal networks with burstiness modelled by renewal processes. Supported by numerical and data-driven simulations, we describe the interplay between heterogeneous temporal interactions and models of threshold-driven and epidemic spreading. We find that increasing interevent time variance can both accelerate and decelerate spreading for threshold models, but can only decelerate epidemic spreading. When accounting for the skewness of different interevent time distributions, spreading times collapse onto a universal curve. Our framework uncovers a deep yet subtle connection between generic diffusion mechanisms and underlying temporal network structures that impacts a broad class of networked phenomena, from spin interactions to epidemic contagion and language dynamics.
Collapse
Affiliation(s)
- Samuel Unicomb
- Université de Lyon, ENS de Lyon, INRIA, CNRS, UMR 5668, IXXI, Lyon, 69364, France.
| | - Gerardo Iñiguez
- Department of Network and Data Science, Central European University, Vienna, A-1100, Austria
- Department of Computer Science, Aalto University School of Science, Aalto, FI-00076, Finland
- Centro de Ciencias de la Complejidad, Universidad Nacional Autonóma de México, CDMX, 04510, Mexico
| | - James P Gleeson
- MACSI and Insight Centre for Data Analytics, University of Limerick, Limerick, V94 T9PX, Ireland
| | - Márton Karsai
- Université de Lyon, ENS de Lyon, INRIA, CNRS, UMR 5668, IXXI, Lyon, 69364, France.
- Department of Network and Data Science, Central European University, Vienna, A-1100, Austria.
| |
Collapse
|
5
|
Hirata Y. Topological epidemic model: Theoretical insight into underlying networks. CHAOS (WOODBURY, N.Y.) 2020; 30:101103. [PMID: 33138460 DOI: 10.1063/5.0023796] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/01/2020] [Accepted: 10/05/2020] [Indexed: 06/11/2023]
Abstract
Although there are various models of epidemic diseases, there are a few individual-based models that can guide susceptible individuals on how they should behave in a pandemic without its appropriate treatment. Such a model would be ideal for the current coronavirus disease 2019 (COVID-19) pandemic. Thus, here, we propose a topological model of an epidemic disease, which can take into account various types of interventions through a time-dependent contact network. Based on this model, we show that there is a maximum allowed number of persons one can see each day for each person so that we can suppress the epidemic spread. Reducing the number of persons to see for the hub persons is a key countermeasure for the current COVID-19 pandemic.
Collapse
Affiliation(s)
- Yoshito Hirata
- Faculty of Engineering, Information and Systems, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
| |
Collapse
|
6
|
Jo HH, Hiraoka T, Kivelä M. Burst-tree decomposition of time series reveals the structure of temporal correlations. Sci Rep 2020; 10:12202. [PMID: 32699282 PMCID: PMC7376115 DOI: 10.1038/s41598-020-68157-1] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/25/2019] [Accepted: 06/19/2020] [Indexed: 11/13/2022] Open
Abstract
Comprehensive characterization of non-Poissonian, bursty temporal patterns observed in various natural and social processes is crucial for understanding the underlying mechanisms behind such temporal patterns. Among them bursty event sequences have been studied mostly in terms of interevent times (IETs), while the higher-order correlation structure between IETs has gained very little attention due to the lack of a proper characterization method. In this paper we propose a method of representing an event sequence by a burst tree, which is then decomposed into a set of IETs and an ordinal burst tree. The ordinal burst tree exactly captures the structure of temporal correlations that is entirely missing in the analysis of IET distributions. We apply this burst-tree decomposition method to various datasets and analyze the structure of the revealed burst trees. In particular, we observe that event sequences show similar burst-tree structure, such as heavy-tailed burst-size distributions, despite of very different IET distributions. This clearly shows that the IET distributions and the burst-tree structures can be separable. The burst trees allow us to directly characterize the preferential and assortative mixing structure of bursts responsible for the higher-order temporal correlations. We also show how to use the decomposition method for the systematic investigation of such correlations captured by the burst trees in the framework of randomized reference models. Finally, we devise a simple kernel-based model for generating event sequences showing appropriate higher-order temporal correlations. Our method is a tool to make the otherwise overwhelming analysis of higher-order correlations in bursty time series tractable by turning it into the analysis of a tree structure.
Collapse
Affiliation(s)
- Hang-Hyun Jo
- Department of Physics, The Catholic University of Korea, Bucheon, 14662, Republic of Korea. .,Asia Pacific Center for Theoretical Physics, Pohang, 37673, Republic of Korea.
| | - Takayuki Hiraoka
- Department of Computer Science, Aalto University, Espoo, 00076, Finland.,Asia Pacific Center for Theoretical Physics, Pohang, 37673, Republic of Korea
| | - Mikko Kivelä
- Department of Computer Science, Aalto University, Espoo, 00076, Finland
| |
Collapse
|
7
|
Lee E, Emmons S, Gibson R, Moody J, Mucha PJ. Concurrency and reachability in treelike temporal networks. Phys Rev E 2019; 100:062305. [PMID: 31962508 PMCID: PMC6989038 DOI: 10.1103/physreve.100.062305] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/25/2019] [Indexed: 04/12/2023]
Abstract
Network properties govern the rate and extent of various spreading processes, from simple contagions to complex cascades. Recently, the analysis of spreading processes has been extended from static networks to temporal networks, where nodes and links appear and disappear. We focus on the effects of accessibility, whether there is a temporally consistent path from one node to another, and reachability, the density of the corresponding accessibility graph representation of the temporal network. The level of reachability thus inherently limits the possible extent of any spreading process on the temporal network. We study reachability in terms of the overall levels of temporal concurrency between edges and the structural cohesion of the network agglomerating over all edges. We use simulation results and develop heterogeneous mean-field model predictions for random networks to better quantify how the properties of the underlying temporal network regulate reachability.
Collapse
Affiliation(s)
- Eun Lee
- Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599, USA
| | - Scott Emmons
- Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599, USA
| | - Ryan Gibson
- Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599, USA
| | - James Moody
- Duke Network Analysis Center and Department of Sociology, Duke University, Durham, North Carolina 27708, USA
| | - Peter J Mucha
- Carolina Center for Interdisciplinary Applied Mathematics, Department of Mathematics, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599, USA
- Department of Applied Physical Sciences, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599, USA
| |
Collapse
|
8
|
Jo HH, Lee BH, Hiraoka T, Jung WS. Copula-based algorithm for generating bursty time series. Phys Rev E 2019; 100:022307. [PMID: 31574731 DOI: 10.1103/physreve.100.022307] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/18/2019] [Indexed: 11/07/2022]
Abstract
Dynamical processes in various natural and social phenomena have been described by a series of events or event sequences showing non-Poissonian, bursty temporal patterns. Temporal correlations in such bursty time series can be understood not only by heterogeneous interevent times (IETs) but also by correlations between IETs. Modeling and simulating various dynamical processes requires us to generate event sequences with a heavy-tailed IET distribution and memory effects between IETs. For this, we propose a Farlie-Gumbel-Morgenstern copula-based algorithm for generating event sequences with correlated IETs when the IET distribution and the memory coefficient between two consecutive IETs are given. We successfully apply our algorithm to the cases with heavy-tailed IET distributions. We also compare our algorithm to the existing shuffling method to find that our algorithm outperforms the shuffling method for some cases. Our copula-based algorithm is expected to be used for more realistic modeling of various dynamical processes.
Collapse
Affiliation(s)
- Hang-Hyun Jo
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea.,Department of Physics, Pohang University of Science and Technology, Pohang 37673, Republic of Korea.,Department of Computer Science, Aalto University, Espoo FI-00076, Finland
| | - Byoung-Hwa Lee
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea.,Department of Physics, Pohang University of Science and Technology, Pohang 37673, Republic of Korea
| | - Takayuki Hiraoka
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea
| | - Woo-Sung Jung
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea.,Department of Physics, Pohang University of Science and Technology, Pohang 37673, Republic of Korea.,Department of Industrial and Management Engineering, Pohang University of Science and Technology, Pohang 37673, Republic of Korea
| |
Collapse
|
9
|
Jo HH. Analytically solvable autocorrelation function for weakly correlated interevent times. Phys Rev E 2019; 100:012306. [PMID: 31499919 DOI: 10.1103/physreve.100.012306] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/03/2019] [Indexed: 11/07/2022]
Abstract
Long-term temporal correlations observed in event sequences of natural and social phenomena have been characterized by algebraically decaying autocorrelation functions. Such temporal correlations can be understood not only by heterogeneous interevent times (IETs) but also by correlations between IETs. In contrast to the role of heterogeneous IETs on the autocorrelation function, little is known about the effects due to the correlations between IETs. To rigorously study these effects, we derive an analytical form of the autocorrelation function for the arbitrary IET distribution in the case with weakly correlated IETs, where the Farlie-Gumbel-Morgenstern copula is adopted for modeling the joint probability distribution function of two consecutive IETs. Our analytical results are confirmed by numerical simulations for exponential and power-law IET distributions. For the power-law case, we find a tendency of the steeper decay of the autocorrelation function for the stronger correlation between IETs. Our analytical approach enables us to better understand long-term temporal correlations induced by the correlations between IETs.
Collapse
Affiliation(s)
- Hang-Hyun Jo
- Asia Pacific Center for Theoretical Physics, Pohang 37673, Republic of Korea; Department of Physics, Pohang University of Science and Technology, Pohang 37673, Republic of Korea; and Department of Computer Science, Aalto University, Espoo FI-00076, Finland
| |
Collapse
|