PaperlayerView exact revision on arXiv

Source-linked AI summary

Higher-order clustering in networks

Hao Yin, Austin R. Benson, Jure Leskovec

arXiv:1704.03913v2cs.SIcond-mat.stat-mechphysics.soc-phstat.ML

TL;DR

Higher-order clique clustering is important but not well quantified by the triangle-based coefficient. This paper generalizes clustering through clique closure and finds that real-world networks have distinct higher-order patterns, with some lacking significant higher-order clustering after classical clustering is controlled for.

  • Problem

    The traditional clustering coefficient measures triangle closure, while the clustering behavior of larger cliques has not been well understood or quantified.

    Source: §I · p. 1

  • Method

    The paper defines higher-order clustering coefficients as normalized frequencies of higher-order clique closure, derives their properties, and analyzes them under G_n,p and small-world null models.

    Source: §I · pp. 1–2, B. Generalizing to higher-order… · p. 2

  • Results

    Real-world network domains show distinct higher-order clustering patterns, and some networks lack significant higher-order clustering after controlling for classical clustering.

    Source: §I · p. 2

  • Takeaways & Limitations

    Higher-order clustering coefficients reveal network structure that the traditional clustering coefficient alone does not show.

    Source: §I · p. 2

Abstract

from arXiv · show

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.

I. INTRODUCTION

Triangle-based clustering leaves higher-order clique closure unquantified, although larger cliques are important in complex networks. The paper reframes clustering as clique expansion, generalizes it to higher orders, and finds distinct patterns across real-world network domains.

I. INTRODUCTION

  • Higher-order cliques are important to network structure, but triangle-based clustering does not quantify their closure; some networks lack significant higher-order clustering after controlling for classical clustering.The passage notes that 4-cliques reveal community structure in word-association and protein-interaction networks.Source: §I · pp. 1–2

II. DERIVATION OF HIGHER-ORDER CLUSTERING COEFFICIENTS

  • The framework defines higher-order coefficients as normalized frequencies of higher-order clique closure and analyzes their properties under G_n,p and small-world null models.It extends the clique-expansion interpretation of the classical coefficient.Source: §I · pp. 1–2, §II · p. 2

I. INTRODUCTION

  • Real-world networks from different domains show distinct higher-order clustering patterns that the traditional coefficient alone does not reveal.Some networks show no significant higher-order clustering once classical clustering is controlled for.Source: §I · p. 2

A. Alternative interpretation of the classical clustering coefficient

  • The classical global coefficient can be viewed as the fraction of wedges formed by expanding an edge with an adjacent edge and closed by a triangle.The paper presents clique expansion, rather than length-2 path closure alone, as the interpretation that supports generalization.Source: A. Alternative interpretation of the… · p. 2

B. Generalizing to higher-order clustering coefficients

The paper generalizes clustering by measuring how often an ℓ-clique and an adjacent edge close into an (ℓ+1)-clique. It defines global and local forms and describes their computation by clique enumeration.

B. Generalizing to higher-order clustering coefficients

  • The global ℓth-order coefficient is the fraction of ℓ-wedges that close into (ℓ+1)-cliques, and it recovers the classical definition when ℓ=2.Each (ℓ+1)-clique closes ℓ²+ℓ ℓ-wedges.Source: B. Generalizing to higher-order… · pp. 2–3
  • The local coefficient counts closure for ℓ-wedges centered at a node, and the average is taken over nodes that center at least one such wedge.The center is the unique node shared by the ℓ-clique and adjacent edge.Source: B. Generalizing to higher-order… · p. 3
  • Computing local coefficients requires enumerating ℓ-cliques and (ℓ+1)-cliques, with Chiba–Nishizeki complexity O(ℓa^(ℓ−2)m); the authors apply it for ℓ=2, 3, 4 on networks with over a hundred million edges.Here a is graph arboricity and m is the number of edges.Source: B. Generalizing to higher-order… · p. 3
  • The algorithm is guaranteed polynomial time only when ℓ is constant; deciding whether a clique of at least ℓ nodes exists is NP-complete in general.Source: B. Generalizing to higher-order… · p. 3

