اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTemporal Gillespie algorithm: Fast simulation of contagion processes on time-varying networks
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Stochastic simulations are one of the cornerstones of the analysis of dynamical processes on complex networks, and are often the only accessible way to explore their behavior. The development of fast algorithms is paramount to allow large-scale simulations. The Gillespie algorithm can be used for fast simulation of stochastic processes, and variants of it have been applied to simulate dynamical processes on static networks. However, its adaptation to temporal networks remains non-trivial. We here present a temporal Gillespie algorithm that solves this problem. Our method is applicable to general Poisson (constant-rate) processes on temporal networks, stochastically exact, and up to multiple orders of magnitude faster than traditional simulation schemes based on rejection sampling. We also show how it can be extended to simulate non-Markovian processes. The algorithm is easily applicable in practice, and as an illustration we detail how to simulate both Poissonian and non-Markovian models of epidemic spreading. Namely, we provide pseudocode and its implementation in C++ for simulating the paradigmatic Susceptible-Infected-Susceptible and Susceptible-Infected-Recovered models and a Susceptible-Infected-Recovered model with non-constant recovery rates. For empirical networks, the temporal Gillespie algorithm is here typically from 10 to 100 times faster than rejection sampling.
قيم البحث
اقرأ أيضاً
The vast majority of strategies aimed at controlling contagion processes on networks considers the connectivity pattern of the system as either quenched or annealed. However, in the real world many networks are highly dynamical and evolve in time con
currently to the contagion process. Here, we derive an analytical framework for the study of control strategies specifically devised for time-varying networks. We consider the removal/immunization of individual nodes according the their activity in the network and develop a block variable mean-field approach that allows the derivation of the equations describing the evolution of the contagion process concurrently to the network dynamic. We derive the critical immunization threshold and assess the effectiveness of the control strategies. Finally, we validate the theoretical picture by simulating numerically the information spreading process and control strategies in both synthetic networks and a large-scale, real-world mobile telephone call dataset
We provide a description of the Epidemics on Networks (EoN) python package designed for studying disease spread in static networks. The package consists of over $100$ methods available for users to perform stochastic simulation of a range of differen
t processes including SIS and SIR disease, and generic simple or comlex contagions.
The metapopulation framework is adopted in a wide array of disciplines to describe systems of well separated yet connected subpopulations. The subgroups or patches are often represented as nodes in a network whose links represent the migration routes
among them. The connections have been so far mostly considered as static, but in general evolve in time. Here we address this case by investigating simple contagion processes on time-varying metapopulation networks. We focus on the SIR process and determine analytically the mobility threshold for the onset of an epidemic spreading in the framework of activity-driven network models. We find profound differences from the case of static networks. The threshold is entirely described by the dynamical parameters defining the average number of instantaneously migrating individuals and does not depend on the properties of the static network representation. Remarkably, the diffusion and contagion processes are slower in time-varying graphs than in their aggregated static counterparts, the mobility threshold being even two orders of magnitude larger in the first case. The presented results confirm the importance of considering the time-varying nature of complex networks.
Stochastic processes can model many emerging phenomena on networks, like the spread of computer viruses, rumors, or infectious diseases. Understanding the dynamics of such stochastic spreading processes is therefore of fundamental interest. In this w
ork we consider the wide-spread compartment model where each node is in one of several states (or compartments). Nodes change their state randomly after an exponentially distributed waiting time and according to a given set of rules. For networks of realistic size, even the generation of only a single stochastic trajectory of a spreading process is computationally very expensive. Here, we propose a novel simulation approach, which combines the advantages of event-based simulation and rejection sampling. Our method outperforms state-of-the-art methods in terms of absolute run-time and scales significantly better, while being statistically equivalent.
This paper mainly discusses the diffusion on complex networks with time-varying couplings. We propose a model to describe the adaptive diffusion process of local topological and dynamical information, and find that the Barabasi-Albert scale-free netw
ork (BA network) is beneficial to the diffusion and leads nodes to arrive at a larger state value than other networks do. The ability of diffusion for a node is related to its own degree. Specifically, nodes with smaller degrees are more likely to change their states and reach larger values, while those with larger degrees tend to stick to their original states. We introduce state entropy to analyze the thermodynamic mechanism of the diffusion process, and interestingly find that this kind of diffusion process is a minimization process of state entropy. We use the inequality constrained optimization method to reveal the restriction function of the minimization and find that it has the same form as the Gibbs free energy. The thermodynamical concept allows us to understand dynamical processes on complex networks from a brand-new perspective. The result provides a convenient means of optimizing relevant dynamical processes on practical circuits as well as related complex systems.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
