BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 th
ese measures. These algorithms are implemented in NetworKit\, an open-sourc
e framework for large-scale network analysis\, on which we provide an overv
iew\, 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 cen
trality problem. Compared to a straightforward implementation\, our approa
ch 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 approxi
mate the group with maximum closeness centrality on networks with up to hun
dreds of millions of edges in minutes or at most a few hours. In a compari
son with the optimum\, our experiments show that the solution found by Gree
dy++ is actually much better than the theoretical guarantee.
DTSTAMP:20181105T173400
DTSTART:20181105T141500
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Room 3.
408 (House 3 / 4th Floor [British Reading])\n Johann von Neumann-Haus\n Rud
ower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Henning Meyerhenke (Humboldt-Universität zu Berlin): Algorithms for
Large-scale Network Analysis
UID:94302207@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20181105-L-Meyerhenke.html
END:VEVENT
END:VCALENDAR