[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - November 5th 2018

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our Monday Lecture & Colloquium on November 5th at 14:15 h & 16:00 h at HU Berlin.

Location:

Room 3.408 (House 3 / 4th Floor) [British Reading]
Humboldt-Universität zu Berlin
Institut für Informatik
Johann von Neumann-Haus
Rudower Chaussee 25
12489 Berlin

Time: Monday, November 5th - 14:15 h

Lecture: Henning Meyerhenke (Humboldt-Universität zu Berlin)

Title: Algorithms for Large-scale Network Analysis

Abstract:

Network centrality measures indicate the importance of nodes (or edges) in a network. In this talk we will discuss a few popular measures and algorithms for computing complete or partial node rankings based on these measures. These algorithms are implemented in NetworKit, an open-source framework for large-scale network analysis, on which we provide an overview, too.

One focus of the talk will be on techniques for speeding up a greedy (1-1/e)-approximation algorithm for the NP-hard group closeness centrality problem.
Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to a heuristic proposed by Chen et al., we always find a solution with better quality in a comparable running time in our experiments. Our
method Greedy++ allows us to approximate the group with maximum closeness centrality on networks with up to hundreds of millions of edges in minutes or at most a few hours.
In a comparison with the optimum, our experiments show that the solution found by Greedy++ is actually much better than the theoretical guarantee.

Coffee & Tea Break :

Room 3.321 (House 3 / 3rd Floor) [British Reading]

Time: Monday, November 5th - 16:00 h

Colloquium: Alexander van der Grinten (Universität zu Köln)

Title: Scalable Katz Ranking Computation

Abstract:

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. We consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. For a certain class of inputs, this yields an optimal algorithm for Katz ranking computation. Furthermore, Experiments demonstrate that our algorithm outperforms both numerical approaches and heuristics with speedups between 1.5x and 3.5x, depending on the desired quality guarantees. Specifically, we provide efficient parallel CPU and GPU implementations of the algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.