Higher-order clustering coefficients
Higher-order clustering coefficients is framework that quantifies the extent of higher-order clustering in networks. It is a natural extension of the classic clustering coefficient [Watts and Strogatz 1998] that measures the rate of triadic closure. We interpret triadic closure from a clique-expansion prospective, which offers a natural generalization when one is interested in the closure of clique of size larger than 3.
Motivation
The clustering coefficient quantifies the extent to which edges of a network cluster in terms of triangles. The clustering coefficient is defined as the fraction of length-2 paths that are closed with a triangle. However, the clustering coefficient is inherently restrictive as it measures the closure probability of just one simple structure—-the triangle. Moreover, higher-order structures such as larger cliques are crucial to the structure and function of complex networks. The extent of clustering of such higher-order structures has not been well understood nor quantified.
Higher-order clustering in networks. Hao Yin, Austin R. Benson, Jure Leskovec. arXiv:1704.03913.
Definition
We interpret triadic closure from a clique-expansion prospective [row \(C_2\)], which offers
a natural generalization when one is interested in the closure of clique of size larger than 3.
Formally, for any \(\ell \geq 2\), we define an \(\ell\)-wedge as a pair of an \(\ell\)-clique and an edge
that shares exactly one common node, and an \(\ell\)-clique is called closed if the related
\(\ell\)+1 nodes induces an (\(\ell\)+1)-clique. Now the \(\ell\)th-order global clustering coefficient is the fraction of
\(\ell\)-wedges in the network that is closed, and the \(\ell\)th-order local clustering coefficient at a node u
is the fraction of \(\ell\)-wedges centered at node \(u\) that is closed, where the center of an \(\ell\)-wedge is the common
node of the clique and edge.
Theoretical Properties
Extremal bounds
For any \(\ell\geq 3\), we obtain an upper bound and lower bound for the local \(\ell\)th-order clustering coefficient at any node based on its second-order (classic) local clustering coefficient: $$ 0 \leq C_\ell(u) \leq \sqrt{C_2(u)}, $$ and these bounds are tight.
In Erdős–Rényi model
In the Erdős–Rényi random graph model \(G_{n,p}\), we have the following results:- \(\mathbb{E}[C_\ell] = \mathbb{E}[C_\ell(u)] = \mathbb{E}[\bar{C}_\ell] = p^{\ell-1}\);
- \(\mathbb{E}[C_\ell(u)|C_2(u)] = (C_2(u))^{\ell-1}\).
In the small-world model
The small-world model [Watts and Strogatz 1998] begins with a ring network of \(n\) nodes where each node connects to its \(2k\) nearest neighbors. Then, for each node \(u\) and each of the \(k\) edges \((u, v)\) with \(v\) following $u$ clockwise in the ring, the edge is rewired to \((u, w)\) with probability \(p\), where \(w\) is chosen uniformly at random.In the small-world model, without rewiring (\(p=0\)), we have $$ \bar{C}_\ell \rightarrow \frac{\ell+1}{2\ell} $$ as \(n, k \rightarrow \infty\). As a result, \(\bar C_\ell\) decreases as \(\ell\) increases. When \(p \neq 0\), obtaining a closed-form formula for the expected value of \(\bar C_\ell\) remains an open problem. Via simulation, we observe that \(\bar C_\ell\) also decreases as $\ell$ increases. The intuition behind these results is that, cliques of larger size are hard to form in these synthetic networks.
Empirical Evaluations
We examine the higher-order clustering on 20 real-world networks from different domains, including online social friendship networks, collaboration networks, human communication networks, neural networks, and technological systems networks. We find that each domain of networks has its own higher-order clustering pattern.
Conventional wisdom in network science posits that practically all real-world networks exhibit clustering; however, we find that the clustering property only holds up to a certain order. More specifically, once we control for the clustering as measured by the classical clustering coefficient, networks from some domains, such as communication networks, do not show significant higher-order clustering in terms of higher-order clique closure; more interestingly, neural networks exhibit lack of higher-order clustering!
