Consistent Identification of Top-$K$ Nodes in Noisy Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914597015912448 |
|---|---|
| author | Shen, Hui Kolaczyk, Eric D. |
| author_facet | Shen, Hui Kolaczyk, Eric D. |
| contents | Identifying the most influential nodes in a network, typically using centrality measures, is a central task in applied network analysis. However, real-world networks are often constructed from noisy or incomplete data, which can distort rankings and lead to errors in identifying the true top-$k$ nodes. In this paper, we study how network noise affects the recovery of the true top-$k$ node set based on degree centrality. Specifically, we consider a noisy network observation in which edges are randomly added or removed according to a probabilistic noise model, and analyze the resulting empirical top-$k$ set. We show that top-$k$ recovery under network noise is governed by the relationship between the degree gap and the noise magnitude, which separates recoverable and unrecoverable regimes. To quantify ranking stability, we derive upper and lower bounds on the expected discrepancy between the empirical and true top-$k$ sets in a general framework and for specific network models. We also extend the analysis to eigenvector centrality, showing that similar noise-gap tradeoffs arise in spectral rankings. Simulation studies support our theoretical findings and illustrate the practical impact of network noise across a range of settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24734 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Consistent Identification of Top-$K$ Nodes in Noisy Networks Shen, Hui Kolaczyk, Eric D. Statistics Theory Identifying the most influential nodes in a network, typically using centrality measures, is a central task in applied network analysis. However, real-world networks are often constructed from noisy or incomplete data, which can distort rankings and lead to errors in identifying the true top-$k$ nodes. In this paper, we study how network noise affects the recovery of the true top-$k$ node set based on degree centrality. Specifically, we consider a noisy network observation in which edges are randomly added or removed according to a probabilistic noise model, and analyze the resulting empirical top-$k$ set. We show that top-$k$ recovery under network noise is governed by the relationship between the degree gap and the noise magnitude, which separates recoverable and unrecoverable regimes. To quantify ranking stability, we derive upper and lower bounds on the expected discrepancy between the empirical and true top-$k$ sets in a general framework and for specific network models. We also extend the analysis to eigenvector centrality, showing that similar noise-gap tradeoffs arise in spectral rankings. Simulation studies support our theoretical findings and illustrate the practical impact of network noise across a range of settings. |
| title | Consistent Identification of Top-$K$ Nodes in Noisy Networks |
| topic | Statistics Theory |
| url | https://arxiv.org/abs/2605.24734 |