pith. sign in

arxiv: 1906.08335 · v1 · pith:M6DBGC2Hnew · submitted 2019-06-19 · 💻 cs.SI · cs.LG

Compressive Closeness in Networks

Hamidreza Mahyar , Rouzbeh Hasheminezhad , H Eugene Stanley This is my paper

Pith reviewed 2026-05-25 19:31 UTC · model grok-4.3

classification 💻 cs.SI cs.LG
keywords closeness centralitycompressive sensingdistributed algorithmscentral node detectionego-centric metricslocal network measuresnetwork analysis
0
0 comments X

The pith

A new local metric correlates more strongly with global closeness centrality than prior alternatives and supports compressive sensing recovery of the most central nodes.

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

The paper shows that a simple metric computed from a node's immediate neighbors tracks the expensive global closeness centrality better than existing local measures. It then folds this local signal into a compressive sensing procedure that identifies the highest-centrality nodes through distributed neighbor interactions alone. The approach addresses the practical constraint that nodes in large networks lack the full topology and cannot afford all-pairs distance calculations. If the correlation holds, the method yields accurate central-node detection at low local cost on both synthetic and real networks.

Core claim

The authors introduce an ego-centric local metric whose values correlate with global closeness centrality more closely than current local alternatives, then demonstrate that a compressive sensing framework built on repeated local measurements of this metric recovers the set of highest-closeness nodes with greater accuracy than existing distributed methods across the tested networks.

What carries the argument

An ego-centric local metric computed from a node's direct neighborhood that acts as a proxy for global closeness centrality, aggregated through compressive sensing to recover top-centrality nodes.

If this is right

  • Nodes can locate high-closeness nodes using only immediate-neighbor exchanges without global topology knowledge.
  • The local metric computation remains low-complexity while still enabling accurate recovery of influential nodes.
  • The compressive sensing recovery step outperforms prior distributed techniques on both synthetic and real-world networks.
  • All steps remain fully distributed, suiting very large networks where centralized computation is impossible.

Where Pith is reading between the lines

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

  • The same local-plus-compressive-sensing pattern could be tested on other global centrality measures whose exact computation is also expensive.
  • Periodic recomputation of the local metric might allow tracking of centrality changes in slowly evolving networks without full re-scans.
  • Applications that rely on identifying spreaders or bottlenecks, such as targeted messaging or vulnerability assessment, could operate with strictly local data collection.

Load-bearing premise

The new local metric maintains a sufficiently strong correlation with true closeness centrality across diverse network structures so that compressive sensing can still recover the top nodes reliably.

What would settle it

A network in which the proposed local metric shows markedly lower correlation with closeness centrality than claimed, causing the compressive sensing recovery step to identify fewer true top-centrality nodes than state-of-the-art distributed baselines.

read the original abstract

Distributed algorithms for network science applications are of great importance due to today's large real-world networks. In such algorithms, a node is allowed only to have local interactions with its immediate neighbors. This is because the whole network topological structure is often unknown to each node. Recently, distributed detection of central nodes, concerning different notions of importance, within a network has received much attention. Closeness centrality is a prominent measure to evaluate the importance (influence) of nodes, based on their accessibility, in a given network. In this paper, first, we introduce a local (ego-centric) metric that correlates well with the global closeness centrality; however, it has very low computational complexity. Second, we propose a compressive sensing (CS)-based framework to accurately recover high closeness centrality nodes in the network utilizing the proposed local metric. Both ego-centric metric computation and its aggregation via CS are efficient and distributed, using only local interactions between neighboring nodes. Finally, we evaluate the performance of the proposed method through extensive experiments on various synthetic and real-world networks. The results show that the proposed local metric correlates with the global closeness centrality, better than the current local metrics. Moreover, the results demonstrate that the proposed CS-based method outperforms the state-of-the-art methods with notable improvement.

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.

Referee Report

3 major / 1 minor

Summary. The paper introduces an ego-centric local metric claimed to correlate well with global closeness centrality while having low computational complexity. It proposes a compressive sensing (CS) framework for distributed recovery of high-closeness-centrality nodes using only local interactions and this metric. Experiments on synthetic and real-world networks are presented to show that the local metric outperforms existing local metrics in correlation and that the CS method outperforms state-of-the-art approaches with notable improvement.

Significance. If the correlation between the local metric and global closeness holds with sufficient strength and the CS recovery is accurate under the stated conditions, the work would provide a practical distributed method for identifying influential nodes in large networks where global topology is unavailable. This is relevant for network science applications, and the combination of a new local proxy with compressive sensing is a methodological contribution worth evaluating.

