arxiv: 2605.03796 · v3 · submitted 2026-05-05 · 💻 cs.SI

Recognition: 3 theorem links

· Lean Theorem

Capability centrality: the next step from scale-free property

Mikhail Tuzhilin

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:05 UTC · model grok-4.3

classification 💻 cs.SI

keywords ksi-centralityscale-free networksBarabasi-Albert modelpreferential attachmentcentrality measuresalgebraic connectivitynetwork modeling

0 comments

The pith

Ksi-centrality distribution is an independent property of real networks that determines the preferential attachment parameter m.

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

The paper establishes ksi-centrality as a measure whose distribution is right-skewed in real networks but centered in random Erdos-Renyi networks and in generative models including Barabasi-Albert. This distribution property stands apart from scale-freeness because scale-free models still produce centered ksi-centrality distributions. A normalized form of the measure relates to algebraic connectivity and Cheeger's value, with its average value in one-to-one correspondence with the number of edges m that each new node attaches to in the Barabasi-Albert model. This correspondence offers a direct method to select m when using the model to represent a specific real-world network.

Core claim

Ksi-centrality distinguishes real networks from random ones by having a right-skewed distribution with a heavy tail on log plots, while Erdos-Renyi networks show centered distributions. The same centered pattern appears in Barabasi-Albert, Watts-Strogatz, and Boccaletti-Hwang-Latora models, establishing the distribution as an additional property independent of scale-freeness. The normalized ksi-centrality links to algebraic connectivity, and its average bijectively matches the relative edge count m in the preferential attachment model.

What carries the argument

Ksi-centrality, a new centrality measure whose normalized average corresponds bijectively to the attachment parameter m in the Barabasi-Albert model and distinguishes network types by distribution shape.

If this is right

Real networks can be identified by their right-skewed ksi-centrality distributions.
Scale-free models like Barabasi-Albert do not reproduce the ksi-centrality distribution of real networks.
The average normalized ksi-centrality provides a precise way to choose the parameter m for modeling a given real network with preferential attachment.
Normalized ksi-centrality values reflect the algebraic connectivity and Cheeger's value of the network.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This measure could help validate whether a generative model accurately captures the structure of a target real network beyond degree distributions.
Researchers might explore ksi-centrality in other network models or on temporal networks to see if the independence holds more broadly.
The bijective mapping suggests that ksi-centrality could guide the design of synthetic networks to match observed real-world connectivity features.

Load-bearing premise

The observed differences in ksi-centrality distributions stem from the intrinsic structure of the networks rather than from the specific definition of the centrality formula or from the particular selection of real networks and models used in the comparisons.

What would settle it

Computing ksi-centrality on additional real networks and their corresponding Barabasi-Albert models with m chosen by the average normalized value, then checking if the distributions match or if the bijective relation holds for new cases, would test the claims; mismatch in distributions or non-unique m would falsify the independence and correspondence.

Figures

Figures reproduced from arXiv: 2605.03796 by Mikhail Tuzhilin.

**Figure 1.** Figure 1: Dependency of normalized ksi-coefficients vs relative number of attachments view at source ↗

**Figure 2.** Figure 2: Linear fitting of ksi distribution at logy plot for networks from supplementary table 1. view at source ↗

**Figure 3.** Figure 3: Ksi-distributions fitted with Weibull distribution, their Pearson’s moment coefficients view at source ↗

**Figure 4.** Figure 4: Normalized average ksi (left) and average ksi (right) coefficients for different param view at source ↗

**Figure 5.** Figure 5: Ksi (left) and normalized ksi (right) distributions for different networks. The x-axis view at source ↗

**Figure 6.** Figure 6: Ksi-distributions (left) and corresponding log-scale for y axes (right) for networks view at source ↗

**Figure 7.** Figure 7: Ksi-distributions (left) and corresponding log-scale for y axes (right) for networks view at source ↗

**Figure 8.** Figure 8: Ksi-distributions (left) and corresponding log-scale for y axes (right) for networks view at source ↗

**Figure 9.** Figure 9: Ksi-distributions (left) and corresponding log-scale for y axes (right) for networks view at source ↗

**Figure 10.** Figure 10: Ksi-distributions (left) and corresponding log-scale for y axes (right) for networks view at source ↗

**Figure 11.** Figure 11: Ksi-distributions fitted with Weibull distribution, their Pearson’s moment coeffi view at source ↗

