Pith. sign in

REVIEW 36 references

Sampling on networks: estimating eigenvector centrality on incomplete graphs

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 A new greedy sampling method, TCEC, uses spectral projection bounds to estimate eigenvector centrality rankings on incomplete networks and outperforms random-walk baselines on several real-world networks.

arxiv 1908.00388 v1 pith:L55IIPRQ submitted 2019-08-01 cs.SI physics.data-anphysics.soc-ph

Nicolò Ruggeri , Caterina De Bacco This is my paper · ORCID
classification cs.SIphysics.data-anphysics.soc-ph
keywords datasamplingcentralityalgorithmeigenvectorestimateincompletemethods
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

Eigenvector centrality is a way of scoring how important each node is in a network: a node is important if it is connected to other important nodes. Computing it usually requires seeing the whole network, which is often impossible when data collection is costly or the network is huge. This paper asks a practical question: if we can only inspect a small subset of nodes, which nodes should we look at so that the centrality scores we compute from the subset match the true scores for those same nodes?
Extended reading notes

Core claim

The central claim is that the TCEC sampling algorithm, guided by the spectral bound gamma = ||B||_2, estimates eigenvector centrality rankings from a subsample better than traditional sampling methods (uniform, random walk variants) on real networks, while remaining computationally scalable. The abstract states: 'we show that approximations obtained from such methods are not always reliable and that our algorithm, while preserving computational scalability, improves performance under different error measures.' If correct, TCEC gives a scalable, theoretically motivated method for ranking-preserving centrality estimation on incomplete graphs.

Load-bearing premise

The load-bearing premise is that greedily reducing gamma = ||P_m A (I - P_m)||_2, via the partial criterion in Eq. (6) that drops the U^T U term, is a reliable proxy for preserving the relative ranking of eigenvector centralities. The paper evaluates Kendall and Spearman rank correlations, not sine distance, and explicitly says 'we observe that this approach works' only empirically (Section III), while noting it fails on Erdős-Rényi graphs. If minimizing this bound does not translate to rank preservation in a new network, the algorithm's advantage disappears.

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.

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

The central derivation relies on standard spectral results and several ad hoc modeling choices. The most consequential choices are the decision to drop the U^T U term, to restrict candidates to the border, and to use in-degree as a proxy for eigenvector centrality in directed networks. No new entities are introduced.

free parameters (4)
  • alpha = 0 for undirected, 0.5 for directed
    Hyperparameter interpolating between the gamma criterion and the in-degree heuristic; chosen empirically per graph family.
  • s (leaderboard max size) = 100
    Maximum leaderboard size, set to 100 as 'generally good' based on empirical runs.
  • p (randomization probability) = 0.2 to 0.8 per dataset
    Fraction of candidate border neighbors scored; tuned per dataset to obtain faster convergence.
  • initial random walk fraction = 1/5 of final sample size
    Random walk initialization size to make the criterion discriminative; fixed by design.
assumptions (9)
  • standard math Perron-Frobenius theorem guarantees a unique positive eigenvector for nonnegative irreducible matrices.
    Needed to define eigenvector centrality uniquely; invoked before Theorem 1.
  • standard math Courant-Fischer theorem for the largest eigenvalue of B^T B.
    Used in Lemma 1 to characterize the largest singular value.
  • standard math Spectral projection bounds from Saad's Numerical Methods for Large Eigenvalues Problems.
    Basis for Theorem 1, cited as reference [11].
  • domain assumption In-degree approximates eigenvector centrality, mu_j approximately d_in(j), from Romance (2011).
    Used to build the alpha-term heuristic for directed networks.
  • domain assumption Adjacency matrix is nonnegative and the graph is strongly connected (only the largest strongly connected component is considered).
    Ensures Perron-Frobenius applies; stated in Section II.
  • domain assumption Neighbor lists for sampled nodes are accessible in the sampling scenario.
    The border selection requires local neighbor information; stated as a practical assumption.
  • ad hoc to paper The U^T U term in B^T B is negligible and can be dropped from the greedy criterion.
    Justified only by computational cost and the claim that removing one node barely changes it; no formal bound given.
  • ad hoc to paper Restricting candidate nodes to the border is sufficient.
    The paper says 'This choice is arbitrary, but motivated by observations' and relies on incoming-neighbor importance.
  • ad hoc to paper Reducing the sine-distance bound is a valid proxy for preserving node rankings.
    The paper evaluates rank correlations, not sine distance, and only observes empirically that the proxy works, noting it fails on Erdős-Rényi graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sampling on networks: estimating eigenvector centrality on incomplete graphs." pith.science (2026). https://pith.science/paper/L55IIPRQ

@misc{pith2026190800388,
  author       = {Pith},
  title        = {Pith review of: Sampling on networks: estimating eigenvector centrality on incomplete graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L55IIPRQ}},
  note         = {Machine review of arXiv:1908.00388}
}
read the original abstract

