Intelligent Systems
Note: This research group has relocated.

Sampling on networks: estimating spectral centrality measures and their impact in evaluating other relevant network measures

2020

Article

pio


We perform an extensive analysis of how sampling impacts the estimate of several relevant network measures. In particular, we focus on how a sampling strategy optimized to recover a particular spectral centrality measure impacts other topological quantities. Our goal is on one hand to extend the analysis of the behavior of TCEC [Ruggeri2019], a theoretically-grounded sampling method for eigenvector centrality estimation. On the other hand, to demonstrate more broadly how sampling can impact the estimation of relevant network properties like centrality measures different than the one aimed at optimizing, community structure and node attribute distribution. Finally, we adapt the theoretical framework behind TCEC for the case of PageRank centrality and propose a sampling algorithm aimed at optimizing its estimation. We show that, while the theoretical derivation can be suitably adapted to cover this case, the resulting algorithm suffers of a high computational complexity that requires further approximations compared to the eigenvector centrality case.

Author(s): Ruggeri, Nicolò and De Bacco, Caterina
Journal: Applied Network Science
Volume: 5:81
Year: 2020
Month: October

Department(s): Physics for Inference and Optimization
Bibtex Type: Article (article)
Paper Type: Journal

DOI: https://doi.org/10.1007/s41109-020-00324-9
State: Published

Links: Code
Preprint
pdf

BibTex

@article{tcec_ext,
  title = {Sampling on networks: estimating spectral centrality measures and their impact in evaluating other relevant network measures},
  author = {Ruggeri, Nicolò and De Bacco, Caterina},
  journal = {Applied Network Science},
  volume = {5:81},
  month = oct,
  year = {2020},
  doi = {https://doi.org/10.1007/s41109-020-00324-9},
  month_numeric = {10}
}