C. Probabilistic interpretations of higher-order clustering coefficients

Higher-order local clustering can be read as a probability over sampled wedges or cliques in a node’s neighborhood. Products of local coefficients also give the clique density among that node’s neighbors.

C. Probabilistic interpretations of higher-order clustering coefficients

III. THEORETICAL ANALYSIS AND HIGHER-ORDER CLUSTERING IN RANDOM GRAPH MODELS

The theoretical analysis establishes extremal relationships between higher-order and traditional local clustering, then examines their behavior under common random-graph models. The bounds are essentially tight, with constructions approaching them across prescribed values of C2(u).

A. Extremal bounds

  • Proposition 1 gives essentially tight lower and upper bounds on higher-order local clustering coefficients in terms of the traditional local clustering coefficient.Source: A. Extremal bounds · p. 4
  • A neighborhood consisting of an (ℓ−1)-partite graph attains the lower bound, and edge removal can bring C2(u) arbitrarily close to any value in the stated interval.Source: A. Extremal bounds · p. 4
  • For sufficiently large neighborhoods, a clique plus isolated nodes can approach the upper bound while tuning C2(u) across [0, 1].Source: A. Extremal bounds · p. 4

B. Analysis for the Gn,p model

In the Gn,p model, higher-order wedge closure requires additional edges, yielding exponentially decreasing clustering with order. Even when conditioning on the traditional local coefficient, higher-order clustering approaches the dense-random pattern as neighborhood size grows.

B. Analysis for the Gn,p model

C. Analysis for the small-world model

The small-world analysis extends clustering results to higher orders. At zero rewiring, average higher-order clustering decreases with order; simulations show a transition near p = 0.1 across orders.

C. Analysis for the small-world model

  • The small-world model starts from a ring connecting each node to its 2k nearest neighbors, then rewires selected clockwise edges with probability p.Each rewired edge connects to a uniformly random node.Source: C. Analysis for the small-world model · p. 5
  • Near p = 0.1, clustering at all orders is lost as rewiring increases in the small-world model.The paper attributes this to sufficient rewiring removing local clique structure.Source: C. Analysis for the small-world model · p. 6
  • At p = 0, average higher-order clustering decreases as the clique order ℓ increases.Proposition 4 considers the limit as k and n grow with 2k < n and constant ℓ ≥ 2.Source: C. Analysis for the small-world model · p. 6

IV. EXPERIMENTAL RESULTS ON REAL-WORLD NETWORKS

The real-world analysis compares higher-order global and average clustering across 20 networks, then examines representative networks against null models and studies local clustering.

IV. EXPERIMENTAL RESULTS ON REAL-WORLD NETWORKS

  • Across 20 networks from several domains, the analysis examines global and average clustering by order, compares representative networks with null models, and studies local clustering.Source: §IV · p. 6

A. Higher-order global and average clustering

Across real-world and synthetic networks, higher-order clustering trends vary by network and by whether clustering is averaged across nodes or summarized globally. The analysis reports coefficients by order alongside the fraction of nodes eligible for the average coefficient.

A. Higher-order global and average clustering

  • Table I reports global and average clustering for orders 2–4 and the fraction of nodes centered on at least one ℓ-wedge; the average uses only participating nodes.The collection spans random graph models and neural, social, collaboration, communication, and technological networks.Source: A. Higher-order global and average… · pp. 6–7, Table I · p. 7
  • For most real-world networks, average clustering decreases from order 2 to 3 to 4, as it does in the synthetic networks; mouse retina, congress committees, and Oregon autonomous systems are exceptions.This indicates that, averaged over nodes, higher-order cliques are generally less likely to close.Source: A. Higher-order global and average… · p. 7
  • Global clustering increases with order in the co-authorship and autonomous-systems networks, decreases in the email and nematode-worm neural networks, and need not change monotonically.The increases are associated with nodes that are both star centers and clique participants; co-authorship networks also have higher base clustering than autonomous-systems networks.Source: A. Higher-order global and average… · p. 7
  • In three of four online social networks, C3 < C2 but C4 > C3.Source: A. Higher-order global and average… · p. 8
  • Within neural, communication, and collaboration subcategories, the order-related trends are consistent across networks even when their second-order clustering levels differ substantially.Source: A. Higher-order global and average… · p. 8

