Algorithms and Experiments for Betweenness Centrality in Tree-Like Networks
Alexander Dittmann (TU Berlin)
When it comes to analyzing networks the betweenness centrality is a
standard measure to
rank the importance of the vertices in a network. The betweenness centrality represents
the relative number of shortest paths a vertex lies on in a network. Finding vertices with
a high betweenness centrality and thus vertices that are important for the network, has
several applications in different fields of science, for example in sociology, biology and
The currently best known algorithms for computing the betweenness centrality for
each vertex of a network have a running time of (O(nm)), where (n) is the number of
vertices and (m) is the number of edges in the network. This running time however is not
feasible for very big instances of networks. This motivates to find faster algorithms or
to improve existing algorithms to make the betweenness centrality a usable method of
analysis even for these instances which are currently to big for practical use.
One such (O(nm))-algorithm is the one of Brandes’ [J Math Sociol 2001]. Baglioni
et al. [ASONAM 2012] improved Brandes’ algorithm by deleting degree-one vertices
in the network before running Brandes’ algorithm on the network. If enough vertices
are deleted, then this can be a significant speed up. In this work we follow this idea.
In particular we provide a parameterized algorithm with respect to the feedback edge
number, which involves the deletion of some vertices of degree two.
Back to the research colloquium site.