Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient

Bing-Yi Jing; Ting Li; Xianshi Yu

Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient

T0 review · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The normalized clustering coefficient converges to a quantity that depends only on the community in-out ratio under the degree-corrected block model, enabling inference of community strength without community detection.

desk verdict Promising new network statistic with a sound DCBM core, but the LCD asymptotics are off by a factor that breaks the claimed model-separation rule. read the letter →

arxiv 1908.00523 v1 pith:ANUNOO3V submitted 2019-08-01 cs.SI physics.soc-phstat.AP

Ting Li , Xianshi Yu , Bing-Yi Jing This is my paper · ORCID

classification cs.SIphysics.soc-phstat.AP

keywords clusteringnetworkcoefficientnormalizedunderanalysisdegreegenerative

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Networks, like social graphs or the web, often have clusters of nodes that connect more tightly among themselves than to the rest of the network. A standard measure of this clustering strength is the clustering coefficient, which counts how often two friends of the same node are also friends. The problem is that the number depends on network size, density, and whether some nodes have far more connections than others, so it cannot be compared across different networks.

The authors define a normalized version: they take the density of triangles, divide by the cube of the ratio of edge density to connected-triple density, and cancel out the effects of density and degree variation. Under the degree-corrected block model, a common generative model for networks with communities, the normalized value converges to a known expression that depends only on the ratio of within-community to between-community connection probabilities. Thus one can read off community strength directly from the statistic, without running a community-detection algorithm.

The paper derives asymptotic normality for this estimator and applies it to detect fake Twitter accounts, to choose among network sampling methods, and to track partisan polarization in U.S. Senate cosponsorship networks over time. The Twitter and Senate examples suggest the statistic behaves as claimed, though the theoretical treatment of the scale-free model is underdeveloped and some empirical choices are ad hoc.

Extended reading notes

Core claim

Under the degree-corrected block model with balanced class sizes, common within-block probability p, common between-block probability q, and E(θ^2)=1, the normalized clustering coefficient ρ̂ converges to ρ = [K r^3 + 3K(K-1)r + K(K-1)(K-2)]/(r+K-1)^3, a strictly increasing function of the in-out ratio r=p/q (Section 2.2, Eq. 7). Theorem 1 states that sqrt(C(N,3) T)(ρ̂-ρ)/ρ converges in distribution to N(0,1), so the in-out ratio can be inferred from the statistic without running community detection. The paper further claims this statistic is robust to network size, density, and degree heterogeneity, and that its value falls in (1,K) for DCBM, near 1 for Erdős-Rényi, and below 3/4 for the LCD model.

Load-bearing premise

The clean mapping from ρ̂ to the in-out ratio r holds only for the restricted DCBM submodel defined in Section 2.2: all communities have the same within-community probability p and the same between-community probability q, class sizes are balanced (π_i=1/K), and the degree-correction parameters satisfy E(θ^2)=1. Under a general DCBM with heterogeneous block probabilities or unbalanced community sizes, the normalized clustering coefficient also depends on those nuisance parameters, and the displayed monotone relation to r fails. This restriction is stated in the paper ('we reduce the parameter domain to B_ii=p>q=B_ij' and 'we also set π_i=1/K'), but it directly limits the scope of the headline claim that the statistic reveals community strength.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The normalized clustering coefficient is a genuinely new statistic, and the DCBM core in Section 2.2 is sound: Eq. (7) is correct, the monotone dependence on the in-out ratio is real, and the idea of inferring r without community detection is useful. But the LCD part, Theorem 2, has a real math error. The stress-test note checks out: V-hat as defined in Eq. (2) is a per-triple average of three wedge indicators, so V-hat = W/(3*C(N,3)) where W is the number of wedges. The paper's recombination of Lemmas 3-4 treats V as the standard triple count, which is off by a factor of 3 in V-hat and hence gives the wrong constant. The correct limit appears to be m(m-1)/(m+1)^2, not the stated 3m(m-1)/(4(m+1)^2). This matters because the claim that LCD networks have value below 3/4, and the whole Figure 1 separation rule, rests on that constant.

The DCBM theorem itself is plausible; the proof is sketched with remainder terms dismissed, but the lemmas it uses are the right ones and the algebra in the appendix is consistent. Treat that part as probably correct, but in need of a complete proof. The scope restriction to balanced, homogeneous-probability blocks with E(theta^2)=1 is clearly stated, and it's an honest limitation rather than a hidden one.

The applications are suggestive. The Senate example is nice: the normalized statistic tracks the party-based in-out ratio without labels. The Twitter analysis is weaker, with ad hoc degree filters and thresholds, and the AUC gain over the clustering coefficient is modest (0.661 vs 0.627). These are illustrative, not the paper's main contribution.

