CENTRALITY ESTIMATION IN LARGE NETWORKS

2007/07/01 by Ulrik Brandes, ULRIK BRANDES, CHRISTIAN PICH +1 · 6 citations
Physics and Astronomy · Biochemistry, Genetics and Molecular Biology · Mathematics · #Complex Network Analysis Techniques #Bioinformatics and Genomic Networks #Graph theory and applications

paper · doi:10.1142/s0218127407018403

Abstract

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.

Citations

• The Centrality Index of a Graph
• A unified approach to approximation algorithms for bottleneck problems
• Authoritative sources in a hyperlinked environment
• Random Graphs

Cited by

• Discovering the Network Backbone from Traffic Activity Data
• Centrality Measures in Complex Networks: A Survey
• Vertex Ordering Algorithms for Graph Coloring Problem
• ralphi: a deep reinforcement learning framework for haplotype assembly
• Betweenness computation in the single graph representation of hypergraphs
• Betweenness Centrality : Algorithms and Lower Bounds

Related

• On Local and Global Centrality in Large Scale Networks
• Centrality Measures in Networks
• Centrality Measures in Complex Networks: A Survey
• Generalized Centrality Aggregation and Exclusive Centrality
• Range-limited Centrality Measures in Complex Networks