重複コミュニティ発見のための重み付き線グラフ  [in Japanese] Weighted Line Graphs for Overlapping Community Discovery  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本稿では,複数のコミュニティへの所属を許容する重複コミュニティの発見を実現するために,ネットワークの重みを反映する重み付き線グラフを提案する.従来のノード分割に基づくコミュニティ発見手法ではノードは 1 つのコミュニティに割り当てられるため,複数のコミュニティには所属できないという課題がある.この課題に対し,本稿ではネットワークをその線グラフに変換し,変換後の線グラフにノード分割手法を適用することにより重複コミュニティ発見を実現する.従来の線グラフはネットワークの接続関係のみから定義されるが,ネットワークの重みを活用したリンク分割を実現するため,重みに基づいて拡張した重み付き線グラフを提案し,その性質を示す.さらに,ノード分割に基づくモジュラリティを拡張し,重複コミュニティ発見におけるソフトなノード分割に対するモジュラリティを提案する.提案法を人工ネットワークと実世界のネットワークに適用し,他手法との比較を通じてその有効性を示す.We propose an approach for overlapping community discovery via weighted line graphs of networks. For undirected connected networks without self-loops, we propose weighted line graphs by: 1) defining weights of a line graph based on the weights in the original network, and 2) removing self-loops in weighted line graphs, while sustaining their properties. By applying some off-the-shelf node partitioning method to the weighted line graph, the node in the original network can be assigned to more than one community based on the community labels of its adjacent links. Various properties of the proposed weighted line graphs are clarified. Furthermore, we propose a generalized quality measure for soft assignment of nodes in overlapping communities. Preliminary experiments are conducted over synthetic and real-world networks, and the results indicate that the proposed approach can improve the quality of discovered overlapping communities.

We propose an approach for overlapping community discovery via weighted line graphs of networks. For undirected connected networks without self-loops, we propose weighted line graphs by: 1) defining weights of a line graph based on the weights in the original network, and 2) removing self-loops in weighted line graphs, while sustaining their properties. By applying some off-the-shelf node partitioning method to the weighted line graph, the node in the original network can be assigned to more than one community based on the community labels of its adjacent links. Various properties of the proposed weighted line graphs are clarified. Furthermore, we propose a generalized quality measure for soft assignment of nodes in overlapping communities. Preliminary experiments are conducted over synthetic and real-world networks, and the results indicate that the proposed approach can improve the quality of discovered overlapping communities.

Journal

  • 情報処理学会論文誌数理モデル化と応用(TOM)]

    情報処理学会論文誌数理モデル化と応用(TOM)] 5(3), 79-88, 2012-09-28

    情報処理学会

Codes

  • NII Article ID (NAID)
    110009456292
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    JPN
  • Article Type
    Article
  • ISSN
    1882-7780
  • NDL Article ID
    024049045
  • NDL Call No.
    YH247-812
  • Data Source
    NDL  NII-ELS  IPSJ 
Page Top