ネットワーク構造に対するコミュニティの高速抽出手法

塩川 浩昭  藤原 靖宏  鬼塚 真  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.5   pp.1145-1157
発行日: 2013/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (データ工学と情報マネジメント論文特集)
専門分野: ネットワークコミュニティ分析
キーワード: 
ネットワーク構造,  コミュニティ抽出,  データマイニング,  ソーシャルネットワーク,  

本文: PDF(1.2MB)
>>論文を購入


あらまし: 
ソーシャルグラフに代表される様々なネットワーク構造の登場により,これらに対する高速なコミュニティ抽出手法が重要な技術要素となっている.しかしながら,近年研究されてきたコミュニティ抽出手法では,ネットワーク構造に対して膨大な処理時間が必要となるだけでなく,計算対象となるノードの選択順序に依存して処理時間が大幅に増加する問題点が我々の検証により明らかになった.そこで本論文ではネットワーク構造に対するコミュニティ抽出手法の高速化について取り組む.本論文で提案するコミュニティ抽出手法はコミュニティに含まれるノードを逐次的に集約することにより,計算対象となるエッジを削減し高速化を実現する.本論文では提案手法のプロトタイプを作成し,現在最速とされる既存手法に対して,コミュニティ抽出精度を同程度に示しつつ,約10倍から約60倍程度高速化可能であることを示した.