B. Comparison against null models

Comparisons with null models separate higher-order clustering from ordinary triadic closure. Some friendship and autonomous-systems networks show significant higher-order clustering after controlling for degree distribution and second-order clustering.

B. Comparison against null models

  • Compared with MRCN, Facebook friendship and autonomous-systems networks have significantly more higher-order clustering, C. elegans has significantly less, and co-authorship and email networks have slightly but not significantly more.MRCN preserves degree distribution and average second-order clustering.Source: B. Comparison against null models · p. 8
  • All real-world networks show clustering against the degree-preserving Configuration Model, but only some show higher-order clustering against MRCN, which also preserves average second-order clustering.Source: B. Comparison against null models · p. 8
  • C. elegans lacks higher-order clustering, consistent with under-expressed 4-cliques and overexpressed open 3-wedges; event-driven co-authorship and email networks’ average third-order clustering is not much larger than random graphs preserving second-order clustering and degree sequence.Source: B. Comparison against null models · p. 8
  • C. elegans has 2,010 4-cliques—nearly twice the MRCN mean of 1,006.2 (standard deviation 73.6)—yet its third-order average clustering is lower than MRCN’s.The authors attribute this discrepancy to clustering coefficients normalizing clique counts by closure opportunities.Source: B. Comparison against null models · p. 8

C. Higher-order local clustering coefficients and degree dependencies

Local higher-order clustering varies across networks: some nodes resemble random closure, while others approach the maximum allowed by their triangle clustering. Degree-stratified patterns also differ by network and clique order.

C. Higher-order local clustering coefficients and degree dependencies

  • Many C. elegans nodes lie near the random-configuration trend, whereas some arXiv co-authorship nodes with large C2(u) approach the C3(u) upper bound.Only a handful of nodes in the Facebook, Enron, and Oregon networks are near that bound.Source: C. Higher-order local clustering… · p. 9
  • Across all degrees, average higher-order clustering separates by clique order in Erdős–Rényi, small-world, C. elegans, and Enron networks.In Facebook, C2(u) exceeds C3(u) and C4(u), while C3(u) and C4(u) are roughly equal; co-authorship nodes have roughly equal Cℓ(u) for ℓ=2, 3, 4.Source: C. Higher-order local clustering… · p. 9
  • In Oregon, large-degree nodes have C4(u) > C3(u) > C2(u), explaining why global clustering can increase with order while average clustering does not.The plotted comparisons show higher-order average clustering by node degree in real-world and synthetic networks.Source: C. Higher-order local clustering… · p. 9

V. DISCUSSION

The discussion presents higher-order clustering coefficients as a generalization for studying clique closure beyond triangles. It distinguishes this focus from related higher-order work and contrasts the coefficients with earlier generalizations.

V. DISCUSSION

  • Higher-order clustering coefficients generalize the traditional clustering coefficient to study higher-order clique closure patterns.The work examines clique closure and only implicitly considers time as motivation for closure.Source: §V · p. 10
  • The framework complements work on higher-order information in network navigation and temporal community structure, while focusing on clique closure.The discussion says time is considered only implicitly as a motivation for closure.Source: §V · p. 10
  • Earlier generalizations focused on shortest paths, cycle formation, or triangle frequency in k-hop neighborhoods; the authors say these miss clique closure and pose analysis challenges.The discussion describes their own coefficients as simple but effective measurements.Source: §V · p. 10
Loading 1704.03913v2…