講演抄録/キーワード |
講演名 |
2011-10-21 10:35
Closeness Centralityの高いノードを発見する高速アルゴリズム ○田畑公次・中村篤祥・工藤峰一(北大) COMP2011-29 |
抄録 |
(和) |
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. |
キーワード |
(和) |
中心性 / グラフマイニング / スケールフリーグラフ / / / / / |
(英) |
Centrality / Graph mining / Scale Free Graph / / / / / |
文献情報 |
信学技報, vol. 111, no. 256, COMP2011-29, pp. 7-14, 2011年10月. |
資料番号 |
COMP2011-29 |
発行日 |
2011-10-14 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-29 |