An Efficient Approximate Algorithm for the 1-Median Problem on a Graph
An Efficient Approximate Algorithm for the 1-Median Problem on a Graph
复制标题
图上一中值问题的高效近似算法
DOI：
10.1587/transinf.2016edp7398
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Mineichi Kudo
中科院分区：
文献类型：
--
作者：
Koji Tabata;Atsuyoshi Nakamura;Mineichi Kudo
我们提出了一种求解1-中值问题的启发式近似算法。1-中值问题是寻找具有最高接近中心性的顶点的问题。从随机选择的顶点开始，我们的算法通过使用更简单的生成子图（称为带捷径的k邻密集最短路径图）近似计算每个顶点的接近中心性来重复寻找具有更高接近中心性的顶点。根据我们使用超过10,000个顶点的真实网络的实验结果，我们的算法比穷举搜索快100倍以上，比最先进的使用顶点注释信息的近似算法快20倍以上，并且我们的算法输出的解具有更高的近似比。
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.
DOI：
10.1007/978-3-540-69311-6_21
发表时间：
2008-06
期刊：
--
影响因子：
--
作者：
K. Okamoto;Wei Chen-;Xiangyang Li
通讯作者：
K. Okamoto;Wei Chen-;Xiangyang Li