major comments (3)
  1. [Abstract] Abstract: The claim that the proposed local metric 'correlates with the global closeness centrality, better than the current local metrics' is load-bearing for the CS recovery step but is asserted without the metric definition, any reported correlation coefficient (e.g., Pearson or Spearman), or minimum threshold, preventing assessment of whether the proxy quality is adequate for accurate top-k recovery.
  2. [Abstract] Abstract: No details are given on the CS measurement matrix construction, recovery algorithm (e.g., basis pursuit or OMP), or quantitative recovery metrics (precision@K, recall, or error rates), which are required to substantiate the 'notable improvement' over state-of-the-art methods.
  3. [Abstract] Abstract: The manuscript does not identify network regimes (diameter, degree heterogeneity, etc.) where the local metric's proxy quality may degrade, leaving the conditions for the CS recovery guarantees unspecified and undermining the generalizability claim.
minor comments (1)
  1. [Abstract] Abstract: The sentence 'The results show that the proposed local metric correlates with the global closeness centrality, better than the current local metrics' contains an unnecessary comma before 'better'.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment below and will make revisions to the abstract and discussion sections to improve clarity and support for the claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The claim that the proposed local metric 'correlates with the global closeness centrality, better than the current local metrics' is load-bearing for the CS recovery step but is asserted without the metric definition, any reported correlation coefficient (e.g., Pearson or Spearman), or minimum threshold, preventing assessment of whether the proxy quality is adequate for accurate top-k recovery.

    Authors: The abstract is space-constrained and summarizes results detailed in the full manuscript. Section 3 defines the local metric, and Section 5 reports quantitative correlations (Pearson and Spearman coefficients) across multiple networks demonstrating consistent outperformance over baselines. We will revise the abstract to include a brief reference to the observed correlation strengths (e.g., typical Spearman rho values) and experimental validation to better substantiate the claim. revision: yes

  2. Referee: [Abstract] Abstract: No details are given on the CS measurement matrix construction, recovery algorithm (e.g., basis pursuit or OMP), or quantitative recovery metrics (precision@K, recall, or error rates), which are required to substantiate the 'notable improvement' over state-of-the-art methods.

    Authors: The abstract summarizes the framework; full details appear in Sections 4 (measurement matrix from local interactions and recovery via basis pursuit) and 5 (precision@K, recall, and error metrics with comparisons). We will add a concise mention of the recovery algorithm and observed quantitative improvements to the abstract. revision: yes

  3. Referee: [Abstract] Abstract: The manuscript does not identify network regimes (diameter, degree heterogeneity, etc.) where the local metric's proxy quality may degrade, leaving the conditions for the CS recovery guarantees unspecified and undermining the generalizability claim.

    Authors: Experiments in Section 5 evaluate the approach on synthetic networks with controlled variation in diameter and degree heterogeneity plus diverse real-world networks. We agree an explicit discussion of potential degradation regimes would strengthen generalizability. We will add a paragraph in the discussion section addressing conditions (e.g., very small-diameter networks) where proxy quality may weaken, based on the empirical results. revision: yes

Circularity Check

0 steps flagged

No circularity: local metric and CS recovery are independent proposals.

full rationale

The paper proposes an ego-centric local metric asserted to correlate with global closeness centrality, then separately applies a compressive sensing framework that uses this metric as input for node recovery. No equations, definitions, or self-citations are shown that reduce either step to a tautology, fitted parameter renamed as prediction, or self-referential construction. The correlation is presented as an empirical observation evaluated on synthetic and real networks rather than enforced by the metric's definition. The derivation chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of a computable local metric with good correlation to global closeness and the standard assumptions of compressive sensing for sparse recovery; no free parameters or invented entities are identifiable from the abstract alone.

axioms (1)
  • standard math Compressive sensing recovers sparse signals from underdetermined linear measurements under suitable conditions
    Invoked for the aggregation framework in the abstract

