Paper Info
Title
Measuring and maximizing group closeness centrality over disk-resident graphs
Abstract
As an important metric in graphs, group closeness centrality measures how close a group of vertices is to all other vertices in a graph, and it is used in numerous graph applications such as measuring the dominance and influence of a node group over the graph. However, when a large-scale graph contains hundreds of millions of nodes/edges which cannot reside entirely in computer's main memory, measuring and maximizing group closeness become challenging tasks. In this paper, we present a systematic solution for efficiently calculating and maximizing the group closeness for disk-resident graphs. Our solution first leverages a probabilistic counting method to efficiently estimate the group closeness with high accuracy, rather than exhaustively computing it in an exact fashion. In addition, we design an I/O-efficient greedy algorithm to find a node group that maximizes group closeness. Our proposed algorithm significantly reduces the number of random accesses to disk, thereby dramatically improving computational efficiency. Experiments on real-world big graphs demonstrate the efficacy of our approach.
Year
DOI
Venue
2014
10.1145/2567948.2579356
WWW (Companion Volume)
Keywords
Field
DocType
disk-resident graph,o-efficient greedy algorithm,real-world big graph,numerous graph application,maximizes group closeness,large-scale graph,group closeness centrality measure,proposed algorithm,group closeness,node group,greedy algorithm
Graph center,Data mining,Graph,Mathematical optimization,Random walk closeness centrality,Vertex (geometry),Computer science,Closeness,Centrality,Greedy algorithm,Theoretical computer science,Probabilistic logic
Conference
Citations 
PageRank 
References 
3
0.43
14
Authors
4
Name
Order
Citations
PageRank
Junzhou Zhao110418.36
John C.S. Lui23680279.85
Don Towsley3186931951.05
X. Guan41169137.97