Overall, the central idea is worth taking seriously and deserves referee time, but the paper needs major revision before it can stand: fix Theorem 2, give a proper proof of Theorem 1, and be upfront about the restricted DCBM submodel. The reader's conditional verdict is about right.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities; the analysis rests on cited subgraph-count lemmas and a restricted DCBM. The free parameters are practical tuning choices in the applications, not fitted values in the theoretical derivation.

free parameters (2)

Threshold c in networks clustering
In Section 3.1.1 and Proposition 2, the rejection threshold for comparing two networks is left as 'a certain threshold c' or a formula involving the unknown number of communities K; no data-driven rule is given.
Number of communities K in the test threshold
In Proposition 2, the critical value depends on K, which must be known or upper-bounded; the paper does not specify how to set it in practice.

assumptions (4)

domain assumption Lemmas 1 and 2 from Gao and Lafferty (2017) providing variance bounds and CLT for triangle counts under DCBM
Used in the proof of Theorem 1 (Appendix A) and Proposition 1; not proven in this paper.
domain assumption Lemmas 3 and 4 from Bollobás and Riordan (2003) on triangle and triplet counts in the LCD model
Used in the proof of Theorem 2; the constants in these lemmas are taken as given.
domain assumption The DCBM submodel restricts to B_ii=p>q=B_ij for all blocks, balanced class sizes π_i=1/K, and constraint E(θ^2)=1
This restriction makes the limit ρ depend only on r and K; without it the 'in-out-ratio' is not identifiable from the three counts used.
domain assumption The network is simple and undirected; self-loops and multi-edges are excluded
All derivations use an adjacency matrix with zero diagonal and assume A_ij ∈ {0,1}.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient." pith.science (2026). https://pith.science/paper/ANUNOO3V

@misc{pith2026190800523,
  author       = {Pith},
  title        = {Pith review of: Measuring the Clustering Strength of a Network via the Normalized Clustering Coefficient},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ANUNOO3V}},
  note         = {Machine review of arXiv:1908.00523}
}

read the original abstract

In this paper, we propose a novel statistic of networks, the normalized clustering coefficient, which is a modified version of the clustering coefficient that is robust to network size, network density and degree heterogeneity under different network generative models. In particular, under the degree corrected block model (DCBM), the "in-out-ratio" could be inferred from the normalized clustering coefficient. Asymptotic properties of the proposed indicator are studied under three popular network generative models. The normalized clustering coefficient can also be used for networks clustering, network sampling as well as dynamic network analysis. Simulations and real data analysis are carried out to demonstrate these applications.

Figures

Figures reproduced from arXiv: 1908.00523 by the authors.

