Centrality Estimation in Large Networks

By U. Brandes, Christian Pich. International Journal of Bifurcation and Chaos in Applied Sciences and Engineering, 2007

431 citations recorded by the source corpus.

Centrality indices are an essential concept in network analysis. For those based on shortest-path distances the computation is at least quadratic in the number of nodes, since it usually involves solving the single-source shortest-paths (SSSP) problem from every node. Therefore, exact computation is infeasible for many large networks of interest today. Centrality scores can be estimated, however, from a limited number of SSSP computations. We present results from an experimental study of the quality of such estimates under various selection strategies for the source vertices.

Subfields: Geometry and Topology, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/2e0d94d072d79ba73c9a153a228b93520b3ce670

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

1. David A. Bader
2. Milena Mihail
3. Shiva Kintali
4. Kamesh Madduri
5. David M. Beskow

In Statistical and Nonlinear Physics

1. David A. Bader
2. Milena Mihail
3. Shiva Kintali
4. Kamesh Madduri
5. David M. Beskow

Citations in the corpus

• Approximating Betweenness Centrality (2007, background): “Recently, Brandes and Pich [18] presented centrality estimation heuristics, where they experimented with different strategies for selecting the source vertices.”