機能性に基づくコミュニティ抽出法の比較  [in Japanese] Comparison of Community Extraction Method Based on Functionality Equivalence  [in Japanese]

Access this Article

Search this Article

Abstract

本稿では,ネットワークに対する各ノードの役割・機能・立場が類似したノードからなるコミュニティを抽出することを主題とする.周辺ノードとのリンク関係の類似性,すなわち同値性を同定するための Versim 法, Simrank 法と呼ぶ従来の手法,および機能の類似するノード群を抽出する Randwalk 法の 3 手法に着目する. Randwalk 法は,ネットワーク全体でのランダムウォークにより類似経路構造を探す方法であり, PageRank 反復計算時のスコア収束曲線の類似性を用いる手法である.結果より,局所的なリンク構造に着目する Versim 法と Simrank 法では,手法の問題点が顕著に現れる人工ネットワークや表出する構造にバラつきのある現実ネットワークへの適用に限界があることを示す.一方,大域的な構造上での現象の類似性による Randwalk 法は,現実ネットワークに対しても機能が類似するノード群を抽出可能であることを示す.In this paper, we attempt to extract communities in a given network, each of which consists of nodes with a homogeneous role or function. To this end, we focus on three methods using respective node similarity based on regular equivalence, i.e., two conventional methods refered to as Versim and Simrank, and a recently proposed method refered to as Randwalk, which calculates the node similarity based on the convergence process of a PageRank score. By our experimental results using some artificial and real networks, we show that the Versim and Simrank methods have some real limitations to apply to real networks because of directly focusing on local link structures. On the other hand, the Randwalk method more explicitly extracted fucntional community, charcterized by similarity from a relative location, role, or hierarchical status. This is because the Randwalk method focuses on the similarity of phenomena on the global link structure.

In this paper, we attempt to extract communities in a given network, each of which consists of nodes with a homogeneous role or function. To this end, we focus on three methods using respective node similarity based on regular equivalence, i.e., two conventional methods refered to as Versim and Simrank, and a recently proposed method refered to as Randwalk, which calculates the node similarity based on the convergence process of a PageRank score. By our experimental results using some artificial and real networks, we show that the Versim and Simrank methods have some real limitations to apply to real networks because of directly focusing on local link structures. On the other hand, the Randwalk method more explicitly extracted fucntional community, charcterized by similarity from a relative location, role, or hierarchical status. This is because the Randwalk method focuses on the similarity of phenomena on the global link structure.

Journal

  • 情報処理学会論文誌データベース(TOD)

    情報処理学会論文誌データベース(TOD) 5(3), 26-35, 2012-09-28

    情報処理学会

Codes

  • NII Article ID (NAID)
    110009456273
  • NII NACSIS-CAT ID (NCID)
    AA11464847
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7799
  • NDL Article ID
    024049216
  • NDL Call No.
    YH247-812
  • Data Source
    NDL  NII-ELS  IPSJ 
Page Top