【論文メモ】Louvain法 - ガラナが飲みたい

概要
背景知識
課題
Louvain法(提案手法)
- アルゴリズム
- Louvain法の特徴
実験
まとめ

Louvain法について、提案論文（下記リンク）を元に調べてみました。

Louvain法は、ネットワーク内のコミュニティ（密に結合しているノードの集合）を抽出する手法であり、従来の手法に比べ高速で抽出することができます。また、アルゴリズムもとてもシンプルで、プログラムへの実装も容易にできます。

※私はグラフ理論が専門ではないので、間違いがある可能性も多分にあります。参考にして頂く際には、ご注意下さい。

概要

近年、SNSやWebの流行を背景にグラフデータ（ネットワーク）への関心が高まっています。グラフデータの活用方法として、グラフデータからコミュニティ（密に結合しているノードの集合）を抽出するという方法があります。しかし、SNSやWebの発達に伴いグラフデータの規模が年々拡大しており、従来のコミュニティ抽出手法では、常識的な時間で計算が完了できないことが増えています。

本稿では、以下の２点により計算量を抑え、従来の手法に比べ高速にコミュニティ抽出できる手法を提案します。

最適化の計算を局所的に行う
コミュニティごとにノードを集約

様々な規模のグラフデータにおいて、既存手法との比較実験を行いました。その結果、いずれのグラフデータでも、品質が高いコミュニティを高速で抽出することできました。

背景知識

グラフとネットワーク

グラフとは、下画像のようにノード（頂点）とノード同士を繋ぐエッジ（辺）で構成されたものを指します。特に、エッジの結びつき（重み、コスト）が一律ではなく、エッジによって異なるグラフをネットワーク（重み付きグラフ）と呼びます。SNSの場合、ノードがユーザー、エッジがユーザー同士の関係性を表します。

f:id:guarana001:20200810123942p:plain:w450 — グラフ説明

参考URL: グラフ理論 - Wikipedia

コミュニティ

下図のように、密に結合しているノードの集合をコミュニティと呼びます。ただし、コミュニティ同士は疎な結合をしていることが多いです。コミュニティは、ノード同士の関係性を基にノードを分類（クラスタリング）した結果を表します。 SNSの場合、コミュニティに着目することで、密なユーザー同士を抽出することができるようになります。

f:id:guarana001:20200810124135p:plain:w450 — コミュニティの説明

モジュラリティ

モジュラリティは、wikiにおいて以下のように説明されています。

モジュラリティ（英: Modularity）は、コンピューターネットワークや、ソーシャルネットワークなどのネットワークやグラフの解析に用いられる効果関数。ネットワークから、モジュールやコミュニティへの分割の「質」を定量化するものである。

高いモジュラリティを持つような高レベルな分割は、モジュール内部でのノード間の密なネットワークを持つ反面、異なるモジュール間で疎なネットワークを持つ。

モジュラリティ - Wikipedia

つまり、モジュラリティは、抽出されたコミュニティの質を評価する指標です。モジュラリティが高いグラフは、コミュニティ内が密で、コミュニティ同士が疎な関係になります。逆に、モジュラリティが低いグラフは、コミュニティ内が疎で、コミュニティ同士が密な関係になります。

モジュラリティ $Q$ は、以下の式で表されます。

f:id:guarana001:20200810144616p:plain:w300

ただし、数式内で使用される記号は下表の通りです。

記号	意味	数式
$A_{ij}$	ノード $i$ とノード $j$ のエッジの重み	ー
$c_{i}$	ノード $i$ が所属するコミュニティ	ー
$k_{i}$	ノード $i$ に結合しているエッジの重みの合計	$k_i = \sum_j A_{ij}$
$m$	全てのエッジの重みの総合計	$m = \sum_i \sum_j A_{ij}$
$\delta$	クロネッカーのデルタ	(省略)

課題