We develop a new sampling method to estimate eigenvector centrality on incomplete networks. Our goal is to estimate this global centrality measure having at disposal a limited amount of data. This is the case in many real-world scenarios where data collection is expensive, the network is too big for data storage capacity or only partial information is available. The sampling algorithm is theoretically grounded by results derived from spectral approximation theory. We studied the problem on both synthetic and real data and tested the performance comparing with traditional methods, such as random walk and uniform sampling. We show that approximations obtained from such methods are not always reliable and that our algorithm, while preserving computational scalability, improves performance under different error measures.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 33 canonical work pages

  1. [1]

    We define the border of a sampled subgraph as the set of all the incoming neighbors not include d in the sample itself

    we aim at minimizing the informa- tion missed by not sampling informative incoming neighbors of nodes in the sample. We define the border of a sampled subgraph as the set of all the incoming neighbors not include d in the sample itself. In our online algorithm, we choose to se - lect candidate nodes from those in the border. This choice is arbitrary, but m...

    work page

  2. [2]

    However, these two quantities are difficult to treat analytically and we therefore rely on acti ng on γ, which is instead accessible

    by minimizing tan(µ, Km) or maxi- mizing||Am− λ/onebbb||2,Km∩ ˜µ⊥ . However, these two quantities are difficult to treat analytically and we therefore rely on acti ng on γ, which is instead accessible. We will partially address the minimization of tan(µ, Km) using theoretically grounded heuristics below. From (3), we see that γdepends on the choice of the ...

    work page

  3. [3]

    How does the data sampling strategy impact the discovery of info r- mation diffusion in social media? In F ourth International AAAI Conference on W eblogs and Social Media, 2010

    Munmun De Choudhury, Y u-Ru Lin, Hari Sundaram, Kasim Selcuk Candan, Lexing Xie, and Aisling Kelliher. How does the data sampling strategy impact the discovery of info r- mation diffusion in social media? In F ourth International AAAI Conference on W eblogs and Social Media, 2010

    work page 2010

  4. [4]

    Correcting for missing data in information cas- cades

    Eldar Sadikov, Montserrat Medina, Jure Leskovec, and Hecto r Garcia-Molina. Correcting for missing data in information cas- cades. In Proceedings of the fourth ACM international confer- ence on W eb search and data mining, pages 55–64. ACM, 2011

    work page 2011

  5. [5]

    Sampling from large graphs

    Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 631–636. ACM, 2006

    2006

  6. [6]

    Towards compress- ing web graphs

    Micah Adler and Michael Mitzenmacher. Towards compress- ing web graphs. In Proceedings DCC 2001. Data Compression Conference, pages 203–212. IEEE, 2001

    work page 2001

  7. [7]

    Network sampling and model fitting

    Ove Frank. Network sampling and model fitting. Models and methods in social network analysis , pages 31–56, 2005

    work page 2005

  8. [8]

    Effect of sampling on topology predic- tions of protein-protein interaction networks

    Jing-Dong J Han, Denis Dupuy, Nicolas Bertin, Michael E Cu- sick, and Marc Vidal. Effect of sampling on topology predic- tions of protein-protein interaction networks. Nature biotech- nology, 23(7):839, 2005

    work page 2005

