An Efficient Approximate Algorithm for the 1-Median Problem on a Graph

Koji TABATA  Atsuyoshi NAKAMURA  Mineichi KUDO  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E100-D   No.5   pp.994-1002
Publication Date: 2017/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7398
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
1-median problem,  closeness centrality,  graph mining,  

Full Text: PDF(339.3KB)>>
Buy this Article




Summary: 
We propose a heuristic approximation algorithm for the 1-median problem. The 1-median problem is the problem of finding a vertex with the highest closeness centrality. Starting from a randomly selected vertex, our algorithm repeats to find a vertex with higher closeness centrality by approximately calculating closeness centrality of each vertex using simpler spanning subgraphs, which are called k-neighbor dense shortest path graphs with shortcuts. According to our experimental results using real networks with more than 10,000 vertices, our algorithm is more than 100 times faster than the exhaustive search and more than 20 times faster than the state-of-the-art approximation algorithm using annotated information to the vertices while the solutions output by our algorithm have higher approximation ratio.