上記のモジュラリティ $Q$ は、最適化する目的関数として用いられます。しかし、大規模なネットワークを扱う場合、モジュラリティの計算が困難となるので、近似的な計算が必要となります。

既存の近似手法¹には、以下の２つの問題点があります

シミュレーテッドアニーリングと比較して、モジュラリティの値が大幅に低い傾向があります。
生成されたコミュニティは、ノードの大部分を含むスーパーコミュニティになる傾向があります。このスーパーコミュニティの影響により、計算速度が遅くなり、100万以上のノードを持つネットワークには適用できません。

Louvain法(提案手法)

アルゴリズム

Louvain法がコミュニティを抽出する流れは、下図で表されます。
Louvain法のアルゴリズムは、大きく2つのフェイズに分かれます。一つ目のフェイズではモジュラリティの最適化（手順2）を行い、二つ目のフェイズではコミュニティの集約を行います。また、2つのフェイズを合わせて「パス」と呼びます。

f:id:guarana001:20200817121741p:plain:w450 — アルゴリズムの説明(元論文より引用)

手順1) 初期値の設定
各ノードごとに個別のコミュニティを設定します。

手順2) モジュラリティの最適化
ノードをランダムに選択し、《終了条件》を満たすまで以下の手順2-1), 手順2-2)の操作を行います。

《終了条件》全てのノードにおいて、コミュニティを変化によるモジュラリティの変化量が $\Delta Q \leq 0$ を満たす場合。
つまり、モジュラリティが極大値をとり、モジュラリティがこれ以上改善できない時です。
※同じノードであったとしても複数回操作する可能性があります

手順2-1) 選択されたノード $i$ に隣接した全てのコミュニティにおいて、モジュラリティの変化量 $\Delta Q$ を計算する。このモジュラリティの変化量 $\Delta Q$ は、ノード $i$ が元々所属するコミュニティから隣接したコミュニティへ移動することにより生ずるモジュラリティの変化量のことを指します。

ここでは、移動前のコミュニティを $C_1$ 、移動後のコミュニティを $C_2$ とした時、移動に伴うモジュラリティの変化量を次の式で表すことができます。

この時、右辺の第一項を $\Delta Q_r$ 、第二項を $\Delta Q_a$ と置いた場合、 $\Delta Q_a$ を次式のようになります。また、 $\Delta Q_r$ も符号を反転させた同様な式で表すことができます。

f:id:guarana001:20200816170842p:plain:w550

ただし、数式内で使用される記号は下表の通りです。
(コミュニティ $C_2$ にはノード $i$ は含まれません)

記号	意味	数式
$k_{i, in}$	ノード $i$ と結合しているノードのうちコミュニティ $C_2$ に所属するノードとのエッジの重みの合計
$\sum_{in}$	コミュニティ $C_2$ に所属するノード同士のエッジの重みの合計
$\sum_{tot}$	コミュニティ $C_2$ に所属するノードと結合のあるノードとのエッジの重みの合計

手順2-2) 隣接するコミュニティの $\Delta Q$ の最大値を $\Delta Q_{max}$ をおきます。この時、下表のように $\Delta Q$ の最大値によってノード $i$ が所属するコミュニティを変化させます。

ただし、 $C_{max}$ は $\Delta Q$ の最大値をとるコミュニティを指します。

条件	意味	ノード $i$ が所属するコミュニティ
$\Delta Q_{max} > 0$	ノード $i$ を $C_1$ から $C_{max}$ に移動させた方がモジュラリティが増加する	$C_{max}$
$\Delta Q_{max} \leq 0$	ノード $i$ を $C_1$ から移動させない方がモジュラリティが高い	$C_1$

手順3) コミュニティごとの集約
手順3) では、手順2) によって抽出したコミュニティごとに集約し新たなグラフを構築します。このグラフの構築が完了次第、手順2) に戻ります。

具体的なグラフの構築方法は、それぞれのコミュニティのノードを単一のノードに集約します。その際、集約後のノード同士のエッジの重みと集約後のノード内のエッジの重みは次のように定義します。

