[Dmbu-l] Fast Approximation of Betweenness Centrality through Sampling: Friday @ 11AM, MCS 148
cmav at bu.edu
Tue Oct 15 11:00:32 EDT 2013
*Fast Approximation of Betweenness Centrality through Sampling*
*Matteo Riondato, Brown University*
*Friday, October 18, 2013 at 11AM in MCS 148**
*Abstract: *Betweenness centrality is a fundamental measure in social
analysis, expressing the importance or influence of individual vertices
in a network in terms of the fraction of shortest paths that pass
through them. Exact computation in large networks is prohibitively
expensive and fast approximation algorithms are required in these cases.
We present two efficient randomized algorithms for betweenness
estimation. The algorithms are based on random sampling of shortest
paths and offer probabilistic guarantees on the quality of the
approximation. The first algorithm estimates the betweenness of all
vertices: all approximated values are within an additive factor ε from
the real values, with probability at least 1 - δ. The second algorithm
focuses on the top-K vertices with highest betweenness and approximate
their betweenness within a multiplicative factor ε, with probability at
least 1 - δ. This is the first algorithm that can compute such
approximation for the top-K vertices. We use results from the
VC-dimension theory to develop bounds to the sample size needed to
achieve the desired approxi- mations. By proving upper and lower bounds
to the VC-dimension of a range set associated with the problem at hand,
we obtain a sample size that is independent from the number of vertices
in the network and only depends on a characteristic quantity that we
call the vertex-diameter, that is the maximum number of vertices in a
shortest path. In some cases, the sample size is completely independent
from any property of the graph.
This is joint work with Evgenios M. Kornaropoulos.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Dmbu-l