**Figure 12.** Figure 12: Dependence of the ksi-distribution and its Pearson’s moment coefficients of skewness view at source ↗

**Figure 13.** Figure 13: Dependence of the ksi-distribution and its Pearson’s moment coefficients of skewness view at source ↗

**Figure 14.** Figure 14: Dependence of the ksi-distribution and its Pearson’s moment coefficients of skewness view at source ↗

**Figure 15.** Figure 15: Pearson’s moment coefficients of skewness for the ksi-distribution for the Watts view at source ↗

**Figure 16.** Figure 16: Degree distributions fitted with Weibull distribution, their Pearson’s moment co view at source ↗

read the original abstract

In this article we present a new centrality measure called ksi-centrality. We show that ksi-centrality distinguishes real networks from random ones, similar to degree centrality: the ksi-centrality distribution is right-skewed for real networks and centered for random Erdos-Renyi networks, and has linear pattern with a heavy tail on a log plot. Furthermore, the ksi-centrality distribution is centered for models simulating real networks: Barabasi-Albert, Watts-Strogatz, and Boccaletti-Hwang-Latora. Thus, this centrality distribution is an additional and independent property with respect to scale-freeness. We also introduce a normalized version of ksi-centrality and show that it is related to algebraic connectivity and the Chegeer's value of a network. Moreover, the average value of this normalized centrality is in bijective correspondence with the relative number of edges that a new node connects to others in the Barabasi-Albert preferential attachment model, thus answering the question of how to choose the parameter $m$ to model a given real-world network.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Ksi-centrality shows real networks with skewed distributions unlike BA and other models, but the bijective m link only matches one narrow statistic and does not validate full structural reproduction.

read the letter

The main takeaway is that this new ksi-centrality measure reveals a skewed distribution in real networks that several standard generative models do not reproduce, even when those models are scale-free. The paper defines ksi-centrality and demonstrates its distribution properties across real networks and models like Barabasi-Albert, Watts-Strogatz, and others. Real networks show right-skewed patterns with heavy tails on log plots, while the models and Erdos-Renyi graphs show centered distributions. This difference holds despite the scale-free nature of BA, which supports the independence claim. They also normalize the measure and connect it to algebraic connectivity and the Cheeger value. The average of the normalized version is said to correspond bijectively to the m parameter in the BA model. This bijection is where it gets thin. Matching the average ksi does not ensure the generated network will match the original on other important statistics such as clustering coefficient or diameter. The paper focuses on this single link without broader validation. The distributional evidence looks solid from the described contrasts, and the algebraic tie-in is a positive step if the formulas check out. No major internal contradictions stand out. This work would interest researchers in network science who want diagnostics that go past degree sequences. A reader building or evaluating generative models might pick up the m-choice suggestion, but should treat it as a starting point rather than a complete solution. It deserves a serious referee to examine the centrality definition, the derivations, and whether the patterns generalize. I recommend sending it for peer review, with feedback on expanding the model validation.

Referee Report

3 major / 3 minor

Summary. The manuscript introduces a new centrality measure termed ksi-centrality (also referenced as capability centrality). It reports that the ksi-centrality distribution is right-skewed with a heavy tail in real networks, centered in Erdős–Rényi graphs, and centered in generative models including Barabási–Albert (BA), Watts–Strogatz, and Boccaletti–Hwang–Latora. The authors conclude that this distribution constitutes an additional property independent of scale-freeness. A normalized variant is related to algebraic connectivity and the Cheeger constant, and its network-wide average is claimed to stand in bijective correspondence with the BA attachment parameter m, thereby supplying a method to select m when modeling a given real-world network.

Significance. If the definitions are unambiguous, the empirical contrasts are reproducible across diverse datasets, and the bijective mapping is shown to be non-circular and predictive of additional network statistics, the work would supply a useful supplementary descriptor beyond degree-based properties and a concrete heuristic for BA parameterization. The independence claim is potentially valuable because it offers a direct counter-example (BA networks are scale-free yet exhibit centered ksi distributions) to the idea that scale-freeness alone fixes all structural features. The modeling-utility claim, however, rests on a single scalar match and therefore carries lower immediate impact unless further validation is supplied.

major comments (3)

