1
|
Ghio D, Aragon ALM, Biazzo I, Zdeborová L. Bayes-optimal inference for spreading processes on random networks. Phys Rev E 2023; 108:044308. [PMID: 37978700 DOI: 10.1103/physreve.108.044308] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/06/2023] [Accepted: 09/25/2023] [Indexed: 11/19/2023]
Abstract
We consider a class of spreading processes on networks, which generalize commonly used epidemic models such as the SIR model or the SIS model with a bounded number of reinfections. We analyze the related problem of inference of the dynamics based on its partial observations. We analyze these inference problems on random networks via a message-passing inference algorithm derived from the belief propagation (BP) equations. We investigate whether said algorithm solves the problems in a Bayes-optimal way, i.e., no other algorithm can reach a better performance. For this, we leverage the so-called Nishimori conditions that must be satisfied by a Bayes-optimal algorithm. We also probe for phase transitions by considering the convergence time and by initializing the algorithm in both a random and an informed way and comparing the resulting fixed points. We present the corresponding phase diagrams. We find large regions of parameters where even for moderate system sizes the BP algorithm converges and satisfies closely the Nishimori conditions, and the problem is thus conjectured to be solved optimally in those regions. In other limited areas of the space of parameters, the Nishimori conditions are no longer satisfied and the BP algorithm struggles to converge. No sign of a phase transition is detected, however, and we attribute this failure of optimality to finite-size effects. The article is accompanied by a Python implementation of the algorithm that is easy to use or adapt.
Collapse
Affiliation(s)
- Davide Ghio
- Ide PHICS Laboratory, Ecole Polytechnique Fédérale de Lausanne (EPFL), Rte Cantonale, 1015 Lausanne, Switzerland
| | - Antoine L M Aragon
- SPOC Laboratory, Ecole Polytechnique Fédérale de Lausanne (EPFL), Rte Cantonale, 1015 Lausanne, Switzerland
| | - Indaco Biazzo
- SPOC Laboratory, Ecole Polytechnique Fédérale de Lausanne (EPFL), Rte Cantonale, 1015 Lausanne, Switzerland
| | - Lenka Zdeborová
- SPOC Laboratory, Ecole Polytechnique Fédérale de Lausanne (EPFL), Rte Cantonale, 1015 Lausanne, Switzerland
| |
Collapse
|
2
|
Nian F, Qian Y, Yao Y. Identification of Potential Cooperation Relationships Among Scientists. BIG DATA 2023; 11:87-104. [PMID: 36084020 DOI: 10.1089/big.2021.0398] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/12/2023]
Abstract
In this article, the phenomenon of scientist cooperation in the scientist cooperation network is studied from the perspectives of information spread and link prediction. By mining the information in the scientist cooperation network, analyzing the cooperation has been generated and discovering potential cooperation opportunities. It helps to build a richer cooperation network with more content. Information spread can reflect the inner laws of network structure formation, and the link prediction method can retain the integrity of network information to the maximum extent. First, the real network is abstracted by analyzing its structure as well as node attributes into a simulated network. Second, the process of information spread in the cooperation network is simulated by improving the traditional SIS model. Some improvements are made to the link prediction algorithm for the impact brought to the network by information spread. Finally, the experimental results in the scientist cooperation network show that the hybrid weighted link prediction algorithm combining node attributes and spread factors can improve the accuracy of link prediction and provide suggestions for scientists to find partners. The comparative experiments on simulated and real networks not only validate the effectiveness of the propagation model in the scientist cooperation network, but also verify the accuracy of the hybrid weighted link prediction algorithm.
Collapse
Affiliation(s)
- Fuzhong Nian
- School of Computer and Communication, Lanzhou University of Technology, Lanzhou, China
| | - Yinuo Qian
- School of Computer and Communication, Lanzhou University of Technology, Lanzhou, China
| | - Yabing Yao
- School of Computer and Communication, Lanzhou University of Technology, Lanzhou, China
| |
Collapse
|
3
|
Najem S, Monni S, Hatoum R, Sweidan H, Faour G, Abdallah C, Ghosn N, Hassan H, Touma J. A framework for reconstructing transmission networks in infectious diseases. APPLIED NETWORK SCIENCE 2022; 7:85. [PMID: 36567737 PMCID: PMC9761645 DOI: 10.1007/s41109-022-00525-4] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 09/06/2022] [Accepted: 12/12/2022] [Indexed: 06/17/2023]
Abstract
In this paper, we propose a general framework for the reconstruction of the underlying cross-regional transmission network contributing to the spread of an infectious disease. We employ an autoregressive model that allows to decompose the mean number of infections into three components that describe: intra-locality infections, inter-locality infections, and infections from other sources such as travelers arriving to a country from abroad. This model is commonly used in the identification of spatiotemporal patterns in seasonal infectious diseases and thus in forecasting infection counts. However, our contribution lies in identifying the inter-locality term as a time-evolving network, and rather than using the model for forecasting, we focus on the network properties without any assumption on seasonality or recurrence of the disease. The topology of the network is then studied to get insight into the disease dynamics. Building on this, and particularly on the centrality of the nodes of the identified network, a strategy for intervention and disease control is devised.
Collapse
Affiliation(s)
- Sara Najem
- Department of Physics, American University of Beirut, Beirut, Lebanon
- Center for Advanced Mathematical Sciences, American University of Beirut, Beirut, Lebanon
| | - Stefano Monni
- Department of Physics, American University of Beirut, Beirut, Lebanon
- Department of Mathematics, American University of Beirut, Beirut, Lebanon
| | - Rola Hatoum
- Center for Advanced Mathematical Sciences, American University of Beirut, Beirut, Lebanon
| | - Hawraa Sweidan
- Epidemiological Surveillance Program, Ministry of Public Health, Beirut, Lebanon
| | - Ghaleb Faour
- National Center for Remote Sensing, National Council for Scientific Research (CNRS), Beirut, Lebanon
| | - Chadi Abdallah
- National Center for Remote Sensing, National Council for Scientific Research (CNRS), Beirut, Lebanon
| | - Nada Ghosn
- Epidemiological Surveillance Program, Ministry of Public Health, Beirut, Lebanon
| | - Hamad Hassan
- Faculty of Public Health, Lebanese University, Beirut, Lebanon
| | - Jihad Touma
- Department of Physics, American University of Beirut, Beirut, Lebanon
- Center for Advanced Mathematical Sciences, American University of Beirut, Beirut, Lebanon
| |
Collapse
|
4
|
A Bayesian generative neural network framework for epidemic inference problems. Sci Rep 2022; 12:19673. [PMID: 36385141 PMCID: PMC9667449 DOI: 10.1038/s41598-022-20898-x] [Citation(s) in RCA: 4] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/28/2022] [Accepted: 09/20/2022] [Indexed: 11/17/2022] Open
Abstract
The reconstruction of missing information in epidemic spreading on contact networks can be essential in the prevention and containment strategies. The identification and warning of infectious but asymptomatic individuals (i.e., contact tracing), the well-known patient-zero problem, or the inference of the infectivity values in structured populations are examples of significant epidemic inference problems. As the number of possible epidemic cascades grows exponentially with the number of individuals involved and only an almost negligible subset of them is compatible with the observations (e.g., medical tests), epidemic inference in contact networks poses incredible computational challenges. We present a new generative neural networks framework that learns to generate the most probable infection cascades compatible with observations. The proposed method achieves better (in some cases, significantly better) or comparable results with existing methods in all problems considered both in synthetic and real contact networks. Given its generality, clear Bayesian and variational nature, the presented framework paves the way to solve fundamental inference epidemic problems with high precision in small and medium-sized real case scenarios such as the spread of infections in workplaces and hospitals.
Collapse
|
5
|
Waniek M, Holme P, Cebrian M, Rahwan T. Social diffusion sources can escape detection. iScience 2022; 25:104956. [PMID: 36093057 PMCID: PMC9459693 DOI: 10.1016/j.isci.2022.104956] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/19/2022] [Revised: 04/25/2022] [Accepted: 08/12/2022] [Indexed: 11/16/2022] Open
Abstract
Influencing others through social networks is fundamental to all human societies. Whether this happens through the diffusion of rumors, opinions, or viruses, identifying the diffusion source (i.e., the person that initiated it) is a problem that has attracted much research interest. Nevertheless, existing literature has ignored the possibility that the source might strategically modify the network structure (by rewiring links or introducing fake nodes) to escape detection. Here, without restricting our analysis to any particular diffusion scenario, we close this gap by evaluating two mechanisms that hide the source-one stemming from the source's actions, the other from the network structure itself. This reveals that sources can easily escape detection, and that removing links is far more effective than introducing fake nodes. Thus, efforts should focus on exposing concealed ties rather than planted entities; such exposure would drastically improve our chances of detecting the diffusion source.
Collapse
Affiliation(s)
- Marcin Waniek
- Computer Science, Division of Science, New York University Abu Dhabi, Saadiyat Island, Abu Dhabi 129188, UAE
| | - Petter Holme
- Department of Computer Science, Aalto University, Otakaari 1B, 02150 Espoo, Finland
- Center for Computational Social Science, Kobe University, 2-1 Rokkodai-cho, Nada-ku, Kobe 657-8501, Japan
| | - Manuel Cebrian
- Center for Humans and Machines, Max Planck Institute for Human Development, Lentzeallee 94, 14195 Berlin, Germany
- Department of Statistics, Universidad Carlos III de Madrid, Calle Madrid 126, 28903 Getafe, Spain
- UC3M-Santander Big Data Institute, Calle Madrid 135, 28903 Getafe, Spain
| | - Talal Rahwan
- Computer Science, Division of Science, New York University Abu Dhabi, Saadiyat Island, Abu Dhabi 129188, UAE
| |
Collapse
|
6
|
Cai Z, Gerding E, Brede M. Control Meets Inference: Using Network Control to Uncover the Behaviour of Opponents. ENTROPY (BASEL, SWITZERLAND) 2022; 24:640. [PMID: 35626525 PMCID: PMC9140578 DOI: 10.3390/e24050640] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 04/12/2022] [Revised: 04/29/2022] [Accepted: 04/29/2022] [Indexed: 02/05/2023]
Abstract
Using observational data to infer the coupling structure or parameters in dynamical systems is important in many real-world applications. In this paper, we propose a framework of strategically influencing a dynamical process that generates observations with the aim of making hidden parameters more easily inferable. More specifically, we consider a model of networked agents who exchange opinions subject to voting dynamics. Agent dynamics are subject to peer influence and to the influence of two controllers. One of these controllers is treated as passive and we presume its influence is unknown. We then consider a scenario in which the other active controller attempts to infer the passive controller's influence from observations. Moreover, we explore how the active controller can strategically deploy its own influence to manipulate the dynamics with the aim of accelerating the convergence of its estimates of the opponent. Along with benchmark cases we propose two heuristic algorithms for designing optimal influence allocations. We establish that the proposed algorithms accelerate the inference process by strategically interacting with the network dynamics. Investigating configurations in which optimal control is deployed. We first find that agents with higher degrees and larger opponent allocations are harder to predict. Second, even factoring in strategical allocations, opponent's influence is typically the harder to predict the more degree-heterogeneous the social network.
Collapse
Affiliation(s)
- Zhongqi Cai
- School of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK; (E.G.); (M.B.)
| | | | | |
Collapse
|
7
|
Arici MK, Tuncbag N. Performance Assessment of the Network Reconstruction Approaches on Various Interactomes. Front Mol Biosci 2021; 8:666705. [PMID: 34676243 PMCID: PMC8523993 DOI: 10.3389/fmolb.2021.666705] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/10/2021] [Accepted: 07/14/2021] [Indexed: 01/04/2023] Open
Abstract
Beyond the list of molecules, there is a necessity to collectively consider multiple sets of omic data and to reconstruct the connections between the molecules. Especially, pathway reconstruction is crucial to understanding disease biology because abnormal cellular signaling may be pathological. The main challenge is how to integrate the data together in an accurate way. In this study, we aim to comparatively analyze the performance of a set of network reconstruction algorithms on multiple reference interactomes. We first explored several human protein interactomes, including PathwayCommons, OmniPath, HIPPIE, iRefWeb, STRING, and ConsensusPathDB. The comparison is based on the coverage of each interactome in terms of cancer driver proteins, structural information of protein interactions, and the bias toward well-studied proteins. We next used these interactomes to evaluate the performance of network reconstruction algorithms including all-pair shortest path, heat diffusion with flux, personalized PageRank with flux, and prize-collecting Steiner forest (PCSF) approaches. Each approach has its own merits and weaknesses. Among them, PCSF had the most balanced performance in terms of precision and recall scores when 28 pathways from NetPath were reconstructed using the listed algorithms. Additionally, the reference interactome affects the performance of the network reconstruction approaches. The coverage and disease- or tissue-specificity of each interactome may vary, which may result in differences in the reconstructed networks.
Collapse
Affiliation(s)
- M Kaan Arici
- Graduate School of Informatics, Middle East Technical University, Ankara, Turkey.,Foot and Mouth Diseases Institute, Ministry of Agriculture and Forestry, Ankara, Turkey
| | - Nurcan Tuncbag
- Chemical and Biological Engineering, College of Engineering, Koc University, Istanbul, Turkey.,School of Medicine, Koc University, Istanbul, Turkey
| |
Collapse
|
8
|
Gajewski ŁG, Sienkiewicz J, Hołyst JA. Discovering hidden layers in quantum graphs. Phys Rev E 2021; 104:034311. [PMID: 34654079 DOI: 10.1103/physreve.104.034311] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/17/2021] [Accepted: 09/09/2021] [Indexed: 11/07/2022]
Abstract
Finding hidden layers in complex networks is an important and a nontrivial problem in modern science. We explore the framework of quantum graphs to determine whether concealed parts of a multilayer system exist and if so then what is their extent, i.e., how many unknown layers are there. Assuming that the only information available is the time evolution of a wave propagation on a single layer of a network it is indeed possible to uncover that which is hidden by merely observing the dynamics. We present evidence on both synthetic and real-world networks that the frequency spectrum of the wave dynamics can express distinct features in the form of additional frequency peaks. These peaks exhibit dependence on the number of layers taking part in the propagation and thus allowing for the extraction of said number. We show that, in fact, with sufficient observation time, one can fully reconstruct the row-normalized adjacency matrix spectrum. We compare our propositions to a machine learning approach using a wave packet signature method modified for the purposes of multilayer systems.
Collapse
Affiliation(s)
- Łukasz G Gajewski
- Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00-662 Warszawa, Poland
| | - Julian Sienkiewicz
- Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00-662 Warszawa, Poland
| | - Janusz A Hołyst
- Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00-662 Warszawa, Poland and ITMO University, Kronverkskiy Prospekt 49, St Petersburg, Russia 197101
| |
Collapse
|
9
|
Gajewski ŁG, Chołoniewski J, Wilinski M. Detecting hidden layers from spreading dynamics on complex networks. Phys Rev E 2021; 104:024309. [PMID: 34525536 DOI: 10.1103/physreve.104.024309] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/31/2021] [Accepted: 07/23/2021] [Indexed: 11/07/2022]
Abstract
When dealing with spreading processes on networks it can be of the utmost importance to test the reliability of data and identify potential unobserved spreading paths. In this paper we address these problems and propose methods for hidden layer identification and reconstruction. We also explore the interplay between difficulty of the task and the structure of the multilayer network describing the whole system where the spreading process occurs. Our methods stem from an exact expression for the likelihood of a cascade in the susceptible-infected model on an arbitrary graph. We then show that by imploring statistical properties of unimodal distributions and simple heuristics describing joint likelihood of a series of cascades one can obtain an estimate of both existence of a hidden layer and its content with success rates far exceeding those of a null model. We conduct our analyses on both synthetic and real-world networks providing evidence for the viability of the approach presented.
Collapse
Affiliation(s)
- Łukasz G Gajewski
- Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00-662 Warsaw, Poland
| | - Jan Chołoniewski
- Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00-662 Warsaw, Poland
| | - Mateusz Wilinski
- Theoretical Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA
| |
Collapse
|
10
|
Selinger C, Alizon S. Reconstructing contact network structure and cross-immunity patterns from multiple infection histories. PLoS Comput Biol 2021; 17:e1009375. [PMID: 34525092 PMCID: PMC8475980 DOI: 10.1371/journal.pcbi.1009375] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/07/2021] [Revised: 09/27/2021] [Accepted: 08/23/2021] [Indexed: 11/29/2022] Open
Abstract
Interactions within a population shape the spread of infectious diseases but contact patterns between individuals are difficult to access. We hypothesised that key properties of these patterns can be inferred from multiple infection data in longitudinal follow-ups. We developed a simulator for epidemics with multiple infections on networks and analysed the resulting individual infection time series by introducing similarity metrics between hosts based on their multiple infection histories. We find that, depending on infection multiplicity and network sampling, multiple infection summary statistics can recover network properties such as degree distribution. Furthermore, we show that by mining simulation outputs for multiple infection patterns, one can detect immunological interference between pathogens (i.e. the fact that past infections in a host condition future probability of infection). The combination of individual-based simulations and analysis of multiple infection histories opens promising perspectives to infer and validate transmission networks and immunological interference for infectious diseases from longitudinal cohort data.
Collapse
Affiliation(s)
| | - Samuel Alizon
- MIVEGEC, Univ. Montpellier, CNRS, IRD, Montpellier, France
| |
Collapse
|
11
|
Kuang J, Scoglio C. Layer reconstruction and missing link prediction of a multilayer network with maximum a posteriori estimation. Phys Rev E 2021; 104:024301. [PMID: 34525660 PMCID: PMC8445383 DOI: 10.1103/physreve.104.024301] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/07/2021] [Accepted: 07/16/2021] [Indexed: 04/23/2023]
Abstract
From social networks to biological networks, different types of interactions among the same set of nodes characterize distinct layers, which are termed multilayer networks. Within a multilayer network, some layers, confirmed through different experiments, could be structurally similar and interdependent. In this paper, we propose a maximum a posteriori-based method to study and reconstruct the structure of a target layer in a multilayer network. Nodes within the target layer are characterized by vectors, which are employed to compute edge weights. Further, to detect structurally similar layers, we propose a method for comparing networks based on the eigenvector centrality. Using similar layers, we obtain the parameters of the conjugate prior. With this maximum a posteriori algorithm, we can reconstruct the target layer and predict missing links. We test the method on two real multilayer networks, and the results show that the maximum a posteriori estimation is promising in reconstructing the target layer even when a large number of links is missing.
Collapse
Affiliation(s)
- Junyao Kuang
- Department of Electrical and Computer Engineering, Kansas State University, Manhattan, KS 66506, USA
| | - Caterina Scoglio
- Department of Electrical and Computer Engineering, Kansas State University, Manhattan, KS 66506, USA
| |
Collapse
|
12
|
Wong NS, Lee SS, Kwan TH, Yeoh EK. Settings of virus exposure and their implications in the propagation of transmission networks in a COVID-19 outbreak. THE LANCET REGIONAL HEALTH. WESTERN PACIFIC 2020; 4:100052. [PMID: 34013218 PMCID: PMC7649091 DOI: 10.1016/j.lanwpc.2020.100052] [Citation(s) in RCA: 13] [Impact Index Per Article: 3.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 09/16/2020] [Revised: 10/15/2020] [Accepted: 10/27/2020] [Indexed: 12/15/2022]
Abstract
BACKGROUND Transmission dynamics of SARS-CoV-2 varied by the settings of virus exposure. Understanding the inter-relationship between exposure setting and transmission networks would provide a basis for informing public health control strategies. METHODS Surveillance and clinical data from the first wave of COVID-19 outbreaks in Hong Kong were accessed. Twelve exposure setting types were differentiated - household, neighbourhood, eateries, entertainment, parties, shopping, personalised service, workplace, education, worship, healthcare, transport. Clustering was investigated followed by reconstructing the transmission cascades of clustered cases using social networking approach. Linked and unlinked cases were compared in statistical analyses. FINDINGS Between 23 January and 19 June 2020, 1128 cases were reported. Among 324 cases related to local transmission, 123 clusters comprising two or more epidemiologically linked cases were identified. Linked cases had lower Ct value (p < 0·001) than unlinked cases. Households accounted for 63% of all clusters with half as primary setting, while entertainment accounted for the highest number of primary setting transmission cases. There were altogether 19 cascades involving >1 exposure setting, with a median reproduction number of 3(IQR: 2-4), versus 1(IQR:1-2) for cascades involving a single setting (n = 36 cascades). The longest cascade featured a bar (entertainment) as primary setting, with propagation through 30 non-primary exposure settings from seven setting types, reflecting, propensity for widespread dispersion and difficulty in containment. INTERPRETATION There was marked heterogeneity in the characteristics of SARS-CoV-2 transmission cascades which differed by exposure setting. Network epidemiological analyses of transmission cascades can be applied as a risk assessment tool in decision-making for calibrating social distancing measures. FUNDING Health and Medical Research Fund.
Collapse
Affiliation(s)
- Ngai Sze Wong
- Stanley Ho Centre for Emerging Infectious Diseases, Faculty of Medicine, The Chinese University of Hong Kong, Shatin, Hong Kong, China
| | - Shui Shan Lee
- Stanley Ho Centre for Emerging Infectious Diseases, Faculty of Medicine, The Chinese University of Hong Kong, Shatin, Hong Kong, China
| | - Tsz Ho Kwan
- Stanley Ho Centre for Emerging Infectious Diseases, Faculty of Medicine, The Chinese University of Hong Kong, Shatin, Hong Kong, China
| | - Eng-Kiong Yeoh
- Centre for Health Systems and Policy Research, Faculty of Medicine, The Chinese University of Hong Kong, Shatin, Hong Kong, China
- Jockey Club School of Public Health and Primary Care, Faculty of Medicine, The Chinese University of Hong Kong, Shatin, Hong Kong, China
| |
Collapse
|
13
|
Surano FV, Bongiorno C, Zino L, Porfiri M, Rizzo A. Backbone reconstruction in temporal networks from epidemic data. Phys Rev E 2019; 100:042306. [PMID: 31770979 PMCID: PMC7217498 DOI: 10.1103/physreve.100.042306] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/11/2019] [Indexed: 01/22/2023]
Abstract
Many complex systems are characterized by time-varying patterns of interactions. These interactions comprise strong ties, driven by dyadic relationships, and weak ties, based on node-specific attributes. The interplay between strong and weak ties plays an important role on dynamical processes that could unfold on complex systems. However, seldom do we have access to precise information about the time-varying topology of interaction patterns. A particularly elusive question is to distinguish strong from weak ties, on the basis of the sole node dynamics. Building upon analytical results, we propose a statistically-principled algorithm to reconstruct the backbone of strong ties from data of a spreading process, consisting of the time series of individuals' states. Our method is numerically validated over a range of synthetic datasets, encapsulating salient features of real-world systems. Motivated by compelling evidence, we propose the integration of our algorithm in a targeted immunization strategy that prioritizes influential nodes in the inferred backbone. Through Monte Carlo simulations on synthetic networks and a real-world case study, we demonstrate the viability of our approach.
Collapse
Affiliation(s)
- Francesco Vincenzo Surano
- Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Turin, Italy
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, New York 11201, USA
| | - Christian Bongiorno
- Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Turin, Italy
- Laboratoire de Mathématiques et Informatique pour les Systèmes Complexes, CentraleSupélec, Université Paris Saclay, 91190 Gif-sur-Yvette, France
| | - Lorenzo Zino
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, New York 11201, USA
| | - Maurizio Porfiri
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, New York 11201, USA
| | - Alessandro Rizzo
- Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Turin, Italy
| |
Collapse
|
14
|
Peixoto TP. Network Reconstruction and Community Detection from Dynamics. PHYSICAL REVIEW LETTERS 2019; 123:128301. [PMID: 31633974 PMCID: PMC7226905 DOI: 10.1103/physrevlett.123.128301] [Citation(s) in RCA: 30] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/28/2019] [Revised: 05/21/2019] [Indexed: 05/06/2023]
Abstract
We present a scalable nonparametric Bayesian method to perform network reconstruction from observed functional behavior that at the same time infers the communities present in the network. We show that the joint reconstruction with community detection has a synergistic effect, where the edge correlations used to inform the existence of communities are also inherently used to improve the accuracy of the reconstruction which, in turn, can better inform the uncovering of communities. We illustrate the use of our method with observations arising from epidemic models and the Ising model, both on synthetic and empirical networks, as well as on data containing only functional information.
Collapse
Affiliation(s)
- Tiago P Peixoto
- Department of Network and Data Science, Central European University, H-1051 Budapest, Hungary
- ISI Foundation, Via Chisola 5, 10126 Torino, Italy
- Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom
| |
Collapse
|