Higher-order clustering in networks

Abstract

A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by the clustering coefficient, which is the probability that a length-2 path is closed, i.e., induces a triangle in the network. However, higher-order cliques beyond triangles are crucial to understanding complex networks, and the clustering behavior with respect to such higher-order network structures is not well understood. Here we introduce higher-order clustering coefficients that measure the closure probability of higher-order network cliques and provide a more comprehensive view of how the edges of complex networks cluster. Our higher-order clustering coefficients are a natural generalization of the traditional clustering coefficient. We derive several properties about higher-order clustering coefficients and analyze them under common random graph models. Finally, we use higher-order clustering coefficients to gain new insights into the structure of real-world networks from several domains.

References in corpus (7)

• Uncovering the overlapping community structure of complex networks in nature and society
• Higher-order organization of complex networks
• Random graphs with clustering
• Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks
• Structural Transitions in Dense Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Modeling scientific-citation patterns and other triangle-rich acyclic networks

Cited by in corpus (24)

• Dynamics on higher-order networks: A review
• Higher-order motif analysis in hypergraphs
• Measuring Integrated Information: Comparison of Candidate Measures in Theory and Simulation
• Hyperedge overlap drives explosive collective behaviors in systems with higher-order interactions
• The Power of Pivoting for Exact Clique Counting
• Higher-order Spectral Clustering for Heterogeneous Graphs
• Random Spatial Network Models with Core-Periphery Structure
• Random graphs with arbitrary clustering and their applications
• A Network Science perspective of Graph Convolutional Networks: A survey
• A framework for second order eigenvector centralities and clustering coefficients
• Higher-Order Networks Representation and Learning: A Survey
• Evolving Network Modeling Driven by the Degree Increase and Decrease Mechanism
• Percolation in random graphs with higher-order clustering
• Stratified communities in complex business networks
• Scale-free network clustering in hyperbolic and other random graphs
• Sampling random graph homomorphisms and applications to network data analysis
• Graph Convolutional Neural Networks via Motif-based Attention
• Clustering coefficients for networks with higher order interactions
• Cliques and a new measure of clustering: with application to U.S. domestic airlines
• Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE
• The HyperKron Graph Model for higher-order features
• Growing Attributed Networks through Local Processes
• Efficient and Adaptive Estimation of Local Triadic Coefficients
• Analysis of Clustering and Degree Index in Random Graphs and Complex Networks