Show all 36 references
  1. [9]

    Sta- tistical properties of sampled networks

    Sang Hoon Lee, Pan-Jun Kim, and Hawoong Jeong. Sta- tistical properties of sampled networks. Physical Review E , 73(1):016102, 2006

    2006

  2. [10]

    Effects of missing data in social networ ks

    Gueorgi Kossinets. Effects of missing data in social networ ks. Social networks, 28(3):247–268, 2006

    2006

  3. [11]

    Factoring and weighting approaches to st a- tus scores and clique identification

    Phillip Bonacich. Factoring and weighting approaches to st a- tus scores and clique identification. Journal of mathematical sociology, 2(1):113–120, 1972

    1972

  4. [12]

    The stability of centrality measures when networks are sampled

    Elizabeth Costenbader and Thomas W V alente. The stability of centrality measures when networks are sampled. Social net- works, 25(4):283–307, 2003

    2003

  5. [13]

    Y . Saad. Numerical Methods for Large Eigenvalues Problems . 2011

    2011

  6. [14]

    Empirical com- parison of network sampling: How to choose the most appropri - ate method? Physica A: Statistical Mechanics and its Applica- tions, 477:136–148, 2017

    Neli Blagus, Lovro Šubelj, and Marko Bajec. Empirical com- parison of network sampling: How to choose the most appropri - ate method? Physica A: Statistical Mechanics and its Applica- tions, 477:136–148, 2017. 5https://github.com/cdebacco/tcec

    2017

  7. [15]

    Is the sample good enough? comparing data from twitter’ s streaming api with twitter’s firehose

    Fred Morstatter, Jürgen Pfeffer, Huan Liu, and Kathleen M Ca r- ley. Is the sample good enough? comparing data from twitter’ s streaming api with twitter’s firehose. In Seventh international AAAI conference on weblogs and social media , 2013

    2013

  8. [16]

    On unbiased sampling for unstructure d peer-to-peer networks

    Daniel Stutzbach, Reza Rejaie, Nick Duffield, Subhabrata Se n, and Walter Willinger. On unbiased sampling for unstructure d peer-to-peer networks. IEEE/ACM Transactions on Networking (TON), 17(2):377–390, 2009

    2009

  9. [17]

    Metropolis algorithms for representat ive subgraph sampling

    Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representat ive subgraph sampling. In 2008 Eighth IEEE International Confer- ence on Data Mining , pages 283–292. IEEE, 2008

    2008

  10. [18]

    Sampling properties of random graphs: the degree distribution

    Michael PH Stumpf and Carsten Wiuf. Sampling properties of random graphs: the degree distribution. Physical Review E , 72(3):036118, 2005

    2005

  11. [19]

    Estimation of vertex degrees in a sampled network

    Apratim Ganguly and Eric D Kolaczyk. Estimation of vertex degrees in a sampled network. In 2017 51st Asilomar Con- ference on Signals, Systems, and Computers , pages 967–974. IEEE, 2018

    2017

  12. [20]

    Sampling-based estimation of in-degree distribution with applications to directed complex networ ks

    Nelson Antunes, Shankar Bhamidi, Tianjian Guo, Vladas Pipi - ras, and Bang Wang. Sampling-based estimation of in-degree distribution with applications to directed complex networ ks. arXiv preprint arXiv:1810.01300, 2018

    2018 arXiv

  13. [21]

    The anatomy of a large-scale hypertextual web search engine

    Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):107–117, 1998

    1998

  14. [22]

    An improved method for efficient pagerank estimation

    Y uta Sakakura, Y uto Yamaguchi, Toshiyuki Amagasa, and Hi- royuki Kitagawa. An improved method for efficient pagerank estimation. In International Conference on Database and Ex- pert Systems Applications, pages 208–222. Springer, 2014

    2014

  15. [23]

    Local methods for estimating pagerank values

    Yen-Y u Chen, Qingqing Gan, and Torsten Suel. Local methods for estimating pagerank values. In Proceedings of the thirteenth ACM international conference on Information and knowledge management, pages 381–389. ACM, 2004

    2004

  16. [24]

    Matrix computations, volume 3

    Gene H Golub and Charles F V an Loan. Matrix computations, volume 3. JHU press, 2012

    2012

  17. [25]

    Walking in facebook: A case study of unbiased sampling of osns

    Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina Markopoulou. Walking in facebook: A case study of unbiased sampling of osns. In 2010 Proceedings IEEE Infocom , pages 1–9. Ieee, 2010

    2010

  18. [26]

    Local estimates for eigenvector-like cent ral- ities of complex networks

    Miguel Romance. Local estimates for eigenvector-like cent ral- ities of complex networks. Journal of Computational and Ap- plied Mathematics, 235(7):1868–1874, 2011. 7

    2011

  19. [27]

    On random graphs, i

    Paul Erdös and Alfréd Rényi. On random graphs, i. Publica- tiones Mathematicae (Debrecen), 6:290–297, 1959

    1959

  20. [28]

    Quantifying the completeness of the observed internet as-l evel structure

    Ricardo Oliveira, Walter Willinger, Beichuan Zhang, et al. Quantifying the completeness of the observed internet as-l evel structure. work, 11(15):13–17, 2008

    2008

  21. [29]

    Grap h evolution: Densification and shrinking diameters

    Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Grap h evolution: Densification and shrinking diameters. ACM Trans- actions on Knowledge Discovery from Data (TKDD) , 1(1):2, 2007

    2007

  22. [30]

    Trust management for the semantic web

    Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. Trust management for the semantic web. In International se- mantic W eb conference, pages 351–368. Springer, 2003

    2003

  23. [31]

    Community structure in large networks: Natural cluster sizes and the absence of large well-defined c lus- ters

    Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined c lus- ters. Internet Mathematics, 6(1):29–123, 2009

    2009

  24. [32]

    Random walks on graphs: A survey

    László Lovász et al. Random walks on graphs: A survey. Com- binatorics, Paul erdos is eighty, 2(1):1–46, 1993

    1993

  25. [33]

    Equation of state calculations by fast computing machines

    Nicholas Metropolis, Arianna W Rosenbluth, Marshall N Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6):1087–1092, 1953

    1953

  26. [34]

    Snowball sampling

    Leo A Goodman. Snowball sampling. The annals of mathemat- ical statistics, pages 148–170, 1961

    1961

  27. [35]

    Sampling community structure

    Arun S Maiya and Tanya Y Berger-Wolf. Sampling community structure. In Proceedings of the 19th international conference on W orld wide web, pages 701–710. ACM, 2010

    2010

  28. [36]

    Nonparametric statis- tics: A step-by-step approach

    Gregory W Corder and Dale I Foreman. Nonparametric statis- tics: A step-by-step approach . John Wiley & Sons, 2014. 8 Supporting Information (SI) S1. Additional Theorems and Proofs A. Proof of theorem 1 Proof. We follow the same notation of the proof in [ 11, p.103/104]. What ...

    2014

Pith tools

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