f:id:guarana001:20200817165358p:plain:w500 — 手順3) の説明

この時、上図のようにコミュニティ $C_A$ と $C_B$ を考えます。また、集約後のノードもそれぞれノードa、ノードbとおきます。

集約後のノード同士のエッジの重み
コミュニティ $C_A$ と $C_B$ のエッジは、集約後のノードa,bのエッジとなり、エッジの重みは次の式で表せます。

f:id:guarana001:20200817164812p:plain:w200

集約後のノード内のエッジの重み
コミュニティ $C_A$ 内のエッジは、集約後のノードaのセルフループ（自己閉路）となり、エッジの重みは次の式で表せます。

f:id:guarana001:20200817165024p:plain:w200

Louvain法の特徴

Louvain法は、以下のような特徴があります。

各手順が直感的で、実装が容易です。
アルゴリズムが非常に高速です。
アルゴリズムを繰り返すことでコミュニティ数が大幅に減少するため、実行時間のほとんどが最初のパス(反復作業)に集中します。
アルゴリズムのマルチレベルの性質のおかげで、モジュラリティの resolution limit problem(分解制限問題?,*1)を回避できるようになります。
アルゴリズムが停止して得られた最終的なコミュニティだけではなく、中間的なコミュニティにも意味がある可能性があります。

*1 resolution limit problem：ネットワークが巨大になることでノード同士が相対的に疎になること(ヌルモデルの仮説を保てない)により、小規模なコミュニティを抽出できない問題。詳細は以下のリンクを参照して下さい。

参考URL: Modularity (networks) - Wikipedia

実験

様々なグラフにおいて、Louvain法を既存手法と比較する実験を行います。今回利用するグラフは、下表の通りです。 (グラフの詳細は、元論文等を確認して下さい。)

名称	説明	ノード	リンク
Karate	小規模なソーシャルネットワーク	34	77
Arxiv	科学論文とそれを引用する論文のネットワーク	9k	24k
Internet	インターネットのサブネットワーク	70k	351k
Web nd.edu	nd.eduドメインのサブネットワーク	325k	1M
Phone	携帯電話の利用客のネットワーク(ウェイトは電話回数)	2.6M	6.3M
Web uk-2005	.ukドメインのサブネットワーク	39M	783M
Web WebBase 2001	Stanford WebBase crawlerによって得られたネットワーク	118M	1B

今回比較する既存手法は、以下の3つ手法です。

Clauset, Newman, and Moore (脚注1参照)
Pons and Latapy ²
Wakita and Tsurumi ³

実験結果は、下表の通りです。
表の2つの数値は、(モジュラリティ)/(実行時間)を表します。ただし、実行時間が24時間を超えた場合、"-"と表記します。

いずれのグラフでも、モジュラリティ・実行時間の両方の観点において、Louvain法が最良な結果を得られました。特に、Web uk-2005、Web WebBase 2001などの巨大なネットワークに対しても適用できるのは、Louvain法の優れている点です。

名称	CNM	PL	WT	Louvain法
Karate	.38/0s	.42/0s	.42/0s	.42/0s
Arxiv	.772/3.6s	.757/3.3s	.761/0.7s	.813/0s
Internet	.692/799s	.729/575s	.667/62s	.781/1s
Web nd.edu	.927/5034s	.895/6666s	.898/248s	.935/3s
Phone	-/-	-/-	.56/464s	.769/134s
Web uk-2005	-/-	-/-	-/-	.979/738s
Web WebBase 2001	-/-	-/-	-/-	.984/152nm

まとめ

本記事では、Louvain法について、提案論文を元に調べました。
Louvain法は、既存手法に比べ、品質が高いコミュニティを高速で抽出することができ、巨大なネットワークに対しても適用可能です。 SNSやWebの発達に伴いグラフデータの規模が年々拡大することが予測できるため、Louvain法への関心がますます高まると思います。