[Abstract and modeling section] Abstract and the section presenting the bijective correspondence: the claim that average normalized ksi-centrality supplies the value of m for a real network is load-bearing for the modeling contribution. Even if the numerical bijection holds inside the BA construction, matching this single derived scalar (itself linked to algebraic connectivity) does not demonstrate that the resulting BA graph reproduces other defining statistics of the target network such as clustering coefficient, diameter, or motif counts. A concrete test—e.g., fitting m via the average and then comparing the full degree exponent, transitivity, and effective diameter—would be required to substantiate the modeling utility.
[Definition and independence section] Section defining ksi-centrality and the independence claim: the assertion that the ksi-centrality distribution is 'an additional and independent property with respect to scale-freeness' is central. Because BA networks are scale-free yet reported to have centered ksi distributions while real networks are skewed, the distinction is a potential counter-example; however, the manuscript must explicitly verify that the measure is not implicitly sensitive to the degree sequence or other scale-free indicators, and that the contrast survives after degree-sequence-preserving randomization of the real networks.
[Normalization and spectral section] Section relating normalized ksi-centrality to algebraic connectivity and Cheeger's constant: the precise mathematical relationship (equality, inequality, or asymptotic link) between the normalized measure and these spectral quantities is not visible from the abstract. Because the normalization is used to obtain the bijective mapping with m, an explicit derivation or bound is needed to justify the normalization choice and to confirm it is not tautological with the BA construction.

minor comments (3)

[Title and abstract] The title uses 'Capability centrality' while the abstract and body employ 'ksi-centrality'; a single consistent term should be adopted throughout.
[Empirical results] The manuscript should include a short table or figure caption that lists the exact real-world networks, their sizes, and the generative-model parameters used for the distribution comparisons.
[Introduction] Standard references to existing centrality measures that also attempt to capture structure beyond degree (e.g., betweenness, eigenvector, or communicability) would help situate the novelty of ksi-centrality.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We believe the points raised will help improve the manuscript's clarity and strengthen its contributions. We address each major comment below and outline the revisions we plan to implement.

read point-by-point responses

Referee: [Abstract and modeling section] Abstract and the section presenting the bijective correspondence: the claim that average normalized ksi-centrality supplies the value of m for a real network is load-bearing for the modeling contribution. Even if the numerical bijection holds inside the BA construction, matching this single derived scalar (itself linked to algebraic connectivity) does not demonstrate that the resulting BA graph reproduces other defining statistics of the target network such as clustering coefficient, diameter, or motif counts. A concrete test—e.g., fitting m via the average and then comparing the full degree exponent, transitivity, and effective diameter—would be required to substantiate the modeling utility.

Authors: We agree that demonstrating the practical modeling utility requires showing that BA networks parameterized by the average normalized ksi-centrality reproduce additional structural features of the target real networks. In the revised manuscript we will add a dedicated subsection containing such validation experiments. For multiple real-world networks we will compute the average normalized ksi-centrality to select m, generate the corresponding BA graphs, and directly compare the resulting degree exponent, clustering coefficient, and effective diameter to those of the original networks. These comparisons will provide concrete evidence that the parameterization yields structurally faithful models. revision: yes
Referee: [Definition and independence section] Section defining ksi-centrality and the independence claim: the assertion that the ksi-centrality distribution is 'an additional and independent property with respect to scale-freeness' is central. Because BA networks are scale-free yet reported to have centered ksi distributions while real networks are skewed, the distinction is a potential counter-example; however, the manuscript must explicitly verify that the measure is not implicitly sensitive to the degree sequence or other scale-free indicators, and that the contrast survives after degree-sequence-preserving randomization of the real networks.

Authors: We accept that an explicit check against degree-sequence effects is required to solidify the independence claim. In the revision we will add results from configuration-model randomizations that preserve the degree sequences of the real networks. We will show that the ksi-centrality distributions of these randomized graphs remain right-skewed with heavy tails, while BA networks possessing comparable degree sequences continue to exhibit centered distributions. This analysis will demonstrate that the observed distinction is not reducible to the degree sequence and thereby reinforce the independence from scale-freeness. revision: yes
Referee: [Normalization and spectral section] Section relating normalized ksi-centrality to algebraic connectivity and Cheeger's constant: the precise mathematical relationship (equality, inequality, or asymptotic link) between the normalized measure and these spectral quantities is not visible from the abstract. Because the normalization is used to obtain the bijective mapping with m, an explicit derivation or bound is needed to justify the normalization choice and to confirm it is not tautological with the BA construction.

