An official website of the United States government
Network data has become widespread, larger, and more complex over the years. Traditional network data is dyadic, capturing the relations among pairs of entities. With the need to model interactions among more than two entities, significant research has focused on higher-order networks and ways to represent, analyze, and learn from them. There are two main directions to studying higher-order networks. One direction has focused on capturing higher-order patterns in traditional (dyadic) graphs by changing the basic unit of study from nodes to small frequently observed subgraphs, called motifs. As most existing network data comes in the form of pairwise dyadic relationships, studying higher-order structures within such graphs may uncover new insights. The second direction aims to directly model higher-order interactions using new and more complex representations such as simplicial complexes or hypergraphs. Some of these models have long been proposed, but improvements in computational power and the advent of new computational techniques have increased their popularity. Our goal in this paper is to provide a succinct yet comprehensive summary of the advanced higher-order network analysis techniques. We provide a systematic review of the foundations and algorithms, along with use cases and applications of higher-order networks in various scientific domains.
more »
« less
A simplicial epidemic model for COVID-19 spread analysis
Networks allow us to describe a wide range of interaction phenomena that occur in complex systems arising in such diverse fields of knowledge as neuroscience, engineering, ecology, finance, and social sciences. Until very recently, the primary focus of network models and tools has been on describing the pairwise relationships between system entities. However, increasingly more studies indicate that polyadic or higher-order group relationships among multiple network entities may be the key toward better understanding of the intrinsic mechanisms behind the functionality of complex systems. Such group interactions can be, in turn, described in a holistic manner by simplicial complexes of graphs. Inspired by these recently emerging results on the utility of the simplicial geometry of complex networks for contagion propagation and armed with a large-scale synthetic social contact network (also known as a digital twin) of the population in the U.S. state of Virginia, in this paper, we aim to glean insights into the role of higher-order social interactions and the associated varying social group determinants on COVID-19 propagation and mitigation measures.
more »
« less
- PAR ID:
- 10496147
- Publisher / Repository:
- PNAS
- Date Published:
- Journal Name:
- Proceedings of the National Academy of Sciences
- Volume:
- 121
- Issue:
- 1
- ISSN:
- 0027-8424
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Simplicial neural networks (SNNs) have recently emerged as a new direction in graph learning which expands the idea of convolutional architectures from node space to simplicial complexes on graphs. Instead of predominantly assessing pairwise relations among nodes as in the current practice, simplicial complexes allow us to describe higher-order interactions and multi-node graph structures. By building upon connection between the convolution operation and the new block Hodge-Laplacian, we propose the first SNN for link prediction. Our new Block Simplicial Complex Neural Networks (BScNets) model generalizes existing graph convolutional network (GCN) frameworks by systematically incorporating salient interactions among multiple higher-order graph structures of different dimensions. We discuss theoretical foundations behind BScNets and illustrate its utility for link prediction on eight real-world and synthetic datasets. Our experiments indicate that BScNets outperforms the state-of-the-art models by a significant margin while maintaining low computation costs. Finally, we show utility of BScNets as a new promising alternative for tracking spread of infectious diseases such as COVID-19 and measuring the effectiveness of the healthcare risk mitigation strategies.more » « less
-
Multilayer networks continue to gain significant attention in many areas of study, particularly due to their high utility in modeling interdependent systems such as critical infrastructures, human brain connectome, and socioenvironmental ecosystems. However, clustering of multilayer networks, especially using the information on higher-order interactions of the system entities, still remains in its infancy. In turn, higher-order connectivity is often the key in such multilayer network applications as developing optimal partitioning of critical infrastructures in order to isolate unhealthy system components under cyber-physical threats and simultaneous identification of multiple brain regions affected by trauma or mental illness. In this paper, we introduce the concepts of topological data analysis to studies of complex multilayer networks and propose a topological approach for network clustering. The key rationale is to group nodes based not on pairwise connectivity patterns or relationships between observations recorded at two individual nodes but based on how similar in shape their local neighborhoods are at various resolution scales. Since shapes of local node neighborhoods are quantified using a topological summary in terms of persistence diagrams, we refer to the approach as clustering using persistence diagrams (CPD). CPD systematically accounts for the important heterogeneous higher-order properties of node interactions within and in-between network layers and integrates information from the node neighbors. We illustrate the utility of CPD by applying it to an emerging problem of societal importance: vulnerability zoning of residential properties to weather- and climate-induced risks in the context of house insurance claim dynamics.more » « less
-
Abstract Cascades over networks (e.g., neuronal avalanches, social contagions, and system failures) often involve higher-order dependencies, yet theory development has largely focused on pairwise-interaction models. Here, we develop a ‘simplicial threshold model’ (STM) for cascades over simplicial complexes that encode dyadic, triadic and higher-order interactions. Focusing on small-world models containing both short- and long-range k -simplices, we explore spatio-temporal patterns that manifest as a frustration between local and nonlocal propagations. We show that higher-order interactions and nonlinear thresholding coordinate to robustly guide cascades along a k -dimensional generalization of paths that we call ‘geometrical channels’. We also find this coordination to enhance the diversity and efficiency of cascades over a simplicial-complex model for a neuronal network, or ‘neuronal complex’. We support these findings with bifurcation theory and data-driven approaches based on latent geometry. Our findings provide fruitful directions for uncovering the multiscale, multidimensional mechanisms that orchestrate the spatio-temporal patterns of nonlinear cascades.more » « less
-
The immense volume of user-generated content on social media provides a rich data source for big data research. Comentioned entities in social media content offer valuable information that can support a broad range of studies, from product market competition to dynamic social network mining and modeling. This paper introduces a new approach that combines named entity recognition (NER) and network modeling to extract and analyze co-mention relationships among entities in the same domain from unstructured social media data. This approach contributes to design for market systems literature because little research has investigated product competition via co-mention networks using large-scale unstructured social media data. In particular, the proposed approach provides designers with a new way to gain insight into market trends and aggregated customer preferences when customer choice data is insufficient. Moreover, our approach can easily support the evolution analysis of co-mention relationships beyond cross-sectional analysis of co-mention networks in a single year due to the abundance of social media data in multiple years. To demonstrate the approach to supporting multi-year product competition analysis, we perform a case study on mining co-mention networks of car models with Twitter data. The result shows that our approach can successfully extract the co-mention relationships of car models in multiple years from 2016 to 2019 from massive Twitter content; and enables us to conduct evolutionary co-mention network analysis with temporal network modeling and descriptive network analysis. The analysis confirmed that the co-mention network is capable of identifying frequently discussed entities and topics, such as car model pairs that often involve in competition and emerging vehicle technologies such as electric vehicles (EV). Furthermore, conducting evolutionary co-mention network analysis provides designers with an efficient way to monitor shifts in customer preferences for car features and to track trends in public discussions such as environmental issues associated with EVs over time. Our approach can be generally applied to other studies on co-mention relationships between entities, such as emerging technologies, cellphones, and political figures.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1073/pnas.2313171120
