Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00081 Fast Approximation of Centrality David Eppstein and Joseph Wang Vol. 8, no. 1, pp. 39-45, 2004. Concise paper Abstract Social scientists 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+ϵ) factor in ~O(m) time.
|
Submitted: March 2001. Revised: March 2004. Communicated by Martin Fürer |
Journal of Graph Algorithms and Applications |