1
|
Kim JH, Goh KI. Higher-Order Components Dictate Higher-Order Contagion Dynamics in Hypergraphs. PHYSICAL REVIEW LETTERS 2024; 132:087401. [PMID: 38457718 DOI: 10.1103/physrevlett.132.087401] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/15/2022] [Revised: 11/13/2023] [Accepted: 01/25/2024] [Indexed: 03/10/2024]
Abstract
The presence of the giant component is a necessary condition for the emergence of collective behavior in complex networked systems. Unlike networks, hypergraphs have an important native feature that components of hypergraphs might be of higher order, which could be defined in terms of the number of common nodes shared between hyperedges. Although the extensive higher-order component (HOC) could be witnessed ubiquitously in real-world hypergraphs, the role of the giant HOC in collective behavior on hypergraphs has yet to be elucidated. In this Letter, we demonstrate that the presence of the giant HOC fundamentally alters the outbreak patterns of higher-order contagion dynamics on real-world hypergraphs. Most crucially, the giant HOC is required for the higher-order contagion to invade globally from a single seed. We confirm it by using synthetic random hypergraphs containing adjustable and analytically calculable giant HOC.
Collapse
Affiliation(s)
- Jung-Ho Kim
- Department of Physics, Korea University, Seoul 02841, Korea
| | - K-I Goh
- Department of Physics, Korea University, Seoul 02841, Korea
- Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095, USA
| |
Collapse
|
2
|
Lai Y, Liu Y, Zheng K, Wang W. Robustness of interdependent higher-order networks. CHAOS (WOODBURY, N.Y.) 2023; 33:073121. [PMID: 37433652 DOI: 10.1063/5.0152480] [Citation(s) in RCA: 2] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/30/2023] [Accepted: 06/19/2023] [Indexed: 07/13/2023]
Abstract
In real complex systems, interactions occur not only between a pair of nodes, but also in groups of three or more nodes, which can be abstracted as higher-order structures in the networks. The simplicial complex is one of a model to represent systems with both low-order and higher-order structures. In this paper, we study the robustness of interdependent simplicial complexes under random attacks, where the complementary effects of the higher-order structure are introduced. When a higher-order node in a 2-simplex fails, its dependent node in the other layer survives with a certain probability due to the complementary effects from the 2-simplex. By using the percolation method, we derive the percolation threshold and the size of the giant component when the cascading failure reaches its steady state. The simulation results agree well with analytical predictions. We find that the type of phase transition changes from the first-order to the second-order when the complementary effect of the higher-order structure on the dependent node increases or the number of 2-simplices in the interdependent simplicial complex increases. While the interlayer coupling strength increases, the type of phase transition changes from the second-order to the first-order. In particular, even if the higher-order interactions do not provide complementary effects for dependent nodes, the robustness of the interdependent heterogeneous simplicial complex is higher than that of the ordinary interdependent network with the same average degree due to the existence of 2-simplices in the system. This study furthers our understanding in the robustness of interdependent higher-order networks.
Collapse
Affiliation(s)
- Yuhang Lai
- School of Computer Science, Southwest Petroleum University, Chengdu 610500, China
| | - Ying Liu
- School of Computer Science, Southwest Petroleum University, Chengdu 610500, China
- Department of Physics, University of Fribourg, Fribourg 1700, Switzerland
| | - Kexian Zheng
- School of Computer Science, Southwest Petroleum University, Chengdu 610500, China
| | - Wei Wang
- School of Public Health and Management, Chongqing Medical University, Chongqing 400016, China
| |
Collapse
|
3
|
The dynamic nature of percolation on networks with triadic interactions. Nat Commun 2023; 14:1308. [PMID: 36894591 PMCID: PMC9998640 DOI: 10.1038/s41467-023-37019-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: 10/09/2022] [Accepted: 02/24/2023] [Indexed: 03/11/2023] Open
Abstract
Percolation establishes the connectivity of complex networks and is one of the most fundamental critical phenomena for the study of complex systems. On simple networks, percolation displays a second-order phase transition; on multiplex networks, the percolation transition can become discontinuous. However, little is known about percolation in networks with higher-order interactions. Here, we show that percolation can be turned into a fully fledged dynamical process when higher-order interactions are taken into account. By introducing signed triadic interactions, in which a node can regulate the interactions between two other nodes, we define triadic percolation. We uncover that in this paradigmatic model the connectivity of the network changes in time and that the order parameter undergoes a period doubling and a route to chaos. We provide a general theory for triadic percolation which accurately predicts the full phase diagram on random graphs as confirmed by extensive numerical simulations. We find that triadic percolation on real network topologies reveals a similar phenomenology. These results radically change our understanding of percolation and may be used to study complex systems in which the functional connectivity is changing in time dynamically and in a non-trivial way, such as in neural and climate networks.
Collapse
|
4
|
Giambagli L, Calmon L, Muolo R, Carletti T, Bianconi G. Diffusion-driven instability of topological signals coupled by the Dirac operator. Phys Rev E 2022; 106:064314. [PMID: 36671168 DOI: 10.1103/physreve.106.064314] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/17/2022] [Accepted: 11/30/2022] [Indexed: 12/24/2022]
Abstract
The study of reaction-diffusion systems on networks is of paramount relevance for the understanding of nonlinear processes in systems where the topology is intrinsically discrete, such as the brain. Until now, reaction-diffusion systems have been studied only when species are defined on the nodes of a network. However, in a number of real systems including, e.g., the brain and the climate, dynamical variables are not only defined on nodes but also on links, faces, and higher-dimensional cells of simplicial or cell complexes, leading to topological signals. In this work, we study reaction-diffusion processes of topological signals coupled through the Dirac operator. The Dirac operator allows topological signals of different dimension to interact or cross-diffuse as it projects the topological signals defined on simplices or cells of a given dimension to simplices or cells of one dimension up or one dimension down. By focusing on the framework involving nodes and links, we establish the conditions for the emergence of Turing patterns and we show that the latter are never localized only on nodes or only on links of the network. Moreover, when the topological signals display a Turing pattern their projection does as well. We validate the theory hereby developed on a benchmark network model and on square lattices with periodic boundary conditions.
Collapse
Affiliation(s)
- Lorenzo Giambagli
- Department of Physics and Astronomy, University of Florence, INFN & CSDC, Sesto Fiorentino, Italy.,Department of Mathematics & naXys, Namur Institute for Complex Systems, University of Namur, Rue Grafé 2, B5000 Namur, Belgium
| | - Lucille Calmon
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
| | - Riccardo Muolo
- Department of Mathematics & naXys, Namur Institute for Complex Systems, University of Namur, Rue Grafé 2, B5000 Namur, Belgium.,Department of Applied Mathematics, Mathematical Institute Federal University of Rio de Janeiro, Avenida Athos da Silveira Ramos, 149, Rio de Janeiro 21941-909, Brazil
| | - Timoteo Carletti
- Department of Mathematics & naXys, Namur Institute for Complex Systems, University of Namur, Rue Grafé 2, B5000 Namur, Belgium
| | - Ginestra Bianconi
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom.,The Alan Turing Institute, 96 Euston Road, London NW1 2DB, United Kingdom
| |
Collapse
|
5
|
Majhi S, Perc M, Ghosh D. Dynamics on higher-order networks: a review. J R Soc Interface 2022; 19:20220043. [PMID: 35317647 PMCID: PMC8941407 DOI: 10.1098/rsif.2022.0043] [Citation(s) in RCA: 73] [Impact Index Per Article: 36.5] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/16/2022] [Accepted: 02/18/2022] [Indexed: 12/25/2022] Open
Abstract
Network science has evolved into an indispensable platform for studying complex systems. But recent research has identified limits of classical networks, where links connect pairs of nodes, to comprehensively describe group interactions. Higher-order networks, where a link can connect more than two nodes, have therefore emerged as a new frontier in network science. Since group interactions are common in social, biological and technological systems, higher-order networks have recently led to important new discoveries across many fields of research. Here, we review these works, focusing in particular on the novel aspects of the dynamics that emerges on higher-order networks. We cover a variety of dynamical processes that have thus far been studied, including different synchronization phenomena, contagion processes, the evolution of cooperation and consensus formation. We also outline open challenges and promising directions for future research.
Collapse
Affiliation(s)
- Soumen Majhi
- Department of Mathematics, Bar-Ilan University, Ramat-Gan 5290002, Israel
| | - Matjaž Perc
- Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, 2000 Maribor, Slovenia
- Department of Medical Research, China Medical University Hospital, China Medical University, Taichung, Taiwan
- Complexity Science Hub Vienna, Josefstödter Straße 39, 1080 Vienna, Austria
- Alma Mater Europaea, Slovenska ulica 17, 2000 Maribor, Slovenia
| | - Dibakar Ghosh
- Physics and Applied Mathematics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata 700108, India
| |
Collapse
|
6
|
A hands-on tutorial on network and topological neuroscience. Brain Struct Funct 2022; 227:741-762. [PMID: 35142909 PMCID: PMC8930803 DOI: 10.1007/s00429-021-02435-0] [Citation(s) in RCA: 8] [Impact Index Per Article: 4.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/18/2021] [Accepted: 11/23/2021] [Indexed: 02/08/2023]
Abstract
The brain is an extraordinarily complex system that facilitates the optimal integration of information from different regions to execute its functions. With the recent advances in technology, researchers can now collect enormous amounts of data from the brain using neuroimaging at different scales and from numerous modalities. With that comes the need for sophisticated tools for analysis. The field of network neuroscience has been trying to tackle these challenges, and graph theory has been one of its essential branches through the investigation of brain networks. Recently, topological data analysis has gained more attention as an alternative framework by providing a set of metrics that go beyond pairwise connections and offer improved robustness against noise. In this hands-on tutorial, our goal is to provide the computational tools to explore neuroimaging data using these frameworks and to facilitate their accessibility, data visualisation, and comprehension for newcomers to the field. We will start by giving a concise (and by no means complete) overview of the field to introduce the two frameworks and then explain how to compute both well-established and newer metrics on resting-state functional magnetic resonance imaging. We use an open-source language (Python) and provide an accompanying publicly available Jupyter Notebook that uses the 1000 Functional Connectomes Project dataset. Moreover, we would like to highlight one part of our notebook dedicated to the realistic visualisation of high order interactions in brain networks. This pipeline provides three-dimensional (3-D) plots of pairwise and higher-order interactions projected in a brain atlas, a new feature tailor-made for network neuroscience.
Collapse
|
7
|
Jhun B. Topological analysis of the latent geometry of a complex network. CHAOS (WOODBURY, N.Y.) 2022; 32:013116. [PMID: 35105131 DOI: 10.1063/5.0073107] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/27/2021] [Accepted: 12/16/2021] [Indexed: 06/14/2023]
Abstract
Most real-world networks are embedded in latent geometries. If a node in a network is found in the vicinity of another node in the latent geometry, the two nodes have a disproportionately high probability of being connected by a link. The latent geometry of a complex network is a central topic of research in network science, which has an expansive range of practical applications, such as efficient navigation, missing link prediction, and brain mapping. Despite the important role of topology in the structures and functions of complex systems, little to no study has been conducted to develop a method to estimate the general unknown latent geometry of complex networks. Topological data analysis, which has attracted extensive attention in the research community owing to its convincing performance, can be directly implemented into complex networks; however, even a small fraction (0.1%) of long-range links can completely erase the topological signature of the latent geometry. Inspired by the fact that long-range links in a network have disproportionately high loads, we develop a set of methods that can analyze the latent geometry of a complex network: the modified persistent homology diagram and the map of the latent geometry. These methods successfully reveal the topological properties of the synthetic and empirical networks used to validate the proposed methods.
Collapse
Affiliation(s)
- Bukyoung Jhun
- CCSS, CTP, and Department of Physics and Astronomy, Seoul National University, Seoul 08826, South Korea and Department of Physics, The University of Texas at Austin, Austin, Texas 78712, USA
| |
Collapse
|
8
|
Millán AP, Ghorbanchian R, Defenu N, Battiston F, Bianconi G. Local topological moves determine global diffusion properties of hyperbolic higher-order networks. Phys Rev E 2021; 104:054302. [PMID: 34942729 DOI: 10.1103/physreve.104.054302] [Citation(s) in RCA: 7] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/26/2021] [Accepted: 10/13/2021] [Indexed: 12/18/2022]
Abstract
From social interactions to the human brain, higher-order networks are key to describe the underlying network geometry and topology of many complex systems. While it is well known that network structure strongly affects its function, the role that network topology and geometry has on the emerging dynamical properties of higher-order networks is yet to be clarified. In this perspective, the spectral dimension plays a key role since it determines the effective dimension for diffusion processes on a network. Despite its relevance, a theoretical understanding of which mechanisms lead to a finite spectral dimension, and how this can be controlled, still represents a challenge and is the object of intense research. Here, we introduce two nonequilibrium models of hyperbolic higher-order networks and we characterize their network topology and geometry by investigating the intertwined appearance of small-world behavior, δ-hyperbolicity, and community structure. We show that different topological moves, determining the nonequilibrium growth of the higher-order hyperbolic network models, induce tuneable values of the spectral dimension, showing a rich phenomenology which is not displayed in random graph ensembles. In particular, we observe that, if the topological moves used to construct the higher-order network increase the area/volume ratio, then the spectral dimension continuously decreases, while the opposite effect is observed if the topological moves decrease the area/volume ratio. Our work reveals a new link between the geometry of a network and its diffusion properties, contributing to a better understanding of the complex interplay between network structure and dynamics.
Collapse
Affiliation(s)
- Ana P Millán
- Amsterdam UMC, Vrije Universiteit Amsterdam, Department of Clinical Neurophysiology and MEG Center, Amsterdam Neuroscience, De Boelelaan 1117, Amsterdam, The Netherlands
| | - Reza Ghorbanchian
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, E1 4NS, London, United Kingdom
| | - Nicolò Defenu
- Institute for Theoretical Physics, ETH Zürich Wolfgang-Pauli-Str. 27, 8093 Zurich, Switzerland
| | - Federico Battiston
- Department of Network and Data Science, Central European University, 1100 Vienna, Austria
| | - Ginestra Bianconi
- School of Mathematical Sciences, Queen Mary University of London, Mile End Road, E1 4NS, London, United Kingdom.,The Alan Turing Institute, British Library, 96 Euston Road, NW1 2DB, London, United Kingdom
| |
Collapse
|
9
|
Sun H, Bianconi G. Higher-order percolation processes on multiplex hypergraphs. Phys Rev E 2021; 104:034306. [PMID: 34654130 DOI: 10.1103/physreve.104.034306] [Citation(s) in RCA: 22] [Impact Index Per Article: 7.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/12/2021] [Accepted: 08/19/2021] [Indexed: 11/07/2022]
Abstract
Higher-order interactions are increasingly recognized as a fundamental aspect of complex systems ranging from the brain to social contact networks. Hypergraphs as well as simplicial complexes capture the higher-order interactions of complex systems and allow us to investigate the relation between their higher-order structure and their function. Here we establish a general framework for assessing hypergraph robustness and we characterize the critical properties of simple and higher-order percolation processes. This general framework builds on the formulation of the random multiplex hypergraph ensemble where each layer is characterized by hyperedges of given cardinality. We observe that in presence of the structural cutoff the ensemble of multiplex hypergraphs can be mapped to an ensemble of multiplex bipartite networks. We reveal the relation between higher-order percolation processes in random multiplex hypergraphs, interdependent percolation of multiplex networks, and K-core percolation. The structural correlations of the random multiplex hypergraphs are shown to have a significant effect on their percolation properties. The wide range of critical behaviors observed for higher-order percolation processes on multiplex hypergraphs elucidates the mechanisms responsible for the emergence of discontinuous transition and uncovers interesting critical properties which can be applied to the study of epidemic spreading and contagion processes on higher-order networks.
Collapse
Affiliation(s)
- Hanlin Sun
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
| | - Ginestra Bianconi
- School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom.,The Alan Turing Institute, The British Library, 96 Euston Road, London NW1 2DB, United Kingdom
| |
Collapse
|
10
|
Lee J, Lee Y, Oh SM, Kahng B. Betweenness centrality of teams in social networks. CHAOS (WOODBURY, N.Y.) 2021; 31:061108. [PMID: 34241328 DOI: 10.1063/5.0056683] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.7] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/12/2021] [Accepted: 06/01/2021] [Indexed: 06/13/2023]
Abstract
Betweenness centrality (BC) was proposed as an indicator of the extent of an individual's influence in a social network. It is measured by counting how many times a vertex (i.e., an individual) appears on all the shortest paths between pairs of vertices. A question naturally arises as to how the influence of a team or group in a social network can be measured. Here, we propose a method of measuring this influence on a bipartite graph comprising vertices (individuals) and hyperedges (teams). When the hyperedge size varies, the number of shortest paths between two vertices in a hypergraph can be larger than that in a binary graph. Thus, the power-law behavior of the team BC distribution breaks down in scale-free hypergraphs. However, when the weight of each hyperedge, for example, the performance per team member, is counted, the team BC distribution is found to exhibit power-law behavior. We find that a team with a widely connected member is highly influential.
Collapse
Affiliation(s)
- Jongshin Lee
- CCSS, CTP, Department of Physics and Astronomy, Seoul National University, Seoul 08826, South Korea
| | - Yongsun Lee
- CCSS, CTP, Department of Physics and Astronomy, Seoul National University, Seoul 08826, South Korea
| | - Soo Min Oh
- CCSS, CTP, Department of Physics and Astronomy, Seoul National University, Seoul 08826, South Korea
| | - B Kahng
- CCSS, CTP, Department of Physics and Astronomy, Seoul National University, Seoul 08826, South Korea
| |
Collapse
|