IEICE TRANSACTIONS on Information
An Efficient Approximate Algorithm for the 1-Median Problem on a Graph
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.5 pp.994-1002
- Publication Date
- 2017/05/01
- Publicized
- 2017/01/23
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016EDP7398
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Koji TABATA
Hokkaido University
Atsuyoshi NAKAMURA
Hokkaido University
Mineichi KUDO
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Koji TABATA, Atsuyoshi NAKAMURA, Mineichi KUDO, "An Efficient Approximate Algorithm for the 1-Median Problem on a Graph" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 5, pp. 994-1002, May 2017, doi: 10.1587/transinf.2016EDP7398.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016EDP7398/_p
Copy
@ARTICLE{e100-d_5_994,
author={Koji TABATA, Atsuyoshi NAKAMURA, Mineichi KUDO, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Approximate Algorithm for the 1-Median Problem on a Graph},
year={2017},
volume={E100-D},
number={5},
pages={994-1002},
abstract={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.},
keywords={},
doi={10.1587/transinf.2016EDP7398},
ISSN={1745-1361},
month={May},}
Copy
TY - JOUR
TI - An Efficient Approximate Algorithm for the 1-Median Problem on a Graph
T2 - IEICE TRANSACTIONS on Information
SP - 994
EP - 1002
AU - Koji TABATA
AU - Atsuyoshi NAKAMURA
AU - Mineichi KUDO
PY - 2017
DO - 10.1587/transinf.2016EDP7398
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 2017
AB - 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.
ER -
English
