### Inhalt des Dokuments

# 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

computer science.

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.

Date | Speaker | Location | Language |
---|---|---|---|

7.12.2017 16:15 | Alexander Dittmann | TEL 512 | English |