KIT | KIT-Bibliothek | Impressum

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 edge ... mehr

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2017
Sprache Englisch
Identifikator DOI(KIT): 10.5445/IR/1000069278
ISSN: 2190-4782
URN: urn:nbn:de:swb:90-692782
KITopen ID: 1000069278
Verlag 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