時々刻々と成長するグラフのための中心性モニタリング

情報処理学会 Web Site 被引用文献1件

書誌事項

タイトル別名
  • ジジコッコク ト セイチョウ スル グラフ ノ タメ ノ チュウシンセイ モニタリング
  • Centrality Monitoring for Time-evolving Graphs

この論文をさがす

抄録

本論文では時々刻々とノードの数を増やしながら成長するグラフの中から，他のノードまでの距離の和が最小になるノード（最も距離中心性の高いノード）と他のノードまでの距離の最大値が最も小さくなるノード（最も離心中心性の高いノード）を効率的かつ正確に検出し続ける問題を対象とする．過去のこの問題に対する手法では最も中心性の高いノードを高速に求めることができる代わりに計算結果の正確性を犠牲にしていた．本論文は正確性を犠牲にしないで最も中心性の高いノードを求めることができないかということを動機にしている．提案手法は(1)解の正確性を保ったまま元のグラフを縮退してグラフの近似を行い，その近似グラフにおける中心性の値を計算し，(2)中心性を求めるときに不必要な計算を早期に打ち止めるという2つのアプローチで構成される．これらのアプローチにより数多くのノードを枝刈りできるために効率的な検出が可能になる．理論的解析により提案手法は検出結果が正確であり，また必要となる計算量は従来の手法より少ないオーダとなることが分かった．数十万ノードを含む実データで検証を行ったところ，提案手法は解の正確性を保証したまま従来手法と比較して非常に高速であることが確認された．

The goal of this work is to identify the nodes that have the smallest sum of distances to other nodes (the lowest closeness centrality nodes) and the nodes that minimizes the maximum distance to all other nodes (the lowest eccentricity nodes) from graphs that evolve over time. Previous approaches for this problem find the lowest centrality nodes efficiently at the expense of exactness. The main motivation of this paper is to answer the question, ‘Is it possible to improve the search time without sacrificing the exactness?'. Our solution is based on two ideas: (1) It computes approximate centrality by reducing the original graph size while guaranteeing the answer exactness, and (2) It terminates unnecessary distance computations early when pruning unlikely nodes. Our theoretical analyses show that our approach guarantees exactness of the answer and that it has a lower order of space and time complexities than the previous approaches. We perform several experiments to verify the efficiency of our approach with real and large datasets that contain several hundreds of thousands of nodes. The results show that our approach can find the lowest centrality nodes ignificantly faster than the previous approaches while it guarantees the answer exactness.

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