Authors: We will supply the missing mathematical detail in the revised manuscript. A new subsection will present an explicit derivation relating the normalized ksi-centrality to the algebraic connectivity (second-smallest eigenvalue of the Laplacian) and will establish rigorous bounds connecting the measure to the Cheeger constant. This derivation will justify the chosen normalization on spectral grounds and will show that the relationship holds independently of the BA generative process. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's core claims rest on empirical comparisons of ksi-centrality distributions across real networks (right-skewed) versus ER, BA, WS, and BHL models (centered), directly demonstrating independence from scale-freeness without reducing to definitional equivalence. The normalized ksi-centrality's link to algebraic connectivity and Cheeger value, plus the stated bijective correspondence with BA parameter m, are presented as derived properties used to propose a matching procedure for m; these do not collapse to fitted inputs renamed as predictions or self-citations, as no load-bearing self-referential steps or ansatzes are evident. The derivation chain remains self-contained against the external benchmarks and models cited.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

Only the abstract is available, so the precise mathematical foundations cannot be audited. The work relies on standard graph-theoretic concepts (degree, algebraic connectivity, Cheeger's value) and introduces ksi-centrality without providing its formula or independent justification for its construction.

invented entities (1)

ksi-centrality no independent evidence
purpose: New centrality measure claimed to be independent of scale-freeness
Introduced in the abstract as a novel quantity whose definition and derivation are not supplied

pith-pipeline@v0.9.0 · 5475 in / 1375 out tokens · 50843 ms · 2026-05-08T18:05:32.612728+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith.Cost (Jcost = ½(x+x⁻¹)−1) washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

ksi-centrality ξ_i = E(N(i), V\N(i))/d_i ... normalized ksi-centrality ξ̂_i = E(N(i),V\N(i))/(d_i(n-d_i))
IndisputableMonolith.Foundation (parameter-free derivations) reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

the average value of this normalized centrality is in bijective correspondence with the relative number of edges m/n in the Barabasi-Albert preferential attachment model

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 1 canonical work pages · 1 internal anchor

[1]

An experimental study of the small world problem // Social networks

Travers J., Milgram S. An experimental study of the small world problem // Social networks. Academic Press. 1977. P. 179–197

1977
[2]

J., Strogatz S

Watts D. J., Strogatz S. H. Collective dynamics of ‘small-world’networks //nature. 1998.393. №6684. 440–442

1998
[3]

Albert, R., Jeong, H., Barab´ asi, A. L. (1999). Diameter of the world-wide web. nature, 401(6749), 130-131

1999
[4]

D., and Clauset A

Broido A. D., and Clauset A. ”Scale-free networks are rare.” Nature communications 10.1 (2019): 1017

2019
[5]

L., Albert, R

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

1999
[6]

”Growing hierarchical scale-free networks by means of nonhierarchical processes.” International Journal of Bifurcation and Chaos 17.07 (2007): 2447- 2452

Boccaletti S., Hwang D-U., and Latora V. ”Growing hierarchical scale-free networks by means of nonhierarchical processes.” International Journal of Bifurcation and Chaos 17.07 (2007): 2447- 2452

2007
[7]

Freeman, L. C. (2002). Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge, 1(3), 238-263

2002
[8]

Simonis et al., ”Empirically controlled mapping of the Caenorhabditis elegans protein-protein interactome network.” Nature Methods 6(1), 47-54 (2009)

N. Simonis et al., ”Empirically controlled mapping of the Caenorhabditis elegans protein-protein interactome network.” Nature Methods 6(1), 47-54 (2009)

2009
[9]

Joshi-Tope et al

G. Joshi-Tope et al. ”Reactome: a knowledgebase of biological pathways.” Nucleic Acids Research 33.suppl 1, D428-D432 (2005)

2005
[10]

Isella et al., ”What’s in a crowd? Analysis of face-to-face behavioral networks.” Journal of Theoretical Biology 271, 166-180 (2011)

L. Isella et al., ”What’s in a crowd? Analysis of face-to-face behavioral networks.” Journal of Theoretical Biology 271, 166-180 (2011)

2011
[11]

Kunegis, ”Douban network dataset.” KONECT, the Koblenz Network Collection (2016)

J. Kunegis, ”Douban network dataset.” KONECT, the Koblenz Network Collection (2016)

2016
[12]

McAuley and J

J. McAuley and J. Leskovec. Learning to Discover Social Circles in Ego Networks. NIPS, 2012

2012
[13]

Leskovec, J

J. Leskovec, J. Kleinberg and C. Faloutsos. Graph Evolution: Densification and Shrinking Diam- eters. ACM Transactions on Knowledge Discovery from Data (ACM TKDD), 1(1), 2007

2007
[14]

Rozemberczki and R

B. Rozemberczki and R. Sarkar. Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models. 2020

2020
[16]

(2015, March)

Rossi, R., & Ahmed, N. (2015, March). The network data repository with interactive graph analytics and visualization. In Proceedings of the AAAI conference on artificial intelligence (Vol. 29, No. 1)

2015
[17]

Rozemberczki, R

B. Rozemberczki, R. Davies, R. Sarkar and C. Sutton. GEMSEC: Graph Embedding with Self Clustering. 2018

2018
[18]

Rozemberczki, C

B. Rozemberczki, C. Allen and R. Sarkar. Multi-scale Attributed Node Embedding. 2019

2019
[19]

Yang and J

J. Yang and J. Leskovec. Defining and Evaluating Network Communities based on Ground-truth. ICDM, 2012. 6

2012
[20]

E. Cho, S. A. Myers, J. Leskovec. Friendship and Mobility: Friendship and Mobility: User Move- ment in Location-Based Social Networks ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2011

2011
[21]

Leskovec, K

J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics 6(1) 29–123, 2009

2009
[22]

Leskovec, J

J. Leskovec, J. Kleinberg and C. Faloutsos. Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2005

2005
[23]

Rual et al

JF. Rual et al. ”Towards a proteome-scale map of the human protein-protein interaction network.” Nature 437.7062, 1173-1178. (2005)

2005
[24]

”Evolution of resilience in protein interactomes across the tree of life”, Proceedings of the National Academy of Sciences (PNAS), 2019, 116 (10) 4426-4433

Marinka Zitnik, Rok Sosic, Marcus W Feldman, and Jure Leskovec. ”Evolution of resilience in protein interactomes across the tree of life”, Proceedings of the National Academy of Sciences (PNAS), 2019, 116 (10) 4426-4433

2019
[25]

Marvel Universe looks almost like a real social network

R. Alberich, J. Miro-Julia, and F. Rossello, ”Marvel Universe looks almost like a real social network.” arxiv:cond-mat/0202174 (2002)

work page internal anchor Pith review arXiv 2002
[26]

Dallas et al

T. Dallas et al. ”Gauging support for macroecological patterns in helminth parasites.” Glob. Ecol. Biogeogr. 27, 1437-1447 (2018)

2018
[27]

Zhang et al., ”Collecting the Internet AS-level topology.” SIGCOMM Computer Communica- tion Review 35(1), 53-61 (2005)

B. Zhang et al., ”Collecting the Internet AS-level topology.” SIGCOMM Computer Communica- tion Review 35(1), 53-61 (2005)

2005
[28]

M. E. J. Newman, ”The structure of scientific collaboration networks.” Proc. Natl. Acad. Sci. USA 98(2), 404-409 (2001)

2001
[29]

Wachs, M

J. Wachs, M. Fazekas, and J. Kertesz, ”Corruption Risk in Contracting Markets: A Network Science Perspective.” International Journal of Data Science and Analytics, pp 1-16 (2020)

2020
[30]

Kunegis, ”Stack overflow network dataset” KONECT, the Koblenz Network Collection (2016)

2016
[31]

Fellbaum

C. Fellbaum. ”WordNet.” Theory and Applications of Ontology: Computer Applications. Springer, 231-243 (2010). 7 Supplementary Material Capability centrality: the next step from scale-free property Mikhail Tuzhilin1 1HSE university, Moscow State University In what follows we consider simple undirected graphsGwithA=A(G) ={a ij}— adjacency matrix and byL=L(G...

2010
[32]

If the degreed i ≤ n 2 for a vertexi, thenξ i ≥h(G),
[33]

ˆξi ≥ ( h(G) (n−d i),ifd i ≤ n 2 , h(G)d i,otherwise. The next result is that the normalized ksi-centrality (as well as the average normalized ksi- coefficient) are bounded by theλ 2 algebraic connectivity (or the second eigenvalue of the Laplacian matrix). Theorem 4.Consider connected graphG. Let’s denote Laplacian matrix spectrum by0 =λ 1 < λ 2 ≤ λ3 ≤.....

2000