ICS Theory Group

ICS 269, Fall 2000: Theory Seminar

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.