Higher-order organization of complex networks

Abstract

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 based on 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.

References in corpus (14)

• Fast unfolding of communities in large networks
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• The Dynamics of Viral Marketing
• Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
• Spectral redemption: clustering sparse networks
• Clustering and Community Detection in Directed Networks: A Survey
• Memory in network flows and its effects on spreading dynamics and community detection
• Tensor Spectral Clustering for Partitioning Higher-order Network Structures
• Modeling Interactome: Scale-Free or Geometric?
• Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
• Detecting communities of triangles in complex networks using spectral optimization
• Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks
• EmptyHeaded: A Relational Engine for Graph Processing

Cited by in corpus (203)

• Community detection in networks: A user guide
• Networks beyond pairwise interactions: structure and dynamics
• Machine Learning for Integrating Data in Biology and Medicine: Principles, Practice, and Opportunities
• Simplicial Closure and higher-order link prediction
• Dynamics on higher-order networks: A review
• Motifs in Temporal Networks
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Random walks on hypergraphs
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Graph signal processing for machine learning: A review and new perspectives
• Detecting Mixing Services via Mining Bitcoin Transaction Network with Hybrid Motifs
• Network Enhancement: a general method to denoise weighted biological networks
• Higher-order motif analysis in hypergraphs
• Diversity of meso-scale architecture in human and non-human connectomes
• Multi-body Interactions and Non-Linear Consensus Dynamics on Networked Systems
• The many facets of community detection in complex networks
• Machine learning dismantling and early-warning signals of disintegration in complex systems
• EdMot: An Edge Enhancement Approach for Motif-aware Community Detection
• Persistent homology of time-dependent functional networks constructed from coupled time series
• Inference of hyperedges and overlapping communities in hypergraphs
• Higher-order clustering in networks
• Synchronization induced by directed higher-order interactions
• Unveiling the higher-order organization of multivariate time series
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• Beyond the clustering coefficient: A topological analysis of node neighbourhoods in complex networks
• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
• Higher-order interactions promote chimera states
• Inhomogeneous Hypergraph Clustering with Applications
• Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions
• Learning Role-based Graph Embeddings
• MODEL: Motif-based Deep Feature Learning for Link Prediction
• Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
• Prioritizing network communities
• Subgraph Networks with Application to Structural Feature Space Expansion
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• Contagion in simplicial complexes
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Local Algorithms for Hierarchical Dense Subgraph Discovery
• The theory of percolation on hypergraphs
• MagNet: A Neural Network for Directed Graphs
• Epidemics on Hypergraphs: Spectral Thresholds for Extinction
• A Survey on Network Embedding
• The Power of Pivoting for Exact Clique Counting
• Efficient modeling of higher-order dependencies in networks: from algorithm to application for anomaly detection
• Subgraph Neural Networks
• Recommender systems based on graph embedding techniques: A comprehensive review
• Synchronization in temporal simplicial complexes
• Intelligent social bots uncover the link between user preference and diversity of news consumption
• Complex Network Modelling with Power-law Activating Patterns and Its Evolutionary Dynamics
• Higher-order Clustering and Pooling for Graph Neural Networks
• Disentangling homophily, community structure and triadic closure in networks
• Dual-Primal Graph Convolutional Networks
• Homological percolation transitions in growing simplicial complexes
• Self-Supervised Multi-Channel Hypergraph Convolutional Network for Social Recommendation
• Spectral Detection of Simplicial Communities via Hodge Laplacians
• Emergence of dynamic properties in network hyper-motifs
• Different approaches to community detection
• Motif-based Convolutional Neural Network on Graphs
• Random walks in time-varying networks with memory
• Versatility of nodal affiliation to communities
• Randomizing hypergraphs preserving degree correlation and local clustering
• Meta-validation of bipartite network projections
• Statistical inference for network samples using subgraph counts
• The nature of hypergraph $k$-core percolation problems
• A literature survey of matrix methods for data science
• Pre-Training Graph Neural Networks for Generic Structural Feature Extraction
• ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
• Stability analysis of multiplayer games on adaptive simplicial complexes
• Multiplex Communities and the Emergence of International Conflict
• HONEM: Learning Embedding for Higher Order Networks
• Random graphs with arbitrary clustering and their applications
• Graph Feature Preprocessor: Real-time Subgraph-based Feature Extraction for Financial Crime Detection
• Hyperlink communities in higher-order networks
• A framework for second order eigenvector centralities and clustering coefficients
• Interplay between $k$-core and community structure in complex networks
• New Phenomena in Large-Scale Internet Traffic
• Cycle and flow trusses in directed networks
• Enhancing Social Recommendation with Adversarial Graph Convolutional Networks
• Variational principle for scale-free network motifs
• Higher-Order Networks Representation and Learning: A Survey
• Nonlocal PageRank
• Adaptive Payoff-driven Interaction in Networked Snowdrift Games
• Detection of core-periphery structure in networks by 3-tuple motifs
• HONE: Higher-Order Network Embeddings
• Similarity Learning with Higher-Order Graph Convolutions for Brain Network Analysis
• Safeguarding Blockchain Ecosystem: Understanding and Detecting Attack Transactions on Cross-chain Bridges
• Deep Representation Learning for Social Network Analysis
• Percolation in random graphs with higher-order clustering
• MultiNet: A Scalable Multilayer Network Embedding Framework
• Understanding Complex Systems: From Networks to Optimal Higher-Order Models
• Coevolution of relationship-driven cooperation under recommendation protocol on multiplex networks
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Models for Capturing Temporal Smoothness in Evolving Networks for Learning Latent Representation of Nodes
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs
• The evolution of k-shell in syndication networks reveals financial performance of venture capital institutions
• Principled Multilayer Network Embedding
• Higher-order Network Analysis Takes Off, Fueled by Classical Ideas and New Data
• Filtering higher-order datasets
• Atomic subgraphs and the statistical mechanics of networks
• Opinion Dynamics with Multi-Body Interactions
• Scale-free network clustering in hyperbolic and other random graphs
• Fast asynchronous updating algorithms for k-shell indices
• Convexity in complex networks
• The universality of physical images at relative timescales on multiplex networks
• A Hybrid Traffic Speed Forecasting Approach Integrating Wavelet Transform and Motif-based Graph Convolutional Recurrent Neural Network
• Heterogeneous Network Motifs
• FreSCo: Mining Frequent Patterns in Simplicial Complexes
• Size-Invariant Graph Representations for Graph Classification Extrapolations
• Network Representation Learning: Consolidation and Renewed Bearing
• Bifurcations in the Kuramoto model with external forcing and higher-order interactions
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks
• Third order interactions shift the critical coupling in multidimensional Kuramoto models
• On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices
• motif2vec: Motif Aware Node Representation Learning for Heterogeneous Networks
• Graph Convolutional Neural Networks via Motif-based Attention
• Random Recursive Hypergraphs
• Motif-Based Spectral Clustering of Weighted Directed Networks
• Higher-order temporal network effects through triplet evolution
• Exact solutions of the Kuramoto model with asymmetric higher order interactions of arbitrary order
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Higher-order synchronization on the sphere
• Topology reveals universal features for network comparison
• Motif Dynamics in Signed Directional Complex Networks
• Correlation Clustering Generalized
• Deep Node Ranking for Neuro-symbolic Structural Node Embedding and Classification
• Cliques and a new measure of clustering: with application to U.S. domestic airlines
• Narrative Maps: An Algorithmic Approach to Represent and Extract Information Narratives
• CompLex: legal systems through the lens of complexity science
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
• Mind Your Credit: Assessing the Health of the Ripple Credit Network
• On the Triangle Clique Cover and $K_t$ Clique Cover Problems
• DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• Making Communities Show Respect for Order
• Local Hypergraph Clustering using Capacity Releasing Diffusion
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
• Emergence of biconnected clusters in explosive percolation
• Graph Homomorphism Convolution
• Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• Boosting Multitask Learning on Graphs through Higher-Order Task Affinities
• DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data
• Power Network Uniqueness and Synchronization Stability from a Higher-order Structure Perspective
• Quantifying the structural stability of simplicial homology
• A simple bipartite graph projection model for clustering in networks
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• A sampling framework for counting temporal motifs
• Normal and stable approximation to subgraph counts in superpositions of Bernoulli random graphs
• MultiAspect Graphs: Algebraic representation and algorithms
• Higher-order dissimilarity measures for hypergraph comparison
• Representation Learning of Graphs Using Graph Convolutional Multilayer Networks Based on Motifs
• Hypergraph Random Walks, Laplacians, and Clustering
• Inference of time-ordered multibody interactions
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model
• Local Hyper-Flow Diffusion
• Simplex Closing Probabilities in Directed Graphs
• Motif Clustering and Overlapping Clustering for Social Network Analysis
• Combinatorial Properties for a Class of Simplicial Complexes Extended from Pseudo-fractal Scale-free Web
• How to optimize an academic team when the outlier member is leaving?
• Temporal Network Sampling
• Motif Enhanced Recommendation over Heterogeneous Information Network
• Higher-Order Spectral Clustering of Directed Graphs
• Pangolin: An Efficient and Flexible Graph Pattern Mining System on CPU and GPU
• Retrospective Higher-Order Markov Processes for User Trails
• Quantum Motif Clustering
• Directed Network Laplacians and Random Graph Models
• From clusters to queries: exploiting uncertainty in the modularity landscape of complex networks
• Inferring Graph Signal Translations as Invariant Transformations for Classification Tasks
• Observement as Universal Measurement
• Generalizing Egocentric Temporal Neighborhoods to probe for spatial correlations in temporal networks and infer their topology
• Peeling Bipartite Networks for Dense Subgraph Discovery
• Latent Space Model for Higher-order Networks and Generalized Tensor Decomposition
• weg2vec: Event embedding for temporal networks
• Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
• Representing Big Data as Networks: New Methods and Insights
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• Network Reconstruction and Controlling Based on Structural Regularity Analysis
• Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
• Neural Embedding Propagation on Heterogeneous Networks
• Graph Pattern Mining and Learning through User-defined Relations (Extended Version)
• Mixed-Order Spectral Clustering for Networks
• Learning Resolution Parameters for Graph Clustering
• Correlation-Based Community Detection
• Automatic Self-supervised Learning for Social Recommendations
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers
• Consensus dynamics on temporal hypergraphs
• Efficient and High-Quality Seeded Graph Matching: Employing High Order Structural Information
• User-Guided Clustering in Heterogeneous Information Networks via Motif-Based Comprehensive Transcription
• Learning Connectivity and Higher-order Interactions in Radial Distribution Grids
• Evaluation and Comparison of Diffusion Models with Motif Features
• Structural Landmarking and Interaction Modelling: on Resolution Dilemmas in Graph Classification
• $H{S}^2$: Active Learning over Hypergraphs
• Mean Field Analysis of Hypergraph Contagion Model
• Adaptive Shrinkage Estimation for Streaming Graphs
• Testing Alignment of Node Attributes with Network Structure Through Label Propagation
• Meta-Graph Based HIN Spectral Embedding: Methods, Analyses, and Insights
• Spread-gram: A spreading-activation schema of network structural learning
• A nonlinear diffusion method for semi-supervised learning on hypergraphs
• Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation
• Ranking Users in Social Networks with Motif-based PageRank
• Temporal Motif Participation Profiles for Analyzing Node Similarity in Temporal Networks
• A Fast Counting Method for 6-motifs with Low Connectivity
• Fragility of spectral clustering for networks with an overlapping structure