## Dec 1 2000:

"Fast Approximation of Centrality"
(Joint work with David Eppstein)

Speaker: Joseph Wang, ICS, UC Irvine

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.

**Note**: this talk is to be
given as part of the Southern California Theory Day, so the
time will probably be different from the usual 1pm.