  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.