pith-pipeline@v0.9.0 · 5754 in / 1166 out tokens · 20427 ms · 2026-05-25T19:31:24.135831+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    In: Proceedings of the 2017 IEEE/ACM ASONAM, pp

    Saxena, A., Gera, R., Iyengar, S.: Fast estimation of closeness centrality ranking. In: Proceedings of the 2017 IEEE/ACM ASONAM, pp. 80–85 (2017)

    work page 2017

  2. [2]

    Social Network Analysis and Mining 7(1), 22 (2017)

    Taheri, S.M., Mahyar, H., Firouzi, M., Ghalebi, E., Grosu, R., Movaghar, A.: HellRank: a hellinger-based centrality measure for bipartite social networks. Social Network Analysis and Mining 7(1), 22 (2017)

    work page 2017

  3. [3]

    In: Proceedings of the 26th International Conference on World Wide Web Companion, pp

    Taheri, S.M., Mahyar, H., Firouzi, M., Ghalebi K, E., Grosu, R., Movaghar, A.: Extracting implicit social relation for social recommendation techniques in user rating prediction. In: Proceedings of the 26th International Conference on World Wide Web Companion, pp. 1343–1351 (2017)

    work page 2017

  4. [4]

    In: Simp

    Wehmuth, K., Ziviani, A.: Distributed assessment of the closeness centrality ranking in complex networks. In: Simp. Comp. Net. for Pract. (2012)

    work page 2012

  5. [5]

    IEEE TAC 62(5), 2080–2094 (2017)

    You, K., Tempo, R., Qiu, L.: Distributed algorithms for computation of centrality measures in complex networks. IEEE TAC 62(5), 2080–2094 (2017)

    work page 2080

  6. [6]

    In: International Conference on Complex Networks and Their Applications, pp

    Mahyar, H., Hasheminezhad, R., Ghalebi, E., Grosu, R., Stanley, H.E.: A compressive sensing framework for distributed detection of high closeness centrality nodes in networks. In: International Conference on Complex Networks and Their Applications, pp. 91–103 (2018)

    work page 2018

  7. [7]

    In: IEEE INFOCOM, pp

    Xu, W., Mallada, E., Tang, A.: Compressive sensing over graphs. In: IEEE INFOCOM, pp. 2087–2095 (2011)

    work page 2087

  8. [8]

    In: IEEE ICASSP, Canada, pp

    Mahyar, H., Rabiee, H.R., Hashemifar, Z.S.: UCS-NT: An Unbiased Compressive Sensing Framework for Network Tomography. In: IEEE ICASSP, Canada, pp. 4534–4538 (2013)

    work page 2013

  9. [9]

    Ghalebi, E., Mahyar, H., Grosu, R., Rabiee, H.R.: Compressive sampling for sparse recovery in networks. In: Proc of the 23rd ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 13th International Workshop on Mining and Learning with Graphs, Halifax, Nova Scotia, Canada, pp. 1–8 (2017)

    work page 2017

  10. [10]

    In: IEEE/ACM ASONAM, France, pp

    Mahyar, H., Rabiee, H.R., Movaghar, A., Ghalebi, E., Nazemian, A.: CS-ComDet: A compressive sensing approach for inter-community detection in social networks. In: IEEE/ACM ASONAM, France, pp. 89–96 (2015) Mahyar et al. Page 24 of 24

    work page 2015

  11. [11]

    Physica A: Statistical Mechanics and its Applications 497, 166–184 (2018)

    Mahyar, H., Hasheminezhad, R., Ghalebi, E., Nazemian, A., Grosu, R., Movaghar, A., Rabiee, H.R.: Compressive sensing of high betweenness centrality nodes in networks. Physica A: Statistical Mechanics and its Applications 497, 166–184 (2018)

    work page 2018

  12. [12]

    In: Proc of the 34th International Conference on Machine Learning (ICML), Computational Biology Workshop, Sydney, Australia, pp

    Mahyar, H., Ghalebi, E., Rabiee, H., Grosu, R.: The bottlenecks in biological networks. In: Proc of the 34th International Conference on Machine Learning (ICML), Computational Biology Workshop, Sydney, Australia, pp. 1–5 (2017)

    work page 2017

  13. [13]

    In: IEEE INFOCOM, pp

    Wang, M., Xu, W., Mallada, E., Tang, A.k.: Sparse recovery with graph constraints: Fundamental limits and measurement construction. In: IEEE INFOCOM, pp. 1871–1879 (2012)

    work page 2012

  14. [14]

    IETE technical review 34(6), 642–654 (2017)

    Middya, R., Chakravarty, N., Naskar, M.K.: Compressive sensing in wireless sensor networks–a survey. IETE technical review 34(6), 642–654 (2017)

    work page 2017

  15. [15]

    In: IEEE/ACM ASONAM, Paris, France, pp

    Mahyar, H.: Detection of top-k central nodes in social networks: A compressive sensing approach. In: IEEE/ACM ASONAM, Paris, France, pp. 902–909 (2015)

    work page 2015

  16. [16]

    In: IEEE SocialCom, Chengdu, China, pp

    Mahyar, H., Rabiee, H.R., Movaghar, A., Hasheminezhad, R., Ghalebi, E., Nazemian, A.: A low-cost sparse recovery framework for weighted networks under compressive sensing. In: IEEE SocialCom, Chengdu, China, pp. 183–190 (2015)

    work page 2015

  17. [17]

    In: Principles of Modeling, pp

    Grosu, R., Ghalebi, E., Movaghar, A., Mahyar, H.: Compressed sensing in cyber physical social systems. In: Principles of Modeling, pp. 287–305 (2018)

    work page 2018

  18. [18]

    Social Network Analysis and Mining 8(1), 33 (2018)

    Mahyar, H., Hasheminezhad, R., Ghalebi, E., Nazemian, A., Grosu, R., Movaghar, A., Rabiee, H.R.: Identifying central nodes for information flow in social networks using compressive sensing. Social Network Analysis and Mining 8(1), 33 (2018)

    work page 2018

  19. [19]

    In: Decision and Control (CDC), 2015 IEEE 54th Annual Conference On, pp

    Wang, W., Tang, C.Y.: Distributed estimation of closeness centrality. In: Decision and Control (CDC), 2015 IEEE 54th Annual Conference On, pp. 4860–4865 (2015)

    work page 2015

  20. [20]

    In: ICCCN, pp

    Kim, H., Yoneki, E.: Influential neighbours selection for information diffusion in online social networks. In: ICCCN, pp. 1–7 (2012)

    work page 2012

  21. [21]

    Soc Net 31(2), 155–163 (2009)

    Opsahl, T., Panzarasa, P.: Clustering in weighted networks. Soc Net 31(2), 155–163 (2009)

    work page 2009

  22. [22]

    In: Http://rankinfo.pkqs.net/twittercrawl.dot.gz (2018)

    Twitter: Gephi platform. In: Http://rankinfo.pkqs.net/twittercrawl.dot.gz (2018)

    work page 2018

  23. [23]

    ACM TKDD 1(1), 2 (2007)

    Leskovec, J., Kleinberg, J., Faloutsos, C.: Graph evolution: Densification and shrinking diameters. ACM TKDD 1(1), 2 (2007)

    work page 2007

  24. [24]

    Internet Mathematics 6(1), 29–123 (2009)

    Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6(1), 29–123 (2009)

    work page 2009

  25. [25]

    Knowledge and Information Systems 42(1), 181–213 (2015)

    Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42(1), 181–213 (2015)

    work page 2015

  26. [26]

    In: WWW, pp

    Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: WWW, pp. 641–650 (2010)

    work page 2010

  27. [27]

    Science 286(5439), 509–512 (1999)

    Barabasi, A.L., Albert, R.: Emregence of scaling in random networks. Science 286(5439), 509–512 (1999)

    work page 1999

  28. [28]

    In: Publication of the Mathematical Institute of the Hungarian Academy of Science, pp

    Erdos, P., Renyi, A.: On the evolution of random graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Science, pp. 17–61 (1960)

    work page 1960

  29. [29]

    Nature 393(6684), 440–442 (1998)

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

    work page 1998

  30. [30]

    In: Http://foges.github.io/pogs/ (2018)

    POGS: Proximal operator graph solver. In: Http://foges.github.io/pogs/ (2018)

    work page 2018

  31. [31]

    Mathematical Programming Computation 6(1), 77–102 (2014)

    Parikh, N., Boyd, S.: Block splitting for distributed optimization. Mathematical Programming Computation 6(1), 77–102 (2014)

    work page 2014

  32. [32]

    Noise reduction in speech processing, 1–4 (2009)

    Benesty, J., Chen, J., Huang, Y., Cohen, I.: Pearson correlation coefficient. Noise reduction in speech processing, 1–4 (2009)

    work page 2009

  33. [33]

    PhD thesis, Universit¨ at Konstanz, Konstanz (2015)

    Schoch, D.: A positional approach for network centrality. PhD thesis, Universit¨ at Konstanz, Konstanz (2015)

    work page 2015

  34. [34]

    In: CISS, USA (2013)

    Mahyar, H., Rabiee, H.R., Hashemifar, Z.S., Siyari, P.: UCS-WN: An Unbiased Compressive Sensing Framework for Weighted Networks. In: CISS, USA (2013)

    work page 2013