[Dmbu-l] Fast Approximation of Betweenness Centrality through Sampling: Friday @ 11AM, MCS 148

Charalampos Mavroforakis cmav at bu.edu
Wed Oct 16 11:47:40 EDT 2013

Hi all,

If you are interested in meeting with Matteo, send me an email and I'll
arrange it for you.


- Harry

On Tue, Oct 15, 2013 at 11:00 AM, Charalampos Mavroforakis <cmav at bu.edu>wrote:

> *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
> network
> 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.
> - Harry
> http://cs-people.bu.edu/cmav/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20131016/bf8c083e/attachment.html>

More information about the Dmbu-l mailing list