KIT | KIT-Bibliothek | Impressum | Datenschutz

Scaling up Group Closeness Maximization

Bergamini, Elisabetta; Gonser, Tanya; Meyerhenke, Henning

Closeness is a widely-used centrality measure in social network analysis. For a node it indicates the inverse average shortest-path distance to the other nodes of the network. While the identification of the k nodes with highest closeness received significant attention, many applications are actually interested in finding a group of nodes that is central as a whole. For this problem, only recently a greedy algorithm with approximation ratio (1−1/e) has been proposed [Chen et al., ADC 2016]. Since this algorithm’s running time is still expensive for large networks, a heuristic without approximation guarantee has also been proposed in the same paper.
In the present paper we develop new techniques to speed up the greedy algorithm without losing its theoretical guarantee. Compared to a straightforward implementation, our approach is orders of magnitude faster and, compared to the 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 on networks with up to hundreds of millions of edges in minutes or at most a few hours. ... mehr

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000069278
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2017
Sprache Englisch
Identifikator ISSN: 2190-4782
KITopen-ID: 1000069278
Verlag KIT, Karlsruhe
Umfang 17 S.
Serie Karlsruhe Reports in Informatics ; 2017,8
Schlagworte Graph algorithms, network analysis, closeness centrality, group centrality
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page