Lecture by Henning Meyerhenke (Humboldt-Universität zu Berlin): Algorithms for Large-scale Network Analysis
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.
Time & Location
Nov 05, 2018 | 02:15 PM
Humboldt-Universität zu Berlin
Institut für Informatik
Room 3.408 (House 3 / 4th Floor [British Reading])
Johann von Neumann-Haus
Rudower Chaussee 25