1
|
Badalyan A, Ruggeri N, De Bacco C. Structure and inference in hypergraphs with node attributes. Nat Commun 2024; 15:7073. [PMID: 39152121 PMCID: PMC11329712 DOI: 10.1038/s41467-024-51388-5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/07/2023] [Accepted: 08/06/2024] [Indexed: 08/19/2024] Open
Abstract
Many networked datasets with units interacting in groups of two or more, encoded with hypergraphs, are accompanied by extra information about nodes, such as the role of an individual in a workplace. Here we show how these node attributes can be used to improve our understanding of the structure resulting from higher-order interactions. We consider the problem of community detection in hypergraphs and develop a principled model that combines higher-order interactions and node attributes to better represent the observed interactions and to detect communities more accurately than using either of these types of information alone. The method learns automatically from the input data the extent to which structure and attributes contribute to explain the data, down weighing or discarding attributes if not informative. Our algorithmic implementation is efficient and scales to large hypergraphs and interactions of large numbers of units. We apply our method to a variety of systems, showing strong performance in hyperedge prediction tasks and in selecting community divisions that correlate with attributes when these are informative, but discarding them otherwise. Our approach illustrates the advantage of using informative node attributes when available with higher-order data.
Collapse
Affiliation(s)
- Anna Badalyan
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen, Germany
| | - Nicolò Ruggeri
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen, Germany.
- Department of Computer Science, ETH, Zürich, Switzerland.
| | - Caterina De Bacco
- Max Planck Institute for Intelligent Systems, Cyber Valley, Tübingen, Germany.
| |
Collapse
|
2
|
Gallo L, Lacasa L, Latora V, Battiston F. Higher-order correlations reveal complex memory in temporal hypergraphs. Nat Commun 2024; 15:4754. [PMID: 38834592 DOI: 10.1038/s41467-024-48578-6] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/16/2023] [Accepted: 05/02/2024] [Indexed: 06/06/2024] Open
Abstract
Many real-world complex systems are characterized by interactions in groups that change in time. Current temporal network approaches, however, are unable to describe group dynamics, as they are based on pairwise interactions only. Here, we use time-varying hypergraphs to describe such systems, and we introduce a framework based on higher-order correlations to characterize their temporal organization. The analysis of human interaction data reveals the existence of coherent and interdependent mesoscopic structures, thus capturing aggregation, fragmentation and nucleation processes in social systems. We introduce a model of temporal hypergraphs with non-Markovian group interactions, which reveals complex memory as a fundamental mechanism underlying the emerging pattern in the data.
Collapse
Affiliation(s)
- Luca Gallo
- Department of Network and Data Science, Central European University, Vienna, Austria.
| | - Lucas Lacasa
- Institute for Cross-Disciplinary Physics and Complex Systems (IFISC), CSIC-UIB, Palma de Mallorca, Spain
| | - Vito Latora
- School of Mathematical Sciences, Queen Mary University of London, London, E1 4NS, UK
- Department of Physics and Astronomy, University of Catania, 95125, Catania, Italy
- INFN Sezione di Catania, Via S. Sofia, 64, 95125, Catania, Italy
- Complexity Science Hub Vienna, A-1080, Vienna, Austria
| | - Federico Battiston
- Department of Network and Data Science, Central European University, Vienna, Austria.
| |
Collapse
|
3
|
Meng Y, Cornelius SP, Liu YY, Li A. Dynamics of collective cooperation under personalised strategy updates. Nat Commun 2024; 15:3125. [PMID: 38600076 PMCID: PMC11006938 DOI: 10.1038/s41467-024-47380-8] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/22/2023] [Accepted: 03/28/2024] [Indexed: 04/12/2024] Open
Abstract
Collective cooperation is essential for many social and biological systems, yet understanding how it evolves remains a challenge. Previous investigations report that the ubiquitous heterogeneous individual connections hinder cooperation by assuming individuals update strategies at identical rates. Here we develop a general framework by allowing individuals to update strategies at personalised rates, and provide the precise mathematical condition under which universal cooperation is favoured. Combining analytical and numerical calculations on synthetic and empirical networks, we find that when individuals' update rates vary inversely with their number of connections, heterogeneous connections actually outperform homogeneous ones in promoting cooperation. This surprising property undercuts the conventional wisdom that heterogeneous structure is generally antagonistic to cooperation and, further helps develop an efficient algorithm OptUpRat to optimise collective cooperation by designing individuals' update rates in any population structure. Our findings provide a unifying framework to understand the interplay between structural heterogeneity, behavioural rhythms, and cooperation.
Collapse
Affiliation(s)
- Yao Meng
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China
| | - Sean P Cornelius
- Department of Physics, Toronto Metropolitan University, Toronto, ON, M5B 2K3, Canada
| | - Yang-Yu Liu
- Channing Division of Network Medicine, Department of Medicine, Brigham and Women's Hospital and Harvard Medical School, Boston, MA, 02115, USA
- Center for Artificial Intelligence and Modeling, The Carl R. Woese Institute for Genomic Biology, University of Illinois at Urbana-Champaign, Champaign, IL, 61801, USA
| | - Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing, 100871, China.
| |
Collapse
|
4
|
Sheng A, Su Q, Li A, Wang L, Plotkin JB. Constructing temporal networks with bursty activity patterns. Nat Commun 2023; 14:7311. [PMID: 37951967 PMCID: PMC10640578 DOI: 10.1038/s41467-023-42868-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/13/2023] [Accepted: 10/24/2023] [Indexed: 11/14/2023] Open
Abstract
Human social interactions tend to vary in intensity over time, whether they are in person or online. Variable rates of interaction in structured populations can be described by networks with the time-varying activity of links and nodes. One of the key statistics to summarize temporal patterns is the inter-event time, namely the duration between successive pairwise interactions. Empirical studies have found inter-event time distributions that are heavy-tailed, for both physical and digital interactions. But it is difficult to construct theoretical models of time-varying activity on a network that reproduce the burstiness seen in empirical data. Here we develop a spanning-tree method to construct temporal networks and activity patterns with bursty behavior. Our method ensures any desired target inter-event time distributions for individual nodes and links, provided the distributions fulfill a consistency condition, regardless of whether the underlying topology is static or time-varying. We show that this model can reproduce burstiness found in empirical datasets, and so it may serve as a basis for studying dynamic processes in real-world bursty interactions.
Collapse
Affiliation(s)
- Anzhi Sheng
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China
- Department of Biology, University of Pennsylvania, Philadelphia, PA, 19104, USA
| | - Qi Su
- Department of Automation, Shanghai Jiao Tong University, Shanghai, 200240, China
- Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai, 200240, China
- Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai, 200240, China
| | - Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing, 100871, China.
| | - Long Wang
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing, 100871, China.
| | - Joshua B Plotkin
- Department of Biology, University of Pennsylvania, Philadelphia, PA, 19104, USA.
- Center for Mathematical Biology, University of Pennsylvania, Philadelphia, PA, 19014, USA.
| |
Collapse
|
5
|
Li T, Wang W, Jiao P, Wang Y, Ding R, Wu H, Pan L, Jin D. Exploring Temporal Community Structure via Network Embedding. IEEE TRANSACTIONS ON CYBERNETICS 2023; 53:7021-7033. [PMID: 35507615 DOI: 10.1109/tcyb.2022.3168343] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/14/2023]
Abstract
Temporal community detection is helpful to discover and analyze significant groups or clusters hidden in dynamic networks in the real world. A variety of methods, such as modularity optimization, spectral method, and statistical network model, has been developed from diversified perspectives. Recently, network embedding-based technologies have made significant progress, and one can exploit deep learning superiority to network tasks. Although some methods for static networks have shown promising results in boosting community detection by integrating community embedding, they are not suitable for temporal networks and unable to capture their dynamics. Furthermore, the dynamic embedding methods only model network varying without considering community structures. Hence, in this article, we propose a novel unsupervised dynamic community detection model, which is based on network embedding and can effectively discover temporal communities and model dynamic networks. More specifically, we propose the community prior by introducing the Gaussian mixture model (GMM) in the variational autoencoder, which can obtain community information and better model the evolutionary characteristics of community structure and node embedding by utilizing the variant of gated recurrent unit (GRU). Extensive experiments conducted in real-world and artificial networks demonstrate that our proposed model has a better effect on improving the accuracy of dynamic community detection.
Collapse
|
6
|
Gote C, Perri V, Zingg C, Casiraghi G, Arzig C, von Gernler A, Schweitzer F, Scholtes I. Locating community smells in software development processes using higher-order network centralities. SOCIAL NETWORK ANALYSIS AND MINING 2023; 13:129. [PMID: 37829148 PMCID: PMC10564836 DOI: 10.1007/s13278-023-01120-w] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/02/2023] [Revised: 06/08/2023] [Accepted: 08/25/2023] [Indexed: 10/14/2023]
Abstract
Community smells are negative patterns in software development teams' interactions that impede their ability to successfully create software. Examples are team members working in isolation, lack of communication and collaboration across departments or sub-teams, or areas of the codebase where only a few team members can work on. Current approaches aim to detect community smells by analysing static network representations of software teams' interaction structures. In doing so, they are insufficient to locate community smells within development processes. Extending beyond the capabilities of traditional social network analysis, we show that higher-order network models provide a robust means of revealing such hidden patterns and complex relationships. To this end, we develop a set of centrality measures based on the MOGen higher-order network model and show their effectiveness in predicting influential nodes using five empirical datasets. We then employ these measures for a comprehensive analysis of a product team at the German IT security company genua GmbH, showcasing our method's success in identifying and locating community smells. Specifically, we uncover critical community smells in two areas of the team's development process. Semi-structured interviews with five team members validate our findings: while the team was aware of one community smell and employed measures to address it, it was not aware of the second. This highlights the potential of our approach as a robust tool for identifying and addressing community smells in software development teams. More generally, our work contributes to the social network analysis field with a powerful set of higher-order network centralities that effectively capture community dynamics and indirect relationships.
Collapse
Affiliation(s)
- Christoph Gote
- Chair of Systems Design, ETH Zurich, Weinbergstrasse 56/58, 8092 Zurich, Switzerland
- Data Analytics Group, Department of Informatics, University of Zurich, Binzmühlestrasse 14, 8050 Zurich, Switzerland
- Chair of Machine Learning for Complex Networks, Center for Artificial Intelligence and Data Science (CAIDAS), University of Würzburg, John Skilton Str. 8A, 97074 Würzburg, Germany
| | - Vincenzo Perri
- Data Analytics Group, Department of Informatics, University of Zurich, Binzmühlestrasse 14, 8050 Zurich, Switzerland
- Chair of Machine Learning for Complex Networks, Center for Artificial Intelligence and Data Science (CAIDAS), University of Würzburg, John Skilton Str. 8A, 97074 Würzburg, Germany
| | - Christian Zingg
- Chair of Systems Design, ETH Zurich, Weinbergstrasse 56/58, 8092 Zurich, Switzerland
| | - Giona Casiraghi
- Chair of Systems Design, ETH Zurich, Weinbergstrasse 56/58, 8092 Zurich, Switzerland
| | - Carsten Arzig
- genua GmbH, Domagkstraße 7, 85551 Kirchheim bei München, Germany
| | | | - Frank Schweitzer
- Chair of Systems Design, ETH Zurich, Weinbergstrasse 56/58, 8092 Zurich, Switzerland
- Complexity Science Hub, Josefstädter Straße 39, 1080 Vienna, Austria
| | - Ingo Scholtes
- Data Analytics Group, Department of Informatics, University of Zurich, Binzmühlestrasse 14, 8050 Zurich, Switzerland
- Chair of Machine Learning for Complex Networks, Center for Artificial Intelligence and Data Science (CAIDAS), University of Würzburg, John Skilton Str. 8A, 97074 Würzburg, Germany
| |
Collapse
|
7
|
Mancastroppa M, Iacopini I, Petri G, Barrat A. Hyper-cores promote localization and efficient seeding in higher-order processes. Nat Commun 2023; 14:6223. [PMID: 37802994 PMCID: PMC10558485 DOI: 10.1038/s41467-023-41887-2] [Citation(s) in RCA: 3] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/11/2023] [Accepted: 09/22/2023] [Indexed: 10/08/2023] Open
Abstract
Going beyond networks, to include higher-order interactions of arbitrary sizes, is a major step to better describe complex systems. In the resulting hypergraph representation, tools to identify structures and central nodes are scarce. We consider the decomposition of a hypergraph in hyper-cores, subsets of nodes connected by at least a certain number of hyperedges of at least a certain size. We show that this provides a fingerprint for data described by hypergraphs and suggests a novel notion of centrality, the hypercoreness. We assess the role of hyper-cores and nodes with large hypercoreness in higher-order dynamical processes: such nodes have large spreading power and spreading processes are localized in central hyper-cores. Additionally, in the emergence of social conventions very few committed individuals with high hypercoreness can rapidly overturn a majority convention. Our work opens multiple research avenues, from comparing empirical data to model validation and study of temporally varying hypergraphs.
Collapse
Affiliation(s)
- Marco Mancastroppa
- Aix Marseille Univ, Université de Toulon, CNRS, CPT, Turing Center for Living Systems, Marseille, France
| | - Iacopo Iacopini
- Network Science Institute, Northeastern University London, London, E1W 1LP, United Kingdom
- Department of Network and Data Science, Central European University, 1100, Vienna, Austria
| | - Giovanni Petri
- Network Science Institute, Northeastern University London, London, E1W 1LP, United Kingdom
- CENTAI, Corso Inghilterra 3, 10138, Turin, Italy
| | - Alain Barrat
- Aix Marseille Univ, Université de Toulon, CNRS, CPT, Turing Center for Living Systems, Marseille, France.
| |
Collapse
|
8
|
Sheng A, Li A, Wang L. Evolutionary dynamics on sequential temporal networks. PLoS Comput Biol 2023; 19:e1011333. [PMID: 37549167 PMCID: PMC10434888 DOI: 10.1371/journal.pcbi.1011333] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/30/2023] [Revised: 08/17/2023] [Accepted: 07/06/2023] [Indexed: 08/09/2023] Open
Abstract
Population structure is a well-known catalyst for the evolution of cooperation and has traditionally been considered to be static in the course of evolution. Conversely, real-world populations, such as microbiome communities and online social networks, frequently show a progression from tiny, active groups to huge, stable communities, which is insufficient to be captured by constant structures. Here, we propose sequential temporal networks to characterize growing networked populations, and we extend the theory of evolutionary games to these temporal networks with arbitrary structures and growth rules. We derive analytical rules under which a sequential temporal network has a higher fixation probability for cooperation than its static counterpart. Under neutral drift, the rule is simply a function of the increment of nodes and edges in each time step. But if the selection is weak, the rule is related to coalescence times on networks. In this case, we propose a mean-field approximation to calculate fixation probabilities and critical benefit-to-cost ratios with lower calculation complexity. Numerical simulations in empirical datasets also prove the cooperation-promoting effect of population growth. Our research stresses the significance of population growth in the real world and provides a high-accuracy approximation approach for analyzing the evolution in real-life systems.
Collapse
Affiliation(s)
- Anzhi Sheng
- Center for Systems and Control, College of Engineering, Peking University, Beijing, China
- Department of Biology, University of Pennsylvania, Philadelphia, United States of America
| | - Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing, China
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing, China
| | - Long Wang
- Center for Systems and Control, College of Engineering, Peking University, Beijing, China
- Center for Multi-Agent Research, Institute for Artificial Intelligence, Peking University, Beijing, China
| |
Collapse
|
9
|
Zhang J, Heath LS. Adaptive group testing strategy for infectious diseases using social contact graph partitions. Sci Rep 2023; 13:12102. [PMID: 37495642 PMCID: PMC10372051 DOI: 10.1038/s41598-023-39326-9] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/23/2023] [Accepted: 07/24/2023] [Indexed: 07/28/2023] Open
Abstract
Mass testing is essential for identifying infected individuals during an epidemic and allowing healthy individuals to return to normal social activities. However, testing capacity is often insufficient to meet global health needs, especially during newly emerging epidemics. Dorfman's method, a classic group testing technique, helps reduce the number of tests required by pooling the samples of multiple individuals into a single sample for analysis. Dorfman's method does not consider the time dynamics or limits on testing capacity involved in infection detection, and it assumes that individuals are infected independently, ignoring community correlations. To address these limitations, we present an adaptive group testing (AGT) strategy based on graph partitioning, which divides a physical contact network into subgraphs (groups of individuals) and assigns testing priorities based on the social contact characteristics of each subgraph. Our AGT aims to maximize the number of infected individuals detected and minimize the number of tests required. After each testing round (perhaps on a daily basis), the testing priority is increased for each neighboring group of known infected individuals. We also present an enhanced infectious disease transmission model that simulates the dynamic spread of a pathogen and evaluate our AGT strategy using the simulation results. When applied to 13 social contact networks, AGT demonstrates significant performance improvements compared to Dorfman's method and its variations. Our AGT strategy requires fewer tests overall, reduces disease spread, and retains robustness under changes in group size, testing capacity, and other parameters. Testing plays a crucial role in containing and mitigating pandemics by identifying infected individuals and helping to prevent further transmission in families and communities. By identifying infected individuals and helping to prevent further transmission in families and communities, our AGT strategy can have significant implications for public health, providing guidance for policymakers trying to balance economic activity with the need to manage the spread of infection.
Collapse
Affiliation(s)
- Jingyi Zhang
- Department of Computer Science, Virginia Tech, Blacksburg, VA, 24060, USA.
| | - Lenwood S Heath
- Department of Computer Science, Virginia Tech, Blacksburg, VA, 24060, USA
| |
Collapse
|
10
|
Davoodi M, Batista A, Senapati A, Calabrese JM. Personnel Scheduling during the COVID-19 Pandemic: A Probabilistic Graph-Based Approach. Healthcare (Basel) 2023; 11:1917. [PMID: 37444751 DOI: 10.3390/healthcare11131917] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/29/2023] [Revised: 06/27/2023] [Accepted: 06/28/2023] [Indexed: 07/15/2023] Open
Abstract
Effective personnel scheduling is crucial for organizations to match workload demands. However, staff scheduling is sometimes affected by unexpected events, such as the COVID-19 pandemic, that disrupt regular operations. Limiting the number of on-site staff in the workplace together with regular testing is an effective strategy to minimize the spread of infectious diseases like COVID-19 because they spread mostly through close contact with people. Therefore, choosing the best scheduling and testing plan that satisfies the goals of the organization and prevents the virus's spread is essential during disease outbreaks. In this paper, we formulate these challenges in the framework of two Mixed Integer Non-linear Programming (MINLP) models. The first model aims to derive optimal staff occupancy and testing strategies to minimize the risk of infection among employees, while the second is aimed only at optimal staff occupancy under a random testing strategy. To solve the problems expressed in the models, we propose a canonical genetic algorithm as well as two commercial solvers. Using both real and synthetic contact networks of employees, our results show that following the recommended occupancy and testing strategy reduces the risk of infection 25-60% under different scenarios. The minimum risk of infection can be achieved when the employees follow a planned testing strategy. Further, vaccination status and interaction rate of employees are important factors in developing scheduling strategies that minimize the risk of infection.
Collapse
Affiliation(s)
- Mansoor Davoodi
- Center for Advanced Systems Understanding (CASUS), Helmholtz-Zentrum Dresden Rossendorf (HZDR), 01328 Görlitz, Germany
| | - Ana Batista
- Center for Advanced Systems Understanding (CASUS), Helmholtz-Zentrum Dresden Rossendorf (HZDR), 01328 Görlitz, Germany
| | - Abhishek Senapati
- Center for Advanced Systems Understanding (CASUS), Helmholtz-Zentrum Dresden Rossendorf (HZDR), 01328 Görlitz, Germany
| | - Justin M Calabrese
- Center for Advanced Systems Understanding (CASUS), Helmholtz-Zentrum Dresden Rossendorf (HZDR), 01328 Görlitz, Germany
- Department of Ecological Modelling, Helmholtz Centre for Environmental Research (UFZ), 04318 Leipzig, Germany
- Department of Biology, University of Maryland, College Park, MD 20742, USA
| |
Collapse
|
11
|
Cheng S, Pain CC, Guo YK, Arcucci R. Real-time updating of dynamic social networks for COVID-19 vaccination strategies. JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING 2023:1-14. [PMID: 37360777 PMCID: PMC10062280 DOI: 10.1007/s12652-023-04589-7] [Citation(s) in RCA: 2] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 08/11/2021] [Accepted: 03/05/2023] [Indexed: 06/28/2023]
Abstract
Vaccination strategy is crucial in fighting the COVID-19 pandemic. Since the supply is still limited in many countries, contact network-based interventions can be most powerful to set an efficient strategy by identifying high-risk individuals or communities. However, due to the high dimension, only partial and noisy network information can be available in practice, especially for dynamic systems where contact networks are highly time-variant. Furthermore, the numerous mutations of SARS-CoV-2 have a significant impact on the infectious probability, requiring real-time network updating algorithms. In this study, we propose a sequential network updating approach based on data assimilation techniques to combine different sources of temporal information. We then prioritise the individuals with high-degree or high-centrality, obtained from assimilated networks, for vaccination. The assimilation-based approach is compared with the standard method (based on partially observed networks) and a random selection strategy in terms of vaccination effectiveness in a SIR model. The numerical comparison is first carried out using real-world face-to-face dynamic networks collected in a high school, followed by sequential multi-layer networks generated relying on the Barabasi-Albert model emulating large-scale social networks with several communities.
Collapse
Affiliation(s)
- Sibo Cheng
- Data Science Instituite, Department of Computing, Imperial College London, London, UK
| | - Christopher C. Pain
- Department of Earth Science and Engineering, Imperial College London, London, UK
| | - Yi-Ke Guo
- Data Science Instituite, Department of Computing, Imperial College London, London, UK
| | - Rossella Arcucci
- Data Science Instituite, Department of Computing, Imperial College London, London, UK
- Department of Earth Science and Engineering, Imperial College London, London, UK
| |
Collapse
|
12
|
Mazzoli M, Gallotti R, Privitera F, Colet P, Ramasco JJ. Spatial immunization to abate disease spreading in transportation hubs. Nat Commun 2023; 14:1448. [PMID: 36941266 PMCID: PMC10027826 DOI: 10.1038/s41467-023-36985-0] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/10/2022] [Accepted: 02/27/2023] [Indexed: 03/23/2023] Open
Abstract
Proximity social interactions are crucial for infectious diseases transmission. Crowded agglomerations pose serious risk of triggering superspreading events. Locations like transportation hubs (airports and stations) are designed to optimize logistic efficiency, not to reduce crowding, and are characterized by a constant in and out flow of people. Here, we analyze the paradigmatic example of London Heathrow, one of the busiest European airports. Thanks to a dataset of anonymized individuals' trajectories, we can model the spreading of different diseases to localize the contagion hotspots and to propose a spatial immunization policy targeting them to reduce disease spreading risk. We also detect the most vulnerable destinations to contagions produced at the airport and quantify the benefits of the spatial immunization technique to prevent regional and global disease diffusion. This method is immediately generalizable to train, metro and bus stations and to other facilities such as commercial or convention centers.
Collapse
Affiliation(s)
- Mattia Mazzoli
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus UIB, 07122, Palma de Mallorca, Spain.
- INSERM, Sorbonne Université, Institut Pierre Louis d'Epidémiologie et de Santé Publique, IPLESP, Paris, France.
| | - Riccardo Gallotti
- CHuB Lab, Fondazione Bruno Kessler, Via Sommarive 18, 38123, Povo (TN), Trento, Italy
| | | | - Pere Colet
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus UIB, 07122, Palma de Mallorca, Spain
| | - José J Ramasco
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus UIB, 07122, Palma de Mallorca, Spain.
| |
Collapse
|
13
|
A comparison of node vaccination strategies to halt SIR epidemic spreading in real-world complex networks. Sci Rep 2022; 12:21355. [PMID: 36494427 PMCID: PMC9734664 DOI: 10.1038/s41598-022-24652-1] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/18/2022] [Accepted: 11/18/2022] [Indexed: 12/13/2022] Open
Abstract
We compared seven node vaccination strategies in twelve real-world complex networks. The node vaccination strategies are modeled as node removal on networks. We performed node vaccination strategies both removing nodes according to the initial network structure, i.e., non-adaptive approach, and performing partial node rank recalculation after node removal, i.e., semi-adaptive approach. To quantify the efficacy of each vaccination strategy, we used three epidemic spread indicators: the size of the largest connected component, the total number of infected at the end of the epidemic, and the maximum number of simultaneously infected individuals. We show that the best vaccination strategies in the non-adaptive and semi-adaptive approaches are different and that the best strategy also depends on the number of available vaccines. Furthermore, a partial recalculation of the node centrality increases the efficacy of the vaccination strategies by up to 80%.
Collapse
|
14
|
Inference of hyperedges and overlapping communities in hypergraphs. Nat Commun 2022; 13:7229. [PMID: 36433942 PMCID: PMC9700742 DOI: 10.1038/s41467-022-34714-7] [Citation(s) in RCA: 12] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/18/2022] [Accepted: 11/02/2022] [Indexed: 11/27/2022] Open
Abstract
Hypergraphs, encoding structured interactions among any number of system units, have recently proven a successful tool to describe many real-world biological and social networks. Here we propose a framework based on statistical inference to characterize the structural organization of hypergraphs. The method allows to infer missing hyperedges of any size in a principled way, and to jointly detect overlapping communities in presence of higher-order interactions. Furthermore, our model has an efficient numerical implementation, and it runs faster than dyadic algorithms on pairwise records projected from higher-order data. We apply our method to a variety of real-world systems, showing strong performance in hyperedge prediction tasks, detecting communities well aligned with the information carried by interactions, and robustness against addition of noisy hyperedges. Our approach illustrates the fundamental advantages of a hypergraph probabilistic model when modeling relational systems with higher-order interactions.
Collapse
|
15
|
Modelling time-varying interactions in complex systems: the Score Driven Kinetic Ising Model. Sci Rep 2022; 12:19339. [PMID: 36369262 PMCID: PMC9652375 DOI: 10.1038/s41598-022-23770-0] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/30/2022] [Accepted: 11/04/2022] [Indexed: 11/13/2022] Open
Abstract
A common issue when analyzing real-world complex systems is that the interactions between their elements often change over time. Here we propose a new modeling approach for time-varying interactions generalising the well-known Kinetic Ising Model, a minimalistic pairwise constant interactions model which has found applications in several scientific disciplines. Keeping arbitrary choices of dynamics to a minimum and seeking information theoretical optimality, the Score-Driven methodology allows to extract from data and interpret the presence of temporal patterns describing time-varying interactions. We identify a parameter whose value at a given time can be directly associated with the local predictability of the dynamics and we introduce a method to dynamically learn its value from the data, without specifying parametrically the system's dynamics. We extend our framework to disentangle different sources (e.g. endogenous vs exogenous) of predictability in real time, and show how our methodology applies to a variety of complex systems such as financial markets, temporal (social) networks, and neuronal populations.
Collapse
|
16
|
Luo Y, Li Y, Cheng C. Cooperative evolution with opinion formation in a complex social environment. CHAOS (WOODBURY, N.Y.) 2022; 32:103123. [PMID: 36319276 DOI: 10.1063/5.0090831] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/09/2022] [Accepted: 09/09/2022] [Indexed: 06/16/2023]
Abstract
Cooperation is a significant aspect in the daily activities of human or animal populations that involves the process of agents making decisions based in part on the ideas or beliefs of cooperators. The importance of communication in the evolutionary game cannot be overstated. In this paper, we offer a co-evolutionary game model on a communication network, including expressed and private opinions. Then, we present our theoretical analysis of scenarios characterized by different parameters, elucidating the relationship between the agents' opinion formation process and the decision-making process. Finally, we run simulations with our proposed model. Surprisingly, we discover that whereas communication does not increase cooperation on Erdös-Rényi random networks, it does so on the Barabási-Albert scale-free network. Meanwhile, we discover that in the simulation results, the average of private opinions (simplified as values within [0,1]) changes in the same direction of the percentage of cooperators. Furthermore, we discover that deceivers who conceal their true private opinions may, to some extent, foster the formation of collaboration in the human population, which goes against our common sense.
Collapse
Affiliation(s)
- Yun Luo
- School of Computer Science and Technology, Zhejiang University, Hangzhou 310024, People's Republic of China
| | - Yuke Li
- School of Engineering, Westlake Institute for Advanced Study, Hangzhou 310000, People's Republic of China
| | - Chun Cheng
- School of Information Science and Technology, Nantong University, Nantong 226019, People's Republic of China
| |
Collapse
|
17
|
Liu R, Zhang S, Zhang D, Zhang X, Bao X. Node Importance Identification for Temporal Networks Based on Optimized Supra-Adjacency Matrix. ENTROPY (BASEL, SWITZERLAND) 2022; 24:1391. [PMID: 37420410 DOI: 10.3390/e24101391] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/17/2022] [Revised: 09/09/2022] [Accepted: 09/26/2022] [Indexed: 07/09/2023]
Abstract
The research on node importance identification for temporal networks has attracted much attention. In this work, combined with the multi-layer coupled network analysis method, an optimized supra-adjacency matrix (OSAM) modeling method was proposed. In the process of constructing an optimized super adjacency matrix, the intra-layer relationship matrixes were improved by introducing the edge weight. The inter-layer relationship matrixes were formed by improved similarly and the inter-layer relationship is directional by using the characteristics of directed graphs. The model established by the OSAM method accurately expresses the structure of the temporal network and considers the influence of intra- and inter-layer relationships on the importance of nodes. In addition, an index was calculated by the average of the sum of the eigenvector centrality indices for a node in each layer and the node importance sorted list was obtained from this index to express the global importance of nodes in temporal networks. The experimental results on three real temporal network datasets Enron, Emaildept3, and Workspace showed that compared with the SAM and the SSAM methods, the OSAM method has a faster message propagation rate and larger message coverage and better SIR and NDCG@10 indicators.
Collapse
Affiliation(s)
- Rui Liu
- School of Information Engineering, Nanchang Hangkong University, 696 Fenghe South Avenue, Nanchang 330063, China
| | - Sheng Zhang
- School of Information Engineering, Nanchang Hangkong University, 696 Fenghe South Avenue, Nanchang 330063, China
| | - Donghui Zhang
- School of Information Engineering, Nanchang Hangkong University, 696 Fenghe South Avenue, Nanchang 330063, China
| | - Xuefeng Zhang
- School of Information Engineering, Nanchang Hangkong University, 696 Fenghe South Avenue, Nanchang 330063, China
| | - Xiaoling Bao
- School of Foreign Language, Nanchang Hangkong University, 696 Fenghe South Avenue, Nanchang 330063, China
| |
Collapse
|
18
|
Erkol Ş, Mazzilli D, Radicchi F. Effective submodularity of influence maximization on temporal networks. Phys Rev E 2022; 106:034301. [PMID: 36266883 DOI: 10.1103/physreve.106.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: 05/11/2022] [Accepted: 08/16/2022] [Indexed: 06/16/2023]
Abstract
We study influence maximization on temporal networks. This is a special setting where the influence function is not submodular, and there is no optimality guarantee for solutions achieved via greedy optimization. We perform an exhaustive analysis on both real and synthetic networks. We show that the influence function of randomly sampled sets of seeds often violates the necessary conditions for submodularity. However, when sets of seeds are selected according to the greedy optimization strategy, the influence function behaves effectively as a submodular function. Specifically, violations of the necessary conditions for submodularity are never observed in real networks, and only rarely in synthetic ones. The direct comparison with exact solutions obtained via brute-force search indicates that the greedy strategy provides approximate solutions that are well within the optimality gap guaranteed for strictly submodular functions. Greedy optimization appears, therefore, to be an effective strategy for the maximization of influence on temporal networks.
Collapse
Affiliation(s)
- Şirag Erkol
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| | - Dario Mazzilli
- Enrico Fermi Research Center, Via Panisperna 89 A, Rome, Italy
| | - Filippo Radicchi
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| |
Collapse
|
19
|
Dynamic relational event modeling: Testing, exploring, and applying. PLoS One 2022; 17:e0272309. [PMID: 35913924 PMCID: PMC9342787 DOI: 10.1371/journal.pone.0272309] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/22/2022] [Accepted: 07/18/2022] [Indexed: 11/19/2022] Open
Abstract
The relational event model (REM) facilitates the study of network evolution in relational event history data, i.e., time-ordered sequences of social interactions. In real-life social networks it is likely that network effects, i.e., the parameters that quantify the relative importance of drivers of these social interaction sequences, change over time. In these networks, the basic REM is not appropriate to understand what drives network evolution. This research extends the REM framework with approaches for testing and exploring time-varying network effects. First, we develop a Bayesian approach to test whether network effects change during the study period. We conduct a simulation study that illustrates that the Bayesian test accurately quantifies the evidence between a basic (‘static’) REM or a dynamic REM. Secondly, in the case of the latter, time-varying network effects can be studied by means of a moving window that slides over the relational event history. A simulation study was conducted that illustrates that the accuracy and precision of the estimates depend on the window width: narrower windows result in greater accuracy at the cost of lower precision. Third, we develop a Bayesian approach for determining window widths using the empirical network data and conduct a simulation study that illustrates that estimation with empirically determined window widths achieves both good accuracy for time intervals with important changes and good precision for time intervals with hardly any changes in the effects. Finally, in an empirical application, we illustrate how the approaches in this research can be used to test for and explore time-varying network effects of face-to-face contacts at the workplace.
Collapse
|
20
|
Peng H, Qian C, Zhao D, Zhong M, Han J, Wang W. Targeting attack hypergraph networks. CHAOS (WOODBURY, N.Y.) 2022; 32:073121. [PMID: 35907733 DOI: 10.1063/5.0090626] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/08/2022] [Accepted: 06/27/2022] [Indexed: 06/15/2023]
Abstract
In modern systems, from brain neural networks to social group networks, pairwise interactions are not sufficient to express higher-order relationships. The smallest unit of their internal function is not composed of a single functional node but results from multiple functional nodes acting together. Therefore, researchers adopt the hypergraph to describe complex systems. The targeted attack on random hypergraph networks is still a problem worthy of study. This work puts forward a theoretical framework to analyze the robustness of random hypergraph networks under the background of a targeted attack on nodes with high or low hyperdegrees. We discovered the process of cascading failures and the giant connected cluster (GCC) of the hypergraph network under targeted attack by associating the simple mapping of the factor graph with the hypergraph and using percolation theory and generating function. On random hypergraph networks, we do Monte-Carlo simulations and find that the theoretical findings match the simulation results. Similarly, targeted attacks are more effective than random failures in disintegrating random hypergraph networks. The threshold of the hypergraph network grows as the probability of high hyperdegree nodes being deleted increases, indicating that the network's resilience becomes more fragile. When considering real-world scenarios, our conclusions are validated by real-world hypergraph networks. These findings will help us understand the impact of the hypergraph's underlying structure on network resilience.
Collapse
Affiliation(s)
- Hao Peng
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
| | - Cheng Qian
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
| | - Dandan Zhao
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
| | - Ming Zhong
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
| | - Jianmin Han
- College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua 321004, China
| | - Wei Wang
- School of Public Health, Chongqing Medical University, Chongqing 400016, China
| |
Collapse
|
21
|
Piaggesi S, Panisson A. Time-varying graph representation learning via higher-order skip-gram with negative sampling. EPJ DATA SCIENCE 2022; 11:33. [PMID: 35668814 PMCID: PMC9143726 DOI: 10.1140/epjds/s13688-022-00344-8] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 06/11/2021] [Accepted: 05/09/2022] [Indexed: 06/15/2023]
Abstract
UNLABELLED Representation learning models for graphs are a successful family of techniques that project nodes into feature spaces that can be exploited by other machine learning algorithms. Since many real-world networks are inherently dynamic, with interactions among nodes changing over time, these techniques can be defined both for static and for time-varying graphs. Here, we show how the skip-gram embedding approach can be generalized to perform implicit tensor factorization on different tensor representations of time-varying graphs. We show that higher-order skip-gram with negative sampling (HOSGNS) is able to disentangle the role of nodes and time, with a small fraction of the number of parameters needed by other approaches. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned representations outperform state-of-the-art methods when used to solve downstream tasks such as network reconstruction. Good performance on predicting the outcome of dynamical processes such as disease spreading shows the potential of this method to estimate contagion risk, providing early risk awareness based on contact tracing data. SUPPLEMENTARY INFORMATION The online version contains supplementary material available at 10.1140/epjds/s13688-022-00344-8.
Collapse
Affiliation(s)
- Simone Piaggesi
- Alma Mater Studiorum University of Bologna, Bologna, Italy
- ISI Foundation, Turin, Italy
| | | |
Collapse
|
22
|
Vaca-Ramírez F, Peixoto TP. Systematic assessment of the quality of fit of the stochastic block model for empirical networks. Phys Rev E 2022; 105:054311. [PMID: 35706168 DOI: 10.1103/physreve.105.054311] [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/06/2022] [Accepted: 04/19/2022] [Indexed: 06/15/2023]
Abstract
We perform a systematic analysis of the quality of fit of the stochastic block model (SBM) for 275 empirical networks spanning a wide range of domains and orders of size magnitude. We employ posterior predictive model checking as a criterion to assess the quality of fit, which involves comparing networks generated by the inferred model with the empirical network, according to a set of network descriptors. We observe that the SBM is capable of providing an accurate description for the majority of networks considered, but falls short of saturating all modeling requirements. In particular, networks possessing a large diameter and slow-mixing random walks tend to be badly described by the SBM. However, contrary to what is often assumed, networks with a high abundance of triangles can be well described by the SBM in many cases. We demonstrate that simple network descriptors can be used to evaluate whether or not the SBM can provide a sufficiently accurate representation, potentially pointing to possible model extensions that can systematically improve the expressiveness of this class of models.
Collapse
Affiliation(s)
- Felipe Vaca-Ramírez
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| | - Tiago P Peixoto
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| |
Collapse
|
23
|
Guo X, Gupta A, Sampat A, Zhai C. A stochastic contact network model for assessing outbreak risk of COVID-19 in workplaces. PLoS One 2022; 17:e0262316. [PMID: 35030206 PMCID: PMC8759694 DOI: 10.1371/journal.pone.0262316] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/13/2021] [Accepted: 12/20/2021] [Indexed: 12/19/2022] Open
Abstract
The COVID-19 pandemic has drastically shifted the way people work. While many businesses can operate remotely, a large number of jobs can only be performed on-site. Moreover as businesses create plans for bringing workers back on-site, they are in need of tools to assess the risk of COVID-19 for their employees in the workplaces. This study aims to fill the gap in risk modeling of COVID-19 outbreaks in facilities like offices and warehouses. We propose a simulation-based stochastic contact network model to assess the cumulative incidence in workplaces. First-generation cases are introduced as a Bernoulli random variable using the local daily new case rate as the success rate. Contact networks are established through randomly sampled daily contacts for each of the first-generation cases and successful transmissions are established based on a randomized secondary attack rate (SAR). Modification factors are provided for SAR based on changes in airflow, speaking volume, and speaking activity within a facility. Control measures such as mask wearing are incorporated through modifications in SAR. We validated the model by comparing the distribution of cumulative incidence in model simulations against real-world outbreaks in workplaces and nursing homes. The comparisons support the model's validity for estimating cumulative incidences for short forecasting periods of up to 15 days. We believe that the current study presents an effective tool for providing short-term forecasts of COVID-19 cases for workplaces and for quantifying the effectiveness of various control measures. The open source model code is made available at github.com/abhineetgupta/covid-workplace-risk.
Collapse
Affiliation(s)
- Xi Guo
- One Concern, Inc., Menlo Park, CA, United States of America
| | - Abhineet Gupta
- One Concern, Inc., Menlo Park, CA, United States of America
| | - Anand Sampat
- One Concern, Inc., Menlo Park, CA, United States of America
| | - Chengwei Zhai
- One Concern, Inc., Menlo Park, CA, United States of America
| |
Collapse
|
24
|
Zhang S, Zhao X, Wang H. Mitigate SIR epidemic spreading via contact blocking in temporal networks. APPLIED NETWORK SCIENCE 2022; 7:2. [PMID: 35013715 PMCID: PMC8733442 DOI: 10.1007/s41109-021-00436-w] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 05/24/2021] [Accepted: 10/31/2021] [Indexed: 06/14/2023]
Abstract
Progress has been made in how to suppress epidemic spreading on temporal networks via blocking all contacts of targeted nodes or node pairs. In this work, we develop contact blocking strategies that remove a fraction of contacts from a temporal (time evolving) human contact network to mitigate the spread of a Susceptible-Infected-Recovered epidemic. We define the probability that a contact c(i, j, t) is removed as a function of a given centrality metric of the corresponding link l(i, j) in the aggregated network and the time t of the contact. The aggregated network captures the number of contacts between each node pair. A set of 12 link centrality metrics have been proposed and each centrality metric leads to a unique contact removal strategy. These strategies together with a baseline strategy (random removal) are evaluated in empirical contact networks via the average prevalence, the peak prevalence and the time to reach the peak prevalence. We find that the epidemic spreading can be mitigated the best when contacts between node pairs that have fewer contacts and early contacts are more likely to be removed. A strategy tends to perform better when the average number contacts removed from each node pair varies less. The aggregated pruned network resulted from the best contact removal strategy tends to have a large largest eigenvalue, a large modularity and probably a small largest connected component size.
Collapse
Affiliation(s)
- Shilun Zhang
- Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands
| | - Xunyi Zhao
- Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands
| | - Huijuan Wang
- Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands
| |
Collapse
|
25
|
Potter GE, Carnegie NB, Sugimoto JD, Diallo A, Victor JC, Neuzil KM, Halloran ME. Using social contact data to improve the overall effect estimate of a cluster-randomized influenza vaccination program in Senegal. J R Stat Soc Ser C Appl Stat 2022; 71:70-90. [PMID: 35721226 PMCID: PMC9202735 DOI: 10.1111/rssc.12522] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 01/03/2023]
Abstract
This study estimates the overall effect of two influenza vaccination programs consecutively administered in a cluster-randomized trial in western Senegal over the course of two influenza seasons from 2009-2011. We apply cutting-edge methodology combining social contact data with infection data to reduce bias in estimation arising from contamination between clusters. Our time-varying estimates reveal a reduction in seasonal influenza from the intervention and a nonsignificant increase in H1N1 pandemic influenza. We estimate an additive change in overall cumulative incidence (which was 6.13% in the control arm) of -0.68 percentage points during Year 1 of the study (95% CI: -2.53, 1.18). When H1N1 pandemic infections were excluded from analysis, the estimated change was -1.45 percentage points and was significant (95% CI, -2.81, -0.08). Because cross-cluster contamination was low (0-3% of contacts for most villages), an estimator assuming no contamination was only slightly attenuated (-0.65 percentage points). These findings are encouraging for studies carefully designed to minimize spillover. Further work is needed to estimate contamination - and its effect on estimation - in a variety of settings.
Collapse
Affiliation(s)
- Gail E. Potter
- National Institute of Allergy and Infectious Diseases, National Institutes of Health, and the Emmes Company, Rockville Maryland, USA
| | | | - Jonathan D. Sugimoto
- University of Washington and Epidemiologic Research and Information Center, Veterans Affairs Puget Sound Health Care System and Fred Hutchinson Cancer Research Center, Seattle Washington, USA
| | - Aldiouma Diallo
- Institut de Recherche pour le Développement, Niakhar Senegal
| | | | | | - M. Elizabeth Halloran
- University of Washington Department of Biostatistics and Fred Hutchinson Cancer Research Center, Seattle Washington, USA
| |
Collapse
|
26
|
Abstract
AbstractTemporal graphs are structures which model relational data between entities that change over time. Due to the complex structure of data, mining statistically significant temporal subgraphs, also known as temporal motifs, is a challenging task. In this work, we present an efficient technique for extracting temporal motifs in temporal networks. Our method is based on the novel notion of egocentric temporal neighborhoods, namely multi-layer structures centered on an ego node. Each temporal layer of the structure consists of the first-order neighborhood of the ego node, and corresponding nodes in sequential layers are connected by an edge. The strength of this approach lies in the possibility of encoding these structures into a unique bit vector, thus bypassing the problem of graph isomorphism in searching for temporal motifs. This allows our algorithm to mine substantially larger motifs with respect to alternative approaches. Furthermore, by bringing the focus on the temporal dynamics of the interactions of a specific node, our model allows to mine temporal motifs which are visibly interpretable. Experiments on a number of complex networks of social interactions confirm the advantage of the proposed approach over alternative non-egocentric solutions. The egocentric procedure is indeed more efficient in revealing similarities and discrepancies among different social environments, independently of the different technologies used to collect data, which instead affect standard non-egocentric measures.
Collapse
|
27
|
Mauras S, Cohen-Addad V, Duboc G, Dupré la Tour M, Frasca P, Mathieu C, Opatowski L, Viennot L. Mitigating COVID-19 outbreaks in workplaces and schools by hybrid telecommuting. PLoS Comput Biol 2021; 17:e1009264. [PMID: 34437531 PMCID: PMC8389398 DOI: 10.1371/journal.pcbi.1009264] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/04/2021] [Accepted: 07/10/2021] [Indexed: 12/23/2022] Open
Abstract
The COVID-19 epidemic has forced most countries to impose contact-limiting restrictions at workplaces, universities, schools, and more broadly in our societies. Yet, the effectiveness of these unprecedented interventions in containing the virus spread remain largely unquantified. Here, we develop a simulation study to analyze COVID-19 outbreaks on three real-life contact networks stemming from a workplace, a primary school and a high school in France. Our study provides a fine-grained analysis of the impact of contact-limiting strategies at workplaces, schools and high schools, including: (1) Rotating strategies, in which workers are evenly split into two shifts that alternate on a daily or weekly basis; and (2) On-Off strategies, where the whole group alternates periods of normal work interactions with complete telecommuting. We model epidemics spread in these different setups using a stochastic discrete-time agent-based transmission model that includes the coronavirus most salient features: super-spreaders, infectious asymptomatic individuals, and pre-symptomatic infectious periods. Our study yields clear results: the ranking of the strategies, based on their ability to mitigate epidemic propagation in the network from a first index case, is the same for all network topologies (workplace, primary school and high school). Namely, from best to worst: Rotating week-by-week, Rotating day-by-day, On-Off week-by-week, and On-Off day-by-day. Moreover, our results show that below a certain threshold for the original local reproduction number [Formula: see text] within the network (< 1.52 for primary schools, < 1.30 for the workplace, < 1.38 for the high school, and < 1.55 for the random graph), all four strategies efficiently control outbreak by decreasing effective local reproduction number to [Formula: see text] < 1. These results can provide guidance for public health decisions related to telecommuting.
Collapse
Affiliation(s)
| | | | | | | | - Paolo Frasca
- Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, Gipsa-lab, Grenoble, France
| | | | - Lulla Opatowski
- Université Paris-Saclay, UVSQ, Univ. Paris-Sud, Inserm, CESP, Anti-infective evasion and pharmacoepidemiology team, Montigny-Le-Bretonneux, France
- Institut Pasteur, Epidemiology and Modelling of Antibiotic Evasion unit (EMEA), Paris, France
| | | |
Collapse
|
28
|
Colman E, Colizza V, Hanks EM, Hughes DP, Bansal S. Social fluidity mobilizes contagion in human and animal populations. eLife 2021; 10:62177. [PMID: 34328080 PMCID: PMC8324292 DOI: 10.7554/elife.62177] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/17/2020] [Accepted: 06/25/2021] [Indexed: 11/13/2022] Open
Abstract
Humans and other group-living animals tend to distribute their social effort disproportionately. Individuals predominantly interact with a small number of close companions while maintaining weaker social bonds with less familiar group members. By incorporating this behavior into a mathematical model, we find that a single parameter, which we refer to as social fluidity, controls the rate of social mixing within the group. Large values of social fluidity correspond to gregarious behavior, whereas small values signify the existence of persistent bonds between individuals. We compare the social fluidity of 13 species by applying the model to empirical human and animal social interaction data. To investigate how social behavior influences the likelihood of an epidemic outbreak, we derive an analytical expression of the relationship between social fluidity and the basic reproductive number of an infectious disease. For species that form more stable social bonds, the model describes frequency-dependent transmission that is sensitive to changes in social fluidity. As social fluidity increases, animal-disease systems become increasingly density-dependent. Finally, we demonstrate that social fluidity is a stronger predictor of disease outcomes than both group size and connectivity, and it provides an integrated framework for both density-dependent and frequency-dependent transmission.
Collapse
Affiliation(s)
- Ewan Colman
- Department of Biology, Georgetown University, Washington, United States.,Roslin Institute, University of Edinburgh, Midlothian, United Kingdom
| | - Vittoria Colizza
- INSERM, Sorbonne Université, Institut Pierre Louis d'Épidémiologie et de Santé Publique (IPLESP UMRS 1136), F75012, Paris, France
| | - Ephraim M Hanks
- Department of Statistics, Eberly College of Science, Penn State University, State College, United States
| | - David P Hughes
- Department of Entomology, College of Agricultural Sciences, Penn State University, State College, United States
| | - Shweta Bansal
- Department of Biology, Georgetown University, Washington, United States
| |
Collapse
|
29
|
Presigny C, Holme P, Barrat A. Building surrogate temporal network data from observed backbones. Phys Rev E 2021; 103:052304. [PMID: 34134319 DOI: 10.1103/physreve.103.052304] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/23/2020] [Accepted: 04/22/2021] [Indexed: 11/07/2022]
Abstract
Many systems of socioeconomic interests find a convenient representation in the form of temporal networks, i.e., sets of nodes and interactions occurring at specified times. In the corresponding data sets, however, crucial elements coexist with nonessential ones and noise. Several methods have thus been proposed to extract a "network backbone," i.e., the set of most important links in a network data set. The outcome of such methods can be seen as compressed versions of the original data. However, the question of how to practically use such reduced views of the data has not been tackled: for instance, using them directly in numerical simulations of processes on networks might lead to important biases. Overall, such reduced views of the data might not be actionable without an adequate decompression method. Here, we address this issue by putting forward and exploring several systematic procedures to build surrogate data from various kinds of temporal network backbones. In particular, we explore how much information about the original data needs to be retained alongside the backbone so that the surrogate data can be used in data-driven numerical simulations of spreading processes on a wide range of spreading parameters. We illustrate our results using empirical temporal networks with a broad variety of structures and properties. Our results give hints on how to best summarize complex data sets so that they remain actionable. Moreover, they show how ensembles of surrogate data with similar properties can be obtained from an original single data set, without any modeling assumptions.
Collapse
Affiliation(s)
- Charley Presigny
- Aix Marseille Univ, Université de Toulon, CNRS, CPT, Turing Center for Living Systems, 13288 Marseille, France
| | - Petter Holme
- Tokyo Tech World Research Hub Initiative (WRHI), Tokyo Institute of Technology, Yokohama 226-8503, Japan
| | - Alain Barrat
- Aix Marseille Univ, Université de Toulon, CNRS, CPT, Turing Center for Living Systems, 13288 Marseille, France.,Tokyo Tech World Research Hub Initiative (WRHI), Tokyo Institute of Technology, Yokohama 226-8503, Japan
| |
Collapse
|
30
|
Li B, Saad D. Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis. Phys Rev E 2021; 103:052303. [PMID: 34134317 DOI: 10.1103/physreve.103.052303] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/02/2020] [Accepted: 04/19/2021] [Indexed: 01/12/2023]
Abstract
Infectious diseases that incorporate presymptomatic transmission are challenging to monitor, model, predict, and contain. We address this scenario by studying a variant of a stochastic susceptible-exposed-infected-recovered model on arbitrary network instances using an analytical framework based on the method of dynamic message passing. This framework provides a good estimate of the probabilistic evolution of the spread on both static and contact networks, offering a significantly improved accuracy with respect to individual-based mean-field approaches while requiring a much lower computational cost compared to numerical simulations. It facilitates the derivation of epidemic thresholds, which are phase boundaries separating parameter regimes where infections can be effectively contained from those where they cannot. These have clear implications on different containment strategies through topological (reducing contacts) and infection parameter changes (e.g., social distancing and wearing face masks), with relevance to the recent COVID-19 pandemic.
Collapse
Affiliation(s)
- Bo Li
- Non-linearity and Complexity Research Group, Aston University, Birmingham, B4 7ET, United Kingdom
| | - David Saad
- Non-linearity and Complexity Research Group, Aston University, Birmingham, B4 7ET, United Kingdom
| |
Collapse
|
31
|
Kim H, Jo HH, Jeong H. Impact of environmental changes on the dynamics of temporal networks. PLoS One 2021; 16:e0250612. [PMID: 33909631 PMCID: PMC8081251 DOI: 10.1371/journal.pone.0250612] [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: 08/17/2020] [Accepted: 04/10/2021] [Indexed: 11/20/2022] Open
Abstract
Dynamics of complex social systems has often been described in the framework of temporal networks, where links are considered to exist only at the moment of interaction between nodes. Such interaction patterns are not only driven by internal interaction mechanisms, but also affected by environmental changes. To investigate the impact of the environmental changes on the dynamics of temporal networks, we analyze several face-to-face interaction datasets using the multiscale entropy (MSE) method to find that the observed temporal correlations can be categorized according to the environmental similarity of datasets such as classes and break times in schools. By devising and studying a temporal network model considering a periodically changing environment as well as a preferential activation mechanism, we numerically show that our model could successfully reproduce various empirical results by the MSE method in terms of multiscale temporal correlations. Our results demonstrate that the environmental changes can play an important role in shaping the dynamics of temporal networks when the interactions between nodes are influenced by the environment of the systems.
Collapse
Affiliation(s)
- Hyewon Kim
- Asia Pacific Center for Theoretical Physics, Pohang, Republic of Korea
| | - Hang-Hyun Jo
- Asia Pacific Center for Theoretical Physics, Pohang, Republic of Korea
- Department of Physics, The Catholic University of Korea, Bucheon, Republic of Korea
| | - Hawoong Jeong
- Department of Physics, Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea
- Center for Complex Systems, Korea Advanced Institute of Science and Technology, Daejeon, Republic of Korea
- * E-mail:
| |
Collapse
|
32
|
Cencetti G, Battiston F, Lepri B, Karsai M. Temporal properties of higher-order interactions in social networks. Sci Rep 2021; 11:7028. [PMID: 33782492 PMCID: PMC8007734 DOI: 10.1038/s41598-021-86469-8] [Citation(s) in RCA: 19] [Impact Index Per Article: 6.3] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/07/2020] [Accepted: 03/08/2021] [Indexed: 12/25/2022] Open
Abstract
Human social interactions in local settings can be experimentally detected by recording the physical proximity and orientation of people. Such interactions, approximating face-to-face communications, can be effectively represented as time varying social networks with links being unceasingly created and destroyed over time. Traditional analyses of temporal networks have addressed mostly pairwise interactions, where links describe dyadic connections among individuals. However, many network dynamics are hardly ascribable to pairwise settings but often comprise larger groups, which are better described by higher-order interactions. Here we investigate the higher-order organizations of temporal social networks by analyzing five publicly available datasets collected in different social settings. We find that higher-order interactions are ubiquitous and, similarly to their pairwise counterparts, characterized by heterogeneous dynamics, with bursty trains of rapidly recurring higher-order events separated by long periods of inactivity. We investigate the evolution and formation of groups by looking at the transition rates between different higher-order structures. We find that in more spontaneous social settings, group are characterized by slower formation and disaggregation, while in work settings these phenomena are more abrupt, possibly reflecting pre-organized social dynamics. Finally, we observe temporal reinforcement suggesting that the longer a group stays together the higher the probability that the same interaction pattern persist in the future. Our findings suggest the importance of considering the higher-order structure of social interactions when investigating human temporal dynamics.
Collapse
Affiliation(s)
- Giulia Cencetti
- Mobs Lab, Fondazione Bruno Kessler, Via Sommarive 18, 38123, Trento, Italy
| | - Federico Battiston
- Department of Network and Data Science, Central European University, 1100, Vienna, Austria
| | - Bruno Lepri
- Mobs Lab, Fondazione Bruno Kessler, Via Sommarive 18, 38123, Trento, Italy
| | - Márton Karsai
- Department of Network and Data Science, Central European University, 1100, Vienna, Austria.
| |
Collapse
|
33
|
Kobayashi T, Génois M. The switching mechanisms of social network densification. Sci Rep 2021; 11:3160. [PMID: 33542332 PMCID: PMC7862646 DOI: 10.1038/s41598-021-82432-9] [Citation(s) in RCA: 3] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/18/2020] [Accepted: 01/20/2021] [Indexed: 11/09/2022] Open
Abstract
Densification and sparsification of social networks are attributed to two fundamental mechanisms: a change in the population in the system, and/or a change in the chances that people in the system are connected. In theory, each of these mechanisms generates a distinctive type of densification scaling, but in reality both types are generally mixed. Here, we develop a Bayesian statistical method to identify the extent to which each of these mechanisms is at play at a given point in time, taking the mixed densification scaling as input. We apply the method to networks of face-to-face interactions of individuals and reveal that the main mechanism that causes densification and sparsification occasionally switches, the frequency of which depending on the social context. The proposed method uncovers an inherent regime-switching property of network dynamics, which will provide a new insight into the mechanics behind evolving social interactions.
Collapse
Affiliation(s)
- Teruyoshi Kobayashi
- Department of Economics, Kobe University, Kobe, Japan. .,Center for Computational Social Science, Kobe University, Kobe, Japan.
| | - Mathieu Génois
- CNRS, CPT, Aix Marseille Univ, Université de Toulon, Marseille, France. .,GESIS, Leibniz Institute for the Social Sciences, Köln/Mannheim, Germany.
| |
Collapse
|
34
|
Clark RA, Macdonald M. Identification of effective spreaders in contact networks using dynamical influence. APPLIED NETWORK SCIENCE 2021; 6:5. [PMID: 33490367 PMCID: PMC7814176 DOI: 10.1007/s41109-021-00351-0] [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/22/2020] [Accepted: 01/02/2021] [Indexed: 06/12/2023]
Abstract
Contact networks provide insights on disease spread due to the duration of close proximity interactions. For systems governed by consensus dynamics, network structure is key to optimising the spread of information. For disease spread over contact networks, the structure would be expected to be similarly influential. However, metrics that are essentially agnostic to the network's structure, such as weighted degree (strength) centrality and its variants, perform near-optimally in selecting effective spreaders. These degree-based metrics outperform eigenvector centrality, despite disease spread over a network being a random walk process. This paper improves eigenvector-based spreader selection by introducing the non-linear relationship between contact time and the probability of disease transmission into the assessment of network dynamics. This approximation of disease spread dynamics is achieved by altering the Laplacian matrix, which in turn highlights why nodes with a high degree are such influential disease spreaders. From this approach, a trichotomy emerges on the definition of an effective spreader where, for susceptible-infected simulations, eigenvector-based selections can either optimise the initial rate of infection, the average rate of infection, or produce the fastest time to full infection of the network. Simulated and real-world human contact networks are examined, with insights also drawn on the effective adaptation of ant colony contact networks to reduce pathogen spread and protect the queen ant.
Collapse
Affiliation(s)
- Ruaridh A. Clark
- Department of Electronic and Electrical Engineering, University of Strathclyde, George Street, Glasgow, UK
| | - Malcolm Macdonald
- Department of Electronic and Electrical Engineering, University of Strathclyde, George Street, Glasgow, UK
| |
Collapse
|
35
|
Kobayashi T, Génois M. Two types of densification scaling in the evolution of temporal networks. Phys Rev E 2020; 102:052302. [PMID: 33327108 DOI: 10.1103/physreve.102.052302] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/11/2020] [Accepted: 10/18/2020] [Indexed: 11/07/2022]
Abstract
Many real-world social networks constantly change their global properties over time, such as the number of edges, size, and density. While temporal and local properties of social networks have been extensively studied, the origin of their dynamical nature is not yet well understood. Networks may grow or shrink if (a) the total population of nodes changes and/or (b) the chance of two nodes being connected varies over time. Here, we develop a method that allows us to classify the source of time-varying nature of temporal networks. In doing so, we first show empirical evidence that real-world dynamical systems could be categorized into two classes, the difference of which is characterized by the way the number of edges grows with the number of active nodes, i.e., densification scaling. We develop a dynamic hidden-variable model to formally characterize the two dynamical classes. The model is fitted to the empirical data to identify whether the origin of scaling comes from a changing population in the system or shifts in the connecting probabilities.
Collapse
Affiliation(s)
- Teruyoshi Kobayashi
- Department of Economics, Kobe University, Kobe, Japan and Center for Computational Social Science, Kobe University, Kobe, Japan
| | - Mathieu Génois
- CNRS, CPT, Aix-Marseille Université, Université de Toulon, Marseille, France and GESIS, Leibniz Institute for the Social Sciences, Köln/Mannheim, Germany
| |
Collapse
|
36
|
Individual variations lead to universal and cross-species patterns of social behavior. Proc Natl Acad Sci U S A 2020; 117:31754-31759. [PMID: 33257554 DOI: 10.1073/pnas.2002013117] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/18/2022] Open
Abstract
The duration of interaction events in a society is a fundamental measure of its collective nature and potentially reflects variability in individual behavior. Here we performed a high-throughput measurement of trophallaxis and face-to-face event durations experienced by a colony of honeybees over their entire lifetimes. The interaction time distribution is heavy-tailed, as previously reported for human face-to-face interactions. We developed a theory of pair interactions that takes into account individual variability and predicts the scaling behavior for both bee and extant human datasets. The individual variability of worker honeybees was nonzero but less than that of humans, possibly reflecting their greater genetic relatedness. Our work shows how individual differences can lead to universal patterns of behavior that transcend species and specific mechanisms for social interactions.
Collapse
|
37
|
Erkol Ş, Mazzilli D, Radicchi F. Influence maximization on temporal networks. Phys Rev E 2020; 102:042307. [PMID: 33212670 DOI: 10.1103/physreve.102.042307] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/02/2020] [Accepted: 09/14/2020] [Indexed: 11/07/2022]
Abstract
We consider the optimization problem of seeding a spreading process on a temporal network so that the expected size of the resulting outbreak is maximized. We frame the problem for a spreading process following the rules of the susceptible-infected-recovered model with temporal scale equal to the one characterizing the evolution of the network topology. We perform a systematic analysis based on a corpus of 12 real-world temporal networks and quantify the performance of solutions to the influence maximization problem obtained using different level of information about network topology and dynamics. We find that having perfect knowledge of the network topology but in a static and/or aggregated form is not helpful in solving the influence maximization problem effectively. Knowledge, even if partial, of the early stages of the network dynamics appears instead essential for the identification of quasioptimal sets of influential spreaders.
Collapse
Affiliation(s)
- Şirag Erkol
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| | - Dario Mazzilli
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| | - Filippo Radicchi
- Center for Complex Networks and Systems Research, Luddy School of Informatics, Computing, and Engineering, Indiana University, Bloomington, Indiana 47408, USA
| |
Collapse
|
38
|
Rodríguez-Flores MA, Papadopoulos F. Hyperbolic mapping of human proximity networks. Sci Rep 2020; 10:20244. [PMID: 33219308 PMCID: PMC7679465 DOI: 10.1038/s41598-020-77277-7] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/04/2020] [Accepted: 11/09/2020] [Indexed: 11/25/2022] Open
Abstract
Human proximity networks are temporal networks representing the close-range proximity among humans in a physical space. They have been extensively studied in the past 15 years as they are critical for understanding the spreading of diseases and information among humans. Here we address the problem of mapping human proximity networks into hyperbolic spaces. Each snapshot of these networks is often very sparse, consisting of a small number of interacting (i.e., non-zero degree) nodes. Yet, we show that the time-aggregated representation of such systems over sufficiently large periods can be meaningfully embedded into the hyperbolic space, using methods developed for traditional (non-mobile) complex networks. We justify this compatibility theoretically and validate it experimentally. We produce hyperbolic maps of six different real systems, and show that the maps can be used to identify communities, facilitate efficient greedy routing on the temporal network, and predict future links with significant precision. Further, we show that epidemic arrival times are positively correlated with the hyperbolic distance from the infection sources in the maps. Thus, hyperbolic embedding could also provide a new perspective for understanding and predicting the behavior of epidemic spreading in human proximity systems.
Collapse
Affiliation(s)
- Marco A Rodríguez-Flores
- Department of Electrical Engineering, Computer Engineering and Informatics, Cyprus University of Technology, Limassol, 3036, Cyprus
| | - Fragkiskos Papadopoulos
- Department of Electrical Engineering, Computer Engineering and Informatics, Cyprus University of Technology, Limassol, 3036, Cyprus.
| |
Collapse
|
39
|
Fernandes S, Fanaee-T H, Gama J. Tensor decomposition for analysing time-evolving social networks: an overview. Artif Intell Rev 2020. [DOI: 10.1007/s10462-020-09916-4] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/02/2023]
|
40
|
Nadini M, Zino L, Rizzo A, Porfiri M. A multi-agent model to study epidemic spreading and vaccination strategies in an urban-like environment. APPLIED NETWORK SCIENCE 2020; 5:68. [PMID: 32984500 PMCID: PMC7506211 DOI: 10.1007/s41109-020-00299-7] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 04/14/2020] [Accepted: 08/03/2020] [Indexed: 06/11/2023]
Abstract
Worldwide urbanization calls for a deeper understanding of epidemic spreading within urban environments. Here, we tackle this problem through an agent-based model, in which agents move in a two-dimensional physical space and interact according to proximity criteria. The planar space comprises several locations, which represent bounded regions of the urban space. Based on empirical evidence, we consider locations of different density and place them in a core-periphery structure, with higher density in the central areas and lower density in the peripheral ones. Each agent is assigned to a base location, which represents where their home is. Through analytical tools and numerical techniques, we study the formation mechanism of the network of contacts, which is characterized by the emergence of heterogeneous interaction patterns. We put forward an extensive simulation campaign to analyze the onset and evolution of contagious diseases spreading in the urban environment. Interestingly, we find that, in the presence of a core-periphery structure, the diffusion of the disease is not affected by the time agents spend inside their base location before leaving it, but it is influenced by their motion outside their base location: a strong tendency to return to the base location favors the spreading of the disease. A simplified one-dimensional version of the model is examined to gain analytical insight into the spreading process and support our numerical findings. Finally, we investigate the effectiveness of vaccination campaigns, supporting the intuition that vaccination in central and dense areas should be prioritized.
Collapse
Affiliation(s)
- Matthieu Nadini
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, 11201 USA
| | - Lorenzo Zino
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, 11201 USA
- Faculty of Science and Engineering, University of Groningen, Groningen, 9747 AG The Netherlands
| | - Alessandro Rizzo
- Dipartimento di Elettronica e Telecomunicazioni, Politecnico di Torino, Torino, 10129 Italy
- Office of Innovation, New York University Tandon School of Engineering, New York, 11201 USA
| | - Maurizio Porfiri
- Department of Mechanical and Aerospace Engineering, New York University Tandon School of Engineering, Brooklyn, 11201 USA
- Department of Biomedical Engineering, New York University Tandon School of Engineering, Brooklyn, 11201 USA
| |
Collapse
|
41
|
Relevance of temporal cores for epidemic spread in temporal networks. Sci Rep 2020; 10:12529. [PMID: 32719352 PMCID: PMC7385111 DOI: 10.1038/s41598-020-69464-3] [Citation(s) in RCA: 9] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/19/2020] [Accepted: 07/07/2020] [Indexed: 11/08/2022] Open
Abstract
Temporal networks are widely used to represent a vast diversity of systems, including in particular social interactions, and the spreading processes unfolding on top of them. The identification of structures playing important roles in such processes remains largely an open question, despite recent progresses in the case of static networks. Here, we consider as candidate structures the recently introduced concept of span-cores: the span-cores decompose a temporal network into subgraphs of controlled duration and increasing connectivity, generalizing the core-decomposition of static graphs. To assess the relevance of such structures, we explore the effectiveness of strategies aimed either at containing or maximizing the impact of a spread, based respectively on removing span-cores of high cohesiveness or duration to decrease the epidemic risk, or on seeding the process from such structures. The effectiveness of such strategies is assessed in a variety of empirical data sets and compared to baselines that use only static information on the centrality of nodes and static concepts of coreness, as well as to a baseline based on a temporal centrality measure. Our results show that the most stable and cohesive temporal cores play indeed an important role in epidemic processes on temporal networks, and that their nodes are likely to include influential spreaders.
Collapse
|
42
|
The Role of Bedroom Privacy in Social Interaction among Elderly Residents in Nursing Homes: An Exploratory Case Study of Hong Kong. SENSORS 2020; 20:s20154101. [PMID: 32717901 PMCID: PMC7436271 DOI: 10.3390/s20154101] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 05/30/2020] [Revised: 07/15/2020] [Accepted: 07/20/2020] [Indexed: 11/17/2022]
Abstract
Privacy is often overlooked in Hong Kong nursing homes with the majority of elderly residents living in shared bedrooms of three to five people. Only a few studies have used Bluetooth low energy indoor positioning systems to explore the relationship between privacy and social interaction among elderly residents. The study investigates the social behavioural patterns of elderly residents living in three-bed, four-bed, and five-bed rooms in a nursing home. Location data of 50 residents were used for the identification of mobility and social interaction patterns in relation to different degrees of privacy and tested for statistical significance. Privacy is found to have a weak negative correlation with mobility patterns and social behaviour, implying that the more privacy there is, the less mobility and more formal interaction is found. Residents who had more privacy did not spend more time in social space. Residents living in bedrooms that opened directly onto social space had higher social withdrawal tendencies, indicating the importance of transitional spaces between private and public areas. Friends’ rooms were used extensively by residents who had little privacy, however, the concept of friends’ rooms have rarely been discussed in nursing homes. There is evidence supporting the importance of privacy for social interaction. Future study directions include considering how other design factors, such as configuration and social space diversity, work with privacy to influence social interaction.
Collapse
|
43
|
A joint optimization framework for better community detection based on link prediction in social networks. Knowl Inf Syst 2020. [DOI: 10.1007/s10115-020-01490-z] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/23/2022]
|
44
|
Aleta A, Ferraz de Arruda G, Moreno Y. Data-driven contact structures: From homogeneous mixing to multilayer networks. PLoS Comput Biol 2020; 16:e1008035. [PMID: 32673307 PMCID: PMC7386617 DOI: 10.1371/journal.pcbi.1008035] [Citation(s) in RCA: 14] [Impact Index Per Article: 3.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/17/2020] [Revised: 07/28/2020] [Accepted: 06/09/2020] [Indexed: 12/22/2022] Open
Abstract
The modeling of the spreading of communicable diseases has experienced significant advances in the last two decades or so. This has been possible due to the proliferation of data and the development of new methods to gather, mine and analyze it. A key role has also been played by the latest advances in new disciplines like network science. Nonetheless, current models still lack a faithful representation of all possible heterogeneities and features that can be extracted from data. Here, we bridge a current gap in the mathematical modeling of infectious diseases and develop a framework that allows to account simultaneously for both the connectivity of individuals and the age-structure of the population. We compare different scenarios, namely, i) the homogeneous mixing setting, ii) one in which only the social mixing is taken into account, iii) a setting that considers the connectivity of individuals alone, and finally, iv) a multilayer representation in which both the social mixing and the number of contacts are included in the model. We analytically show that the thresholds obtained for these four scenarios are different. In addition, we conduct extensive numerical simulations and conclude that heterogeneities in the contact network are important for a proper determination of the epidemic threshold, whereas the age-structure plays a bigger role beyond the onset of the outbreak. Altogether, when it comes to evaluate interventions such as vaccination, both sources of individual heterogeneity are important and should be concurrently considered. Our results also provide an indication of the errors incurred in situations in which one cannot access all needed information in terms of connectivity and age of the population.
Collapse
Affiliation(s)
| | | | - Yamir Moreno
- ISI Foundation, Turin, Italy
- Institute for Biocomputation and Physics of Complex Systems (BIFI), University of Zaragoza, Zaragoza, Spain
- Department of Theoretical Physics, University of Zaragoza, Zaragoza, Spain
| |
Collapse
|
45
|
Li A, Zhou L, Su Q, Cornelius SP, Liu YY, Wang L, Levin SA. Evolution of cooperation on temporal networks. Nat Commun 2020; 11:2259. [PMID: 32385279 PMCID: PMC7210286 DOI: 10.1038/s41467-020-16088-w] [Citation(s) in RCA: 35] [Impact Index Per Article: 8.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/28/2019] [Accepted: 04/04/2020] [Indexed: 11/28/2022] Open
Abstract
Population structure is a key determinant in fostering cooperation among naturally self-interested individuals in microbial populations, social insect groups, and human societies. Traditional research has focused on static structures, and yet most real interactions are finite in duration and changing in time, forming a temporal network. This raises the question of whether cooperation can emerge and persist despite an intrinsically fragmented population structure. Here we develop a framework to study the evolution of cooperation on temporal networks. Surprisingly, we find that network temporality actually enhances the evolution of cooperation relative to comparable static networks, despite the fact that bursty interaction patterns generally impede cooperation. We resolve this tension by proposing a measure to quantify the amount of temporality in a network, revealing an intermediate level that maximally boosts cooperation. Our results open a new avenue for investigating the evolution of cooperation and other emergent behaviours in more realistic structured populations. Population structure enables emergence of cooperation among individuals, but the impact of the dynamic nature of real interaction networks is not understood. Here, the authors study the evolution of cooperation on temporal networks and find that temporality enhances the evolution of cooperation.
Collapse
Affiliation(s)
- Aming Li
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Zoology and Department of Biochemistry, University of Oxford, Oxford, OX1 3PS, UK.,Center for Complex Network Research and Department of Physics, Northeastern University, Boston, MA, 02115, USA
| | - Lei Zhou
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, 08544, USA
| | - Qi Su
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.,Department of Mathematics and Department of Biology, University of Pennsylvania, Philadelphia, PA, 19104, USA
| | - Sean P Cornelius
- Center for Complex Network Research and Department of Physics, Northeastern University, Boston, MA, 02115, USA.,Department of Physics, Ryerson University, Toronto, ON, M5B 2K3, Canada.,Channing Division of Network Medicine, Brigham and Women's Hospital, Harvard Medical School, Boston, MA, 02115, USA
| | - Yang-Yu Liu
- Channing Division of Network Medicine, Brigham and Women's Hospital, Harvard Medical School, Boston, MA, 02115, USA. .,Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA, 02115, USA.
| | - Long Wang
- Center for Systems and Control, College of Engineering, Peking University, Beijing, 100871, China.
| | - Simon A Levin
- Department of Ecology and Evolutionary Biology, Princeton University, Princeton, NJ, 08544, USA.
| |
Collapse
|
46
|
Okada M, Yamanishi K, Masuda N. Long-tailed distributions of inter-event times as mixtures of exponential distributions. ROYAL SOCIETY OPEN SCIENCE 2020; 7:191643. [PMID: 32257326 PMCID: PMC7062064 DOI: 10.1098/rsos.191643] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 09/25/2019] [Accepted: 01/28/2020] [Indexed: 06/11/2023]
Abstract
Inter-event times of various human behaviour are apparently non-Poissonian and obey long-tailed distributions as opposed to exponential distributions, which correspond to Poisson processes. It has been suggested that human individuals may switch between different states, in each of which they are regarded to generate events obeying a Poisson process. If this is the case, inter-event times should approximately obey a mixture of exponential distributions with different parameter values. In the present study, we introduce the minimum description length principle to compare mixtures of exponential distributions with different numbers of components (i.e. constituent exponential distributions). Because these distributions violate the identifiability property, one is mathematically not allowed to apply the Akaike or Bayes information criteria to their maximum-likelihood estimator to carry out model selection. We overcome this theoretical barrier by applying a minimum description principle to joint likelihoods of the data and latent variables. We show that mixtures of exponential distributions with a few components are selected, as opposed to more complex mixtures in various datasets, and that the fitting accuracy is comparable to that of state-of-the-art algorithms to fit power-law distributions to data. Our results lend support to Poissonian explanations of apparently non-Poissonian human behaviour.
Collapse
Affiliation(s)
- Makoto Okada
- Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo Bunkyo, Tokyo 113-8656, Japan
| | - Kenji Yamanishi
- Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo Bunkyo, Tokyo 113-8656, Japan
| | - Naoki Masuda
- Department of Engineering Mathematics, University of Bristol, Woodland Road, Clifton, Bristol BS8 1UB, UK
- Department of Mathematics, University at Buffalo, State University of New York, Buffalo, NY 14260-2900, USA
- Computational and Data-Enabled Science and Engineering Program, University at Buffalo, State University of New York, Buffalo, NY 14260-5030, USA
| |
Collapse
|
47
|
Colman E, Holme P, Sayama H, Gershenson C. Efficient sentinel surveillance strategies for preventing epidemics on networks. PLoS Comput Biol 2019; 15:e1007517. [PMID: 31765382 PMCID: PMC6910701 DOI: 10.1371/journal.pcbi.1007517] [Citation(s) in RCA: 10] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/10/2019] [Revised: 12/13/2019] [Accepted: 10/29/2019] [Indexed: 12/17/2022] Open
Abstract
Surveillance plays a crucial role in preventing emerging infectious diseases from becoming epidemic. In circumstances where it is possible to monitor the infection status of certain people, transport hubs, or hospitals, early detection of the disease allows interventions to be implemented before most of the damage can occur, or at least its impact can be mitigated. This paper addresses the question of which nodes we should select in a network of individuals susceptible to some infectious disease in order to minimize the number of casualties. By simulating disease outbreaks on a collection of empirical and synthetic networks we show that the best strategy depends on topological characteristics of the network. For highly modular or spatially embedded networks it is better to place the sentinels on nodes distributed across different regions. However, if the degree heterogeneity is high, then a strategy that targets network hubs is preferred. We further consider the consequences of having an incomplete sample of the network and demonstrate that the value of new information diminishes as more data is collected. Finally we find further marginal improvements using two heuristics informed by known results in graph theory that exploit the fragmented structure of sparse network data. In a network of individuals susceptible to some infectious disease, what are the best locations to monitor in order to detect the infection before most damage can be done? In this paper we address this question by considering various heuristic strategies for sentinel placement that can potentially be implemented in real-world situations without requiring excessive amounts of computation, or even having perfect data about the structure of the network. We find that strategies that attempt to distribute sentinels over different regions of the network perform best in highly modular or spatially embedded networks, whereas the strategy of targeting the most well connected individuals works best when there is a considerable amount of contact heterogeneity between individuals. Our results may be used as a guideline to help decide when certain strategies should, or should not, be implemented.
Collapse
Affiliation(s)
- Ewan Colman
- Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, CDMX, Mexico
- * E-mail:
| | - Petter Holme
- Tokyo Tech World Research Hub Initiative (WRHI), Institute of Innovative Research, Tokyo Institute of Technology, Japan
| | - Hiroki Sayama
- Center for Collective Dynamics of Complex Systems, State University of New York at Binghamton, Binghamton, New York, United States of America
- Waseda Innovation Lab, Waseda University, Tokyo, Japan
| | - Carlos Gershenson
- Centro de Ciencias de la Complejidad, Universidad Nacional Autónoma de México, CDMX, Mexico
- Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas, Universidad Nacional Autónoma de México, CDMX, Mexico
- ITMO University, St. Petersburg, Russian Federation
| |
Collapse
|
48
|
Papadopoulos F, Flores MAR. Latent geometry and dynamics of proximity networks. Phys Rev E 2019; 100:052313. [PMID: 31870016 DOI: 10.1103/physreve.100.052313] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/02/2019] [Indexed: 06/10/2023]
Abstract
Proximity networks are time-varying graphs representing the closeness among humans moving in a physical space. Their properties have been extensively studied in the past decade as they critically affect the behavior of spreading phenomena and the performance of routing algorithms. Yet the mechanisms responsible for their observed characteristics remain elusive. Here we show that many of the observed properties of proximity networks emerge naturally and simultaneously in a simple latent space network model, called dynamic-S^{1}. The dynamic-S^{1} does not model node mobility directly but captures the connectivity in each snapshot-each snapshot in the model is a realization of the S^{1} model of traditional complex networks, which is isomorphic to hyperbolic geometric graphs. By forgoing the motion component the model facilitates mathematical analysis, allowing us to prove the contact, intercontact, and weight distributions. We show that these distributions are power laws in the thermodynamic limit with exponents lying within the ranges observed in real systems. Interestingly, we find that network temperature plays a central role in network dynamics, dictating the exponents of these distributions, the time-aggregated agent degrees, and the formation of unique and recurrent components. Further, we show that paradigmatic epidemic and rumor-spreading processes perform similarly in real and modeled networks. The dynamic-S^{1} or extensions of it may apply to other types of time-varying networks and constitute the basis of maximum likelihood estimation methods that infer the node coordinates and their evolution in the latent spaces of real systems.
Collapse
Affiliation(s)
- Fragkiskos Papadopoulos
- Department of Electrical Engineering, Computer Engineering and Informatics, Cyprus University of Technology, 3036 Limassol, Cyprus
| | - Marco Antonio Rodríguez Flores
- Department of Electrical Engineering, Computer Engineering and Informatics, Cyprus University of Technology, 3036 Limassol, Cyprus
| |
Collapse
|
49
|
Weijs-Perrée M, Appel-Meulenbroek R, Arentze T. Analysing knowledge sharing behaviour in business centres: a mixed multinomial logit model. KNOWLEDGE MANAGEMENT RESEARCH & PRACTICE 2019. [DOI: 10.1080/14778238.2019.1664269] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/06/2023]
Affiliation(s)
- Minou Weijs-Perrée
- Urban Systems & Real Estate, Department of the Built Environment, Eindhoven University of Technology, Eindhoven, MB, Netherlands
| | - Rianne Appel-Meulenbroek
- Urban Systems & Real Estate, Department of the Built Environment, Eindhoven University of Technology, Eindhoven, MB, Netherlands
| | - Theo Arentze
- Urban Systems & Real Estate, Department of the Built Environment, Eindhoven University of Technology, Eindhoven, MB, Netherlands
| |
Collapse
|
50
|
Locating the Epidemic Source in Complex Networks with Sparse Observers. APPLIED SCIENCES-BASEL 2019. [DOI: 10.3390/app9183644] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
Epidemic source localization is one of the most meaningful areas of research in complex networks, which helps solve the problem of infectious disease spread. Limited by incomplete information of nodes and inevitable randomness of the spread process, locating the epidemic source becomes a little difficult. In this paper, we propose an efficient algorithm via Bayesian Estimation to locate the epidemic source and find the initial time in complex networks with sparse observers. By modeling the infected time of observers, we put forward a valid epidemic source localization method for tree network and further extend it to the general network via maximum spanning tree. The numerical analyses in synthetic networks and empirical networks show that our algorithm has a higher source localization accuracy than other comparison algorithms. In particular, when the randomness of the spread path enhances, our algorithm has a better performance. We believe that our method can provide an effective reference for epidemic spread and source localization in complex networks.
Collapse
|