Fast Approximation of Centrality
<|reference_start|>Fast Approximation of Centrality: Social studies researchers use graphs to model group activities in social networks. An important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex. We describe a randomized approximation algorithm for centrality in weighted graphs. For graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a (1+epsilon) factor in near-linear time.<|reference_end|>
@article{eppstein2000fast,
    title={Fast Approximation of Centrality},
    author={David Eppstein and Joseph Wang},
    journal={J. Graph Algorithms & Applications 8(1):27-38, 2004},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0009005},
    primaryClass={cs.DS cond-mat.dis-nn cs.SI}
}