Higher-order organization of complex networks

By Austin R. Benson, David F. Gleich, Jure Leskovec. 2016

1,353 citations recorded by the source corpus.

Resolving a network of hubs Graphs are a pervasive tool for modeling and analyzing network data throughout the sciences. Benson et al. developed an algorithmic framework for studying how complex networks are organized by higher-order connectivity patterns (see the Perspective by Pržulj and Malod-Dognin). Motifs in transportation networks reveal hubs and geographical elements not readily achievable by other methods. A motif previously suggested as important for neuronal networks is part of a “rich club” of subnetworks. Science, this issue p. 163; see also p. 123 A mathematical framework for clustering reveals organizational features of a variety of networks. Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks—at the level of small network subgraphs—remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns.

Subfields: Computational Theory and Mathematics, Molecular Biology, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Inductive Representation Learning on Large Graphs (2017, background): “The clustering coefﬁcient is a popular measure of how clustered a node’s local neighborhood is, and it serves as a building block for many more complicated structural motifs [3].”
Evolution of resilience in protein interactomes across the tree of life (2018, methodology): “To study evolutionary mechanisms of structural changes in the interactomes, we investigate network motifs (34, 35).”
Prioritizing network communities (2018, methodology): “For each community we measure: (1) drug-drug interactions between the drugs (“Epistasis”), (2) chemical structure similarity of the drugs (“Chemistry”), and (3) associations between drugs derived from text data (“Text”).”
Deep Representation Learning for Social Network Analysis (2019, background): “Nevertheless, pairwise relations can only provide insights about local neighborhoods, and might not infer global hierarchical network structures, which is crucial for more complex networks (Benson et al., 2016).”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, background): “As network-based system models have become almost ubiquitous across scientific domains [20,93], graphs and their Laplacians feature prominently in many analysis tasks [9, 12, 40, 64, 87, 89].”
Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (2021, background): “…and meaningful motifs/patterns of temporal networks; CAW-N may also be generalized to predict high-order structures ( e.g. , triangles) that correspond to some function units of temporal networks from different domains (Benson et al., 2016; 2018; Zitnik et al., 2019). feedback on the abstract.”
Machine Learning for Integrating Data in Biology and Medicine: Principles, Practice, and Opportunities (2018, background): “For example, recent advances in the theory of multi-level graphs and network motifs enabled us to study, for example, higher-order organization of gene regulatory networks [346, 347] and multi-layer nature of”
Community detection in networks: A user guide (2016, background): “Indeed, one could formulate the network clustering problem by focusing on higher order structures, like motifs (e. g., triangles) (Arenas et al., 2008a; Benson et al., 2016; Serrour et al., 2011).”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “For example, small substructures (graphlets) have been extensively analysed in protein-protein interaction networks [44], triangles and cliques characterise the structure of ego-nets and social networks in general [20], simple cycles (rings) are central in molecular distributions, directed and tempo”
Simplicial closure and higher-order link prediction (2018, background): “But much of the structure in these systems involves higher-order interactions between more than two entities at once [8, 23, 39, 44, 64]: people often communicate or interact in social groups, not just in pairs; associative relations among ideas or topics often involve the intersection of multiple c”
Subgraph-augmented Path Embedding for Semantic User Search on Heterogeneous Social Network (2018, background): “We are inspired by the state-of-the-art work on exploting subgraph patterns to organize complex networks [3].”
A Survey on Network Embedding (2017, background): “For example, how to incorporate network motifs [92], one of the most common higher-order structures in a network, into network embedding remains an open problem.”
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training (2020, background): “ underlying assumption is that there exist common and transferable structural patterns across different graphs such as the motif, k-core, and structural hole, as evident in network science literature [5, 7, 32, 52]. One illustrative scenario is that we pre-train a model on Facebook, IMDB, and DBLP g”