Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00081
Fast Approximation of Centrality
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.
|
Journal Supporters
|