Closeness Centrality の高いノードを発見する高速アルゴリズム  [in Japanese] Fast Algorithm for Finding a Graph Node with High Closeness Centrality  [in Japanese]

Search this Article

Author(s)

    • 田畑 公次 TABATA Koji
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University
    • 工藤 峰一 KUDO Mineichi
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

Abstract

Closeness Centralityはグラフにおけるノードの中心性を表す尺度の一つである.あるノードのCloseness Centralityは,そのノードから他のすべてのノードまでの距離の和の逆数として計算される.本報告では,無向グラフに対しCloseness Centralityが大きいノードを高速に発見するアルゴリズムを提案する.提案法は,与えられたグラフのノードvに対し,vを根とする最短経路木Tを構築し,TにおいてCloseness Centerを新たなvとして同じ手続きを繰り返すアルゴリズムである.頂点の次数分布がべき乗則に従う場合には,高い確率でCloseness Centralityがほぼ最大のノードを見つけることができることが実験的に示された.

The Closeness Centrality is one of centrality measures of a node in a graph. It is calculated as the reciprocal of the sum of distances to all other nodes. In this paper, we propose a fast approximate algorithm that finds the node to maximize its closeness centrality in an undirected graph. Given a node v, the algorithm repeatedly find a node with higher closeness centrality by making use of a shortest path tree of the previous node. According to out experiment, our algorithm can find a node with almost maximum closeness centrality with high probability.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 111(256), 7-14, 2011-10-14

    The Institute of Electronics, Information and Communication Engineers

References:  11

Codes

  • NII Article ID (NAID)
    110008900056
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    0913-5685
  • NDL Article ID
    023345318
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top