Dataset Information

Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm.

ABSTRACT: Efficient stochastic simulation algorithms are of paramount importance to the study of spreading phenomena on complex networks. Using insights and analytical results from network science, we discuss how the structure of contacts affects the efficiency of current algorithms. We show that algorithms believed to require O(log N) or even O(1) operations per update-where N is the number of nodes-display instead a polynomial scaling for networks that are either dense or sparse and heterogeneous. This significantly affects the required computation time for simulations on large networks. To circumvent the issue, we propose a node-based method combined with a composition and rejection algorithm, a sampling scheme that has an average-case complexity of O[log(log N)] per update for general networks. This systematic approach is first set-up for Markovian dynamics, but can also be adapted to a number of non-Markovian processes and can enhance considerably the study of a wide range of dynamics on networks.

SUBMITTER: St-Onge G

PROVIDER: S-EPMC6839824 | biostudies-literature | 2019 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm.

St-Onge Guillaume G Young Jean-Gabriel JG Hébert-Dufresne Laurent L Dubé Louis J LJ

Computer physics communications 20190219

Efficient stochastic simulation algorithms are of paramount importance to the study of spreading phenomena on complex networks. Using insights and analytical results from network science, we discuss how the structure of contacts affects the efficiency of current algorithms. We show that algorithms believed to require O(log N) or even O(1) operations per update-where <i>N</i> is the number of nodes-display instead a polynomial scaling for networks that are either dense or sparse and heterogeneous ...[more]

PMID: 31708586

Similar Datasets

Project description:We propose a theoretical framework for the study of spreading processes in structured metapopulations, with heterogeneous agents, subjected to different recurrent mobility patterns. We propose to represent the heterogeneity in the composition of the metapopulations as layers in a multiplex network, where nodes would correspond to geographical areas and layers account for the mobility patterns of agents of the same class. We analyze classical epidemic models within this framework and obtain an excellent agreement with extensive Monte Carlo simulations. This agreement allows us to derive analytical expressions of the epidemic threshold and to face the challenge of characterizing a real multiplex metapopulation, the city of Medellín in Colombia, where different recurrent mobility patterns are observed depending on the socioeconomic class of the agents. Our framework allows us to unveil the geographical location of those patches that trigger the epidemic state at the critical point. A careful exploration reveals that social mixing between classes and mobility crucially determines these critical patches and, more importantly, it can produce abrupt changes of the critical properties of the epidemic onset. Summary The spread of disease is strongly driven by how humans move and segregate across cities, regions, and countries. Understanding how epidemics arise from the interplay of these behaviors is crucial for implementing efficient containment and prevention policies. In this work, we propose a theoretical framework for the spread of pathogens that incorporates the real patterns of mobility, demographics, and human diversity observed in urban environments. Our framework represents various populations in a community as layers in a multiplex network, where nodes correspond to geographical areas and layers account for movement patterns. With this framework, we analyze a real urban system, the city of Medellin in Colombia, considering the interplay between six socioeconomic classes displaying disparate demographic segregation and mobility habits. Our framework can identify those neighborhoods and classes that trigger epidemic outbreaks. Remarkably, we observe that small changes to both mobility and social mixing among these subpopulations can trigger abrupt changes. As a consequence, containment strategies targeting a certain neighborhood can quickly change from efficient to useless. Finally, we provide a physical interpretation of the abrupt changes of those patches driving the unfolding of epidemics based on the effective number of contacts of agents. Our framework provides a reliable, time-saving platform for analyzing the spread of pathogens among various populations, allowing researchers to identify areas critical to the unfolding of diseases. With further improvements, our formalism could be extended to accommodate more sophisticated commuting patterns and epidemic models.

Dataset Information

Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm.

Publications

Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure