### 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 |

Back to the research colloquium site. [1]

To top

_term_2017/