**Figure 4.** Plot of the clustering strength of the cosponsorship networks structured from bills sponsored in the U.S. Senate during 93rd-114th Congresses. The normalized clustering coefficient (black line) can reveal the truth (red line) without using the party labels, while the clustering coefficient (green line) cannot [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

**Figure 4.** The normalized clustering coefficients of sub-networks and the original networks in [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗

Figures from the paper (2 more)

**Figure 5.** Figure 5: The normalized clustering coefficients of sub-networks and the original networks in [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

**Figure 6.** Figure 6: The normalized clustering coefficients of sub-networks and the original networks in [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 28 canonical work pages

[1]

K., Neville, J., and Kompella, R

Ahmed, N. K., Neville, J., and Kompella, R. (2014). Network sampling: From static to streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 8(2), 7

work page 2014
[2]

L., and Albert, R

Barabási, A. L., and Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439), 509-512

work page 1999
[3]

Barrat, A., Barthelemy, M., and Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America, 101(11), 3747

work page 2004
[4]

Bollobás, B., and Riordan, O. (2003). Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet, 1-34

work page 2003
[5]

Bollobás, B., and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica, 24(1), 5-34

work page 2004
[6]

P., and Grassi, R

Clemente, G. P., and Grassi, R. (2018). Directed clustering in weighted networks: A new perspective. Chaos, Solitons and Fractals , 107, 26-38

work page 2018
[7]

Fowler, J. H. (2006). Legislative cosponsorship networks in the US House and Senate. Social Networks, 28(4), 454-465

work page 2006
[8]

Gao, C., and Lafferty, J. (2017). Testing for global network structure using small subgraph statistics. arXiv preprint arXiv:1710.00862

arXiv 2017

Show all 30 references

[9]

Y., and Zhou, H

Gao, C., Ma, Z., Zhang, A. Y., and Zhou, H. H. (2018). Community detection in degree-corrected block models. The Annals of Statistics, 46(5), 2153-2185

2018
[10]

H., Kirkland, J

Gross, J. H., Kirkland, J. H., and Shalizi, C. (2012). Cosponsorship in the US Senate: A multilevel two-mode approach to detecting subtle social predictors of legislative support

2012
[11]

W., Laskey, K

Holland, P. W., Laskey, K. B., and Leinhardt, S. (1983). Stochastic blockmodels: First steps. Social networks, 5(2), 109-137

1983
[12]

Jin, J. (2015). Fast community detection by SCORE. The Annals of Statistics. 43(1), 57-89

2015
[13]

T., and Luo, S

Jin, J., Ke, Z. T., and Luo, S. (2018, July). Network Global Testing by Counting Graphlets. In International Conference on Machine Learning, (pp. 2338-2346)

2018
[14]

Kagan, D., Elovichi, Y., and Fire, M. (2018). Generic anomalous vertices detection utilizing a link prediction algorithm. Social Network Analysis and Mining, 8(1), 27

2018
[15]

and Newman, M

Karrer, B. and Newman, M. E. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107

2011
[16]

and Gabrys, B

Kendrick, L., Musial, K. and Gabrys, B. (2018). Change point detection in social networks—Critical review with experiments. Computer Science Review, 29, 1-13

2018
[17]

Latapy, M., Magnien, C., and Del Vecchio, N. (2008). Basic notions for the analysis of large two-mode networks. Social Networks , 30(1), 31-48

2008
[18]

H., Kim, P

Lee, S. H., Kim, P. J., and Jeong, H. (2006). Statistical properties of sampled networks. Physical Review E, 73(1), 016102

2006
[19]

and Rinaldo, A

Lei, J. and Rinaldo, A. (2015). Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1), 215-237

2015
[20]

(2006, August)

Leskovec, J., and Faloutsos, C. (2006, August). Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (pp. 631-636). ACM

2006
[21]

D., and Perry, A

Luce, R. D., and Perry, A. D. (1949). A method of matrix analysis of group structure. Psychometrika , 14(2), 95-116

1949
[22]

S., Sarkar, P., and Lin, L

Mukherjee, S. S., Sarkar, P., and Lin, L. (2017). On clustering network-valued data. In Advances in neural information processing systems, pp. 7071-7081

2017
[23]

Opsahl, T., and Panzarasa, P. (2009). Clustering in weighted networks. Social Networks , 31(2), 155-163

2009
[24]

Rezvanian, A., Moradabadi, B., Ghavipour, M., Khomami, M. M. D., and Meybodi, M. R. (2019). Social Network Sampling. In Learning Automata Approach for Social Networks, (pp. 91-149). Springer, Cham

2019
[25]

Rossetti, G., and Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), 51(2), 35

2018
[26]

Schank, T., and Wagner, D. (2004). Approximating clustering-coefficient and transitivity. Journal of Graph Algorithms and Applications, 9(2), 265-275

2004
[27]

Shervashidze, SVN

N. Shervashidze, SVN. Vishwanathan, TH. Petri, K. Mehlhorn, and KM. Borgwardt. (2009) Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics (pp. 488-495)

2009
[28]

J., and Strogatz, S

Watts, D. J., and Strogatz, S. H. (1998). Collective dynamics of small-world networks. Nature, 393(6684), 440

1998
[29]

J., and Olhede, S

Wolfe, P. J., and Olhede, S. C. (2013). Nonparametric graphon estimation. arXiv preprint arXiv:1309.5936

2013 arXiv
[30]

Zhao, Y., Levina, E., and Zhu, J. (2012). Consistency of community detection in networks under degree-corrected stochastic block models. The Annals of Statistics. 40(4), 2266-2292

2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

K., Neville, J., and Kompella, R

Ahmed, N. K., Neville, J., and Kompella, R. (2014). Network sampling: From static to streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), 8(2), 7

work page 2014

[2] [2]

L., and Albert, R

Barabási, A. L., and Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439), 509-512

work page 1999

[3] [3]

Barrat, A., Barthelemy, M., and Vespignani, A. (2004). The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America, 101(11), 3747

work page 2004

[4] [4]

Bollobás, B., and Riordan, O. (2003). Mathematical results on scale-free random graphs. Handbook of graphs and networks: from the genome to the internet, 1-34

work page 2003

[5] [5]

Bollobás, B., and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica, 24(1), 5-34

work page 2004

[6] [6]

P., and Grassi, R

Clemente, G. P., and Grassi, R. (2018). Directed clustering in weighted networks: A new perspective. Chaos, Solitons and Fractals , 107, 26-38

work page 2018

[7] [7]

Fowler, J. H. (2006). Legislative cosponsorship networks in the US House and Senate. Social Networks, 28(4), 454-465

work page 2006

[8] [8]

Gao, C., and Lafferty, J. (2017). Testing for global network structure using small subgraph statistics. arXiv preprint arXiv:1710.00862

arXiv 2017