Today I read a paper titled “Fast Approximation of Centrality”
The abstract is:
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.