Higher-order clustering in networks

By Hao Yin, Austin R. Benson, Jure Leskovec. 2017

113 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Statistical and Nonlinear Physics

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

1. Jure Leskovec
2. Austin R. Benson
3. David F. Gleich
4. Marinka Zitnik
5. Rok Sosic

In Statistical and Nonlinear Physics

1. Austin R. Benson
2. Jure Leskovec
3. David F. Gleich
4. Matjaz Perc
5. Hao Yin
6. S. Majhi
7. Dibakar Ghosh
8. Rok Sosic

Citations in the corpus

• Local Higher-Order Graph Clustering (2017, background): “Œe formal theory rests on the idea of higher-order clustering coecients, which we developed in recent work [49] and brieƒy review below.”
• Dynamics on higher-order networks: a review (2022, background): “Because of the perception that higher-order clusters are particularly important, the concept of higher-order clustering coefficients is introduced in [42], which quantifies the closure probability of higher-order cliques.”