グラフィックアルゴリズム-Community検出アルゴリズム

🧐 Community detection algorithms

ネットワークにおいて他のクラスタよりも密集しているクラスタ,すなわちモジュール化の度合いが高いクラスタをコミュニティと呼ぶ.Community detectionアルゴリズムは、クラスタ全体にどのようなコミュニティがあるか、およびこれらのコミュニティがどのような特性を持っているかを分析する方法です.

1. Louvain

LouvainアルゴリズムはCommunity検出の1つの方法であり,関係密度を適切に定義されたランダムネットワークと比較することによってコミュニティの品質を測定する.

第1段階:1つのノードを隣接する他のコミュニティに配置してモジュール性を測定する.モジュール化の度合いがより高いコミュニティがある場合、ノードはコミュニティに属します.モジュール性が最も高くなるまで繰り返します.

フェーズ2:フェーズ1で作成したコミュニティを使用して新しいコミュニティを作成します.既存のコミュニティ間で接続されているリンクウェイトは、新しいコミュニティ内のノード間のリンクがself-loopで置き換えられるリンクに結合されます.

Pass(Phase 1+Phase 2)をモジュール化が増加しなくなるまで繰り返します.

2. Label Propagation Algorithm(LPA)

LPAは,ネットワーク構造のみを用いてコミュニティを検索する高速アルゴリズムである.私の所属するコミュニティは直感的な観点から、つまり私の周りの人が所属するコミュニティの確率が高いということです.
各ノードにはそれぞれ一意のlabelがあります.ノード順序のランダムなリストを作成し、ノードのlabelをノードの周囲のノードが持つlabelの中で最も頻度の高いlabelに変更します.すべてのノードが最高周波数のlabelになるまで繰り返します.

🙉 Practice in Neo4j!

2-1)データの作成

CREATE
  (alice:User {name: 'Alice', seed_label: 52}),
  (bridget:User {name: 'Bridget', seed_label: 21}),
  (charles:User {name: 'Charles', seed_label: 43}),
  (doug:User {name: 'Doug', seed_label: 21}),
  (mark:User {name: 'Mark', seed_label: 19}),
  (michael:User {name: 'Michael', seed_label: 52}),

  (alice)-[:FOLLOW {weight: 1}]->(bridget),
  (alice)-[:FOLLOW {weight: 10}]->(charles),
  (mark)-[:FOLLOW {weight: 1}]->(doug),
  (bridget)-[:FOLLOW {weight: 1}]->(michael),
  (doug)-[:FOLLOW {weight: 1}]->(mark),
  (michael)-[:FOLLOW {weight: 1}]->(alice),
  (alice)-[:FOLLOW {weight: 1}]->(michael),
  (bridget)-[:FOLLOW {weight: 1}]->(alice),
  (michael)-[:FOLLOW {weight: 1}]->(bridget),
  (charles)-[:FOLLOW {weight: 1}]->(doug)

2-2)Louvain結果

CALL gds.louvain.stream({nodeProjection:'User', relationshipProjection:'FOLLOW'})
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

2-3)LPA結果

CALL gds.labelPropagation.stream({nodeProjection:'User', relationshipProjection:'FOLLOW'})
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name