お気付きの点がありましたらご指摘いただけますと幸いです。
- グラフをコミュニティに分割する手法に、ルーヴァン法と、それを改良したライデン法がある。
- ルーヴァン法もライデン法もコミュニティ分割のモジュラリティ (や Constant Potts Model のハミルトニアン) を最大化しようとする。モジュラリティは同じコミュニティのノードがつながっていることに報酬、つながっていないことにペナルティを課す指標と解釈することもできる。ただし報酬やペナルティの度合いがノードの次数が大きさ (生えている枝の多さ) に依存する。
- ルーヴァン法はシングルトンパーティションから開始し、ノードをランダムな順序で回っていってモジュラリティが大きくなるのであればノードを別コミュニティに移動していくことを周回し、それが終わったら1コミュニティが1ノードになるようにグラフを集約し、また同じことを繰り返す。
- ライデン法もシングルトンパーティションから開始し、ノードをランダムな順序で回っていってモジュラリティが大きくなるのであればノードを別コミュニティに移動していき (ただし移動したら近隣の別コミュニティのノードを必ず後で回るようにし、必ずすべてのノードを回すようにする)、それが一周したら先にパーティションを「精製」してから1コミュニティが1ノードになるようにグラフを集約し、同じことを繰り返す。
- Louvain method - Wikipedia (2023年12月7日参照).
- [0803.0476] Fast unfolding of communities in large networks (2023年12月7日参照).
- Modularity (networks) - Wikipedia (2023年12月7日参照).
- Community detection for NetworkX’s documentation — Community detection for NetworkX 2 documentation (2023年12月7日参照).
- [1810.08473] From Louvain to Leiden: guaranteeing well-connected communities (2023年12月7日参照).
- Introduction — leidenalg 0.10.2.dev0+g47b490f.d20230720 documentation (2023年12月7日参照).
グラフのコミュニティ分割手法の一つである Louvain 法 [1] は、モジュラリティなる指標を最大化するようにグラフをコミュニティ分割するのですね。それでとても高速であると。ちなみに原論文 [2] の著者陣に Louvain さんという方はいらっしゃらなくて不思議に思ったのですが、著者陣の所属大学がベルギーのフランス語圏のルーヴァン・カトリック大学であることが手法名の由来なのですね。であればカタカナ表記は「ルーヴァン法」とすべきですね。わたしは初見で「ルーヴェン法」だと思いそうよんでしまっていたのですが、ルーヴェン・カトリック大学と表記すると分割元であるオランダ語圏の方の大学を指すようですので。それにしても、オランダ語話者とフランス語話者との対立で大学が分割されるという歴史的経緯があったのですね……グラフだけでなく大学まで分割されていたとは……。
閑話休題、グラフのモジュラリティとは何なのでしょうか。ルーヴァン法が如何に高速であるといっても、モジュラリティがグラフの分割のよさを示す指標として納得できるものでなければ採用するわけにはいきません。モジュラリティの定義は [3] などにありますので、さしあたり適当なグラフの適当な分割を考えて計算してみましょう。例えば下図のようになりますね。
ルーヴァン法の Python パッケージ [4] が出す値と合致するかどうかも確認してみましょう。上図と同じ 0～6 のノードを登録し、上図と同じ個所にエッジを張ると、最適な分割は上図の青とオレンジの分け方になりますね (ノード 0～2 がコミュニティ 0、ノード 3～6 がコミュニティ 1)。この分割のモジュラリティは……上図の値と一致していますね。
import networkx as nx import community G = nx.Graph() G.add_nodes_from([0, 1, 2, 3, 4, 5, 6]) G.add_edges_from([ (0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (4, 5), (5, 6)]) partition = community.best_partition(G) print(partition) modularity = community.modularity(partition, G) print(modularity) print( 6.0 / 18.0 - (7.0 / 18.0) * (7.0 / 18.0) + 10.0 / 18.0 - (11.0 / 18.0) * (11.0 / 18.0) )
{0: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 1}
0.3641975308641975
0.3641975308641974
モジュラリティが一致したのはいいのですが、問題はこれがよい分割の指標かどうかです。モジュラリティは「コミュニティ内部の枝の本数の期待値 (枝が生える元を不変としてつながる先がランダムであった場合の期待値) からの差」といった指標になっていますが、この期待値の計算においては、自分自身への枝も、同じノード間の 2 本以上の枝も許容されるし、枝が枝毛になる (枝を張る先を選択するときに既にそこに枝が張られていることを考慮しないという意味) ことも許容されますよね。これでは基準である期待値がめちゃくちゃなような……ただまあ、[3] には in a large random network, the number of self-loops and multi-edges is vanishingly small. とあるのでそこは置いておきますか……。
しかし、やはり個人的には「期待値」を考えるのはわかりにくいです……つながる先のみがランダムである状態に意味を見出しづらいですし……。コミュニティ分割のよさはもっと素朴に「ノードどうしが同じコミュニティなら枝があってほしい (あったら加点、なかったら減点)」「ノードどうしが違うコミュニティなら枝があってほしくない (あったら減点、なかったら加点)」といったものであってほしいですが、モジュラリティの定義をそれっぽく書き下すと以下でしょうか。ここで、 はノード数、
はエッジ数 (両方向からカウントしたものではなく直感的な本数)、
はノード
につながっているエッジ数 (ノードの次数) です。
- すべてのノード対
について以下を足して
で割ったものがモジュラリティです。
のペナルティです。
の報酬です。
- すべてのノード対
のペナルティです。
の報酬です。
の報酬です。
のペナルティです。
こうしてみると、例えば、もしある SNS 上で友達関係にある人たちをコミュニティ分割したいのだとしたら、 が大きい人はたくさんの友達がいる人なので、そんな友達が多い A さんと友達である B さんを同じコミュニティと判定しても報酬は少なめで、違うコミュニティと判定してもペナルティは控えめになりますね。そんなにたくさん友達がいたらどのコミュニティに所属していても不思議でないという感じでしょうか。逆に、友達が少ない人に対する判定は厳しくなりますね。どうも個々人の友達の人数＝各ノードの次数への依存度が大きい指標である気がしますが……。
def modularity(partition, G): mo = 0.0 m = float(len(G.edges)) for v in G.nodes: for w in G.nodes: if partition[v] == partition[w]: # 同じコミュニティならペナルティか報酬 mo -= G.degree[v] * G.degree[w] / (2.0 * m) if ((v, w) in G.edges) or ((w, v) in G.edges): mo += 1.0 # つながっていたら報酬 return mo / (2.0 * m) def modularity2(partition, G): mo = 0.0 m = float(len(G.edges)) for v in G.nodes: for w in G.nodes: if partition[v] == partition[w]: # 同じコミュニティならペナルティか報酬 mo -= 0.5 * G.degree[v] * G.degree[w] / (2.0 * m) if ((v, w) in G.edges) or ((w, v) in G.edges): mo += 0.5 # つながっていたら報酬 else: # 違うコミュニティでもペナルティか報酬 mo += 0.5 * G.degree[v] * G.degree[w] / (2.0 * m) if ((v, w) in G.edges) or ((w, v) in G.edges): mo -= 0.5 # つながっていたらペナルティ return mo / (2.0 * m) print(modularity(partition, G)) print(modularity2(partition, G))
0.3641975308641976 0.36419753086419754
案の定 [3] をみると、グラフが大きい場合、各コミュニティ内が密にエッジで結束している場合でも、コミュニティどうしが統合されてしまうという問題点が指摘されていますね。これは例えば、ある漫画が好きな人たちの密なコミュニティと、あるゲームが好きな人たちの密なコミュニティが形成されているにもかかわらず、前者に所属する C さんと後者に所属する D さんが友達どうしであり、かつ両者ともに友達が少なめであるせいで両者を同じコミュニティにしないことのペナルティが相対的に大きくなり、コミュニティを統合してしまうといった状況でしょうか。
しかし、ルーヴァン法の記事 [1] をみると、Leiden 法ではこれが解消されているというような記述がありますね。Leiden 法もモジュラリティベースのコミュニティ分割手法らしいですが、Leiden 法は純粋なモジュラリティ最大化をしないのでしょうか？ モジュラリティ最大化の範囲でパーティションがよくなるのでしょうか？ Leiden 法の原論文は [5] ですね。ルーヴァン法と同じ命名則で著者陣の所属が Leiden 大学なんですね。であれば以降ライデン法と表記しましょう。しかし、ルーヴァン法に代わるライデン法がオランダの大学発とは、「From Louvain to Leiden:」といった挑戦的にもみえるタイトルといい、因縁を感じるような……どうか分割するのはグラフだけにして……。
とりあえずライデン法の Python パッケージ [6] を使用してみると、グラフを igraph 形式に変換すればコミュニティ分割してくれますね。簡単な例なので結果も変わりません。
import networkx as nx import igraph as ig import leidenalg as la ig_graph = ig.Graph.TupleList(G.edges(), directed=False) partition = la.find_partition(ig_graph, la.ModularityVertexPartition) print(partition)
Clustering with 7 elements and 2 clusters [0] 3, 4, 5, 6 [1] 0, 1, 2
それで肝心のライデン法がどうよいのかですが……ライデン法の原論文 [5] をみていくとそもそもルーヴァン法の疑似コードもありますね。これをまとめると以下でしょうか。なるほどシンプルですね。
- まず初期状態のパーティションはグラフ内のノード1つ1つを1コミュニティにします (シングルトンパーティション)。
- ノードをランダムな順に回って「ノードを別のコミュニティに移動したらモジュラリティが大きくなるか」を調べ、大きくなるようならパーティションを変更します。モジュラリティが大きくなったら次の周回に進み、大きくならなければ終わります。
- 2. の移動結果に基づき、1コミュニティが1ノードになるようにグラフを集約し、パーティションをシングルトンパーティションにし、2. に戻ります。2. でパーティションの変更が発生していなければこれで終わります。
- まず初期状態のパーティションはグラフ内のノード1つ1つを1コミュニティにします (シングルトンパーティション)。
- ノードをランダムな順にキューに入れてキュー内のノードを回って「ノードを別のコミュニティに移動したらモジュラリティが大きくなるか」を調べ、大きくなるようならパーティションを変更します。ただしこのとき変更が発生したら、その隣接ノードであって異なるコミュニティであるノードをキューに追加して後で必ず回るようにします。キュー内のノードを回り切ったらこの手順を終わります。
- パーティションの「精製 (refinement)」をします。2. の結果のコミュニティをそのまま採用するのではなく、そのコミュニティの中でよくつながりあっているところがコミュニティとして採用されます。なので 2. の結果のコミュニティはここで分割され得ます。
- ここまでの結果に基づき、1コミュニティが1ノードになるようにグラフを集約し、パーティションをシングルトンパーティションにし、2. に戻ります。2. と 3. でパーティションの変更が発生していなければ終わります。
