ルーヴァン法

コミュニティ検出のためのルーヴァン法は、ルーヴァン大学のBlondel ら^[1]（この方法の名前の由来） によって作成された大規模ネットワークから重複しないコミュニティを抽出することを目的とした貪欲最適化法である。

コミュニティ検出のこの方法の着想は、アルゴリズムの進行に合わせてモジュール性を最適化することです。モジュール性は、コミュニティ外部のエッジに対するコミュニティ内部のエッジの相対密度を測定する、-1 (非モジュール クラスタリング) から 1 (完全モジュール クラスタリング) の間のスケール値です。この値を最適化すると、理論的には、特定のネットワークのノードを可能な限り最適にグループ化できます。ただし、ノードをグループにまとめるすべての可能な反復を実行するのは非現実的であるため、ヒューリスティック アルゴリズムが使用されます。

コミュニティ検出のルーヴァン法では、まずすべてのノードでモジュール性を局所的に最適化することで小さなコミュニティを見つけ、次に各小さなコミュニティを 1 つのノードにグループ化して最初のステップを繰り返します。この方法は、合併によってモジュール性が最大限に増加するコミュニティを接続する、クラウセット、ニューマン、ムーアによる以前の方法^[2]に似ています。ルーヴァン アルゴリズムは、特に確率的ブロック モデルで、コミュニティ構造が存在する場合に正しく識別できることが示されました。^[3]

最適化される値はモジュール性であり、コミュニティ間のリンクと比較したコミュニティ内のリンクの密度を測定する範囲の値として定義されます。 ^[1]重み付きグラフの場合、モジュール性は次のように定義されます。 ${\displaystyle [-1,1]}$

$${\displaystyle Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),}$$

どこ：

• ${\displaystyle A_{ij}}$ノードiとj間のエッジの重みを表します。隣接行列を参照してください。
• ⁠ ⁠${\displaystyle k_{i}}$と⁠ ⁠ は、それぞれノード${\displaystyle k_{j}}$iとjに接続されたエッジの重みの合計です。
• m はグラフ内のすべてのエッジの重みの合計です。
• N はグラフ内のノードの総数です。
• ⁠ ⁠${\displaystyle c_{i}}$および⁠ ⁠ はノード${\displaystyle c_{j}}$iとj が属するコミュニティであり、
• ${\displaystyle \delta }$クロネッカーのデルタ関数は次のようになります。

$${\displaystyle {\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same cluster}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}}$$

上記の式に基づいて、コミュニティcのモジュール性は次のように計算できる。^[4]

$${\displaystyle {\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}}$$

どこ

• ${\displaystyle \Sigma _{in}}$コミュニティc内のノード間のエッジ重みの合計（各エッジは2回考慮されます）であり、
• ${\displaystyle \Sigma _{tot}}$コミュニティ内のノードのすべてのエッジの重みの合計です (他のコミュニティにリンクするエッジを含む)。

異なるコミュニティのノードはモジュール性Qに寄与しないため、次のように記述できます。

$${\displaystyle Q=\sum _{c}Q_{c}}$$

ルーヴァン法は、2つの段階を繰り返すことによって機能します。^[1] 段階 1 では、ノードがコミュニティを移動したときにグラフのモジュール性がどのように変化するかに基づいて、ノードがコミュニティに分類されます。段階 2 では、コミュニティが個々のノードとして表示されるようにグラフが再解釈されます。詳細な説明は以下にあります。

ルーヴァン法は、グラフ内の各ノードv を独自のコミュニティと見なすことから始まります。これは図 1 に示されており、各ドット (ノードを表す) は固有の色 (ノードが属するコミュニティを表す) になっています。

各ノードvについて、 v を現在のコミュニティCから隣接するコミュニティC'に移動すると、グラフ パーティションのモジュール性にどのような影響が及ぶかを検討します。以下の疑似コードでは、これは for ループで行われます。モジュール性の変化が最も大きいコミュニティC' を選択し、変化が正であればv をC'に移動します。それ以外の場合は、そのままにします。これは、モジュール性の改善が止まるまで続きます。

関数moveNodes(グラフG、パーティションP):
    する 
        古いモジュール性 <- 現在のパーティションのモジュール性
        V(G)のvに対して、
            # v をそのコミュニティに移動したときにモジュール性の最大の増加を引き起こすコミュニティを見つける
            C' <- argmax(delta_Q) # delta_Qはモジュール性の変化です
            delta_Q > 0の場合、
                vをC'に移動する
            終了の場合 
        終了
    現在のパーティションのモジュール性を更新
    現在のパーティションのモジュール性 > 古いモジュール性
    Pを返す 
終了関数

^[5]

このプロセスは、モジュール性の増加がなくなるまで、すべてのノードに繰り返して順番に適用されます。モジュール性のこの局所的最大値に達すると、最初のフェーズは終了します。図 2 は、フェーズ 1 を 1 回繰り返した後の図 1 のグラフの様子を示しています。

グラフのパーティション内の各コミュニティでは、そのコミュニティを構成する個々のノードが結合され、コミュニティ自体がノードになります。個別のコミュニティを接続するエッジは、集約ノードを接続する新しいエッジに重み付けするために使用されます。

このプロセスは擬似コードでモデル化されており、関数aggregateGraphは、頂点が古いグラフのパーティションであり、エッジが古いグラフを使用して計算された新しいグラフを返します。この関数では、重み付けされているエッジは表示されませんが、簡単な変更を加えることで、その情報を追跡できるようになります。

関数aggregateGraph(グラフG、パーティションP):
    V <- P 
    E <- [(A,B) | (x,y) は E(G) に含まれ、x は A に含まれ、A は P に含まれ、y は B に含まれ、B は P に含まれます]
    Graph(V,E)を返す
終了関数

^[5]

図 3 は、図 2 のグラフを集約するとどうなるかを示しています。このグラフは、各ノードが 1 つのコミュニティに割り当てられるという点で、図 1 のグラフに似ています。ここから、このプロセスを繰り返して、最適なレベルのモジュール化に達するまで、より多くのノードを既存のコミュニティに移動することができます。

以下の疑似コードは、前の 2 つの関数が連携してプロセスを完了する方法を示しています。

関数 louvain(グラフ G、パーティション P):
    する
        P <- ノードを移動します(G, P)
        done <- length(P) == length(V(G)) # moveNodes を実行しているにもかかわらず、すべてのコミュニティは単一のノードです
        完了していない場合：
            G <- 集約グラフ(G, P)
            P <- シングルトンパーティション(G)
        終了の場合
    完了していない
終了関数

関数singletonPartition(グラフG):
    return [{v} | v is in V(G)] # 各ノードは独自のコミュニティに配置されます
終了関数

^[5]

一般的に、ルーヴァン法は の時間計算量を持つと想定されています。^{[6] [7]} ルーヴァン法を最初に発表した論文の共著者であるリチャード・ブロンデルは、この考えを支持しているようですが、^[8]他の情報源は、時間計算量は「グラフ内のリンクの数に本質的に線形である」と主張しています。 ^[9]つまり、時間計算量は になります。ここで、m はグラフ内のエッジの数です。残念ながら、ルーヴァン法の時間計算量の分析を発表した情報源はないため、ここで分析を試みます。 ${\displaystyle O(n\log {}n)}$${\displaystyle O(m)}$

上記の疑似コードでは、関数louvain がアルゴリズムの実行を制御します。louvain内では、ノードをコミュニティに結合できなくなるまで、moveNodesが繰り返されることがはっきりとわかります。 これは、グラフのモジュール性がどれだけ向上するか、そして最悪の場合、 louvainの反復ごとにモジュール性が向上できるかどうかという 2 つの要因に依存します。これは、 aggregateGraph がグラフを単一のノードに どれだけ速く縮小するかに依存します。

louvainの各反復で、moveNodes がコミュニティに 1 つのノードしか移動できない場合、 aggregateGraph はグラフのサイズを 1 つだけ縮小できます。これにより、louvain はv回繰り返されます。moveNodes はグラフ内のすべてのノードを反復するため、時間の計算量は になります( nはノードの数)。 ${\displaystyle {\mathcal {O}}(n^{2})}$

この状況が可能かどうかは不明であるため、上記の結果は緩い境界と見なす必要があります。Blondel らは、最初の論文で、実行時間の大部分はアルゴリズムの初期の反復で費やされると述べています。これは、「コミュニティの数は、わずか数回のパスで大幅に減少する」ためです。^{[1]これは、} moveNodesが各ノードを移動して、すべてのコミュニティに 2 つのノードがある シナリオを考えると理解できます。この場合、aggregateGraph は元のグラフの半分のサイズのグラフを返します。これが続くと、Louvain メソッドの実行時間は になりますが、これが最悪のケース、最良のケース、平均的なケース、またはそれらのいずれでもないケースであるかどうかは不明です。さらに、グラフのサイズが各反復で同じ係数で削減される保証はなく、したがって単一の対数関数では時間の複雑さを完全に説明することはできません。 ${\displaystyle n\log _{2}{n}}$

• Twitterソーシャルネットワーク（240万ノード、3800万リンク）Josep Pujol、Vijay Erramilli、Pablo Rodriguez著：^[10]著者らは、オンラインソーシャルネットワークを異なるマシンに分割する問題を研究している。
• モバイルフォンネットワーク（400万ノード、1億リンク）Derek Greene、Donal Doyle、Padraig Cunningham著：^[11]さまざまな動的ソーシャルネットワークの動的コミュニティを識別するためのコミュニティ追跡戦略。
• ネットワークベースの動的モデルにおける種の検出。^[12]

ルーヴァンは重複しないコミュニティのみを生成します。つまり、各ノードは最大で 1 つのコミュニティにしか属することができません。これは、多くの現実世界のアプリケーションでは非常に非現実的です。たとえば、ソーシャル ネットワークでは、ほとんどの人が複数のコミュニティに属しています。家族、友人、同僚、昔の学校の仲間などです。生物学的ネットワークでは、ほとんどの遺伝子またはタンパク質は、複数のパスウェイまたは複合体に属しています。さらに、ルーヴァンは、時々、不適切に接続したコミュニティを生成することが示されており、実質的に (少なくとも重複しない場合は)ライデン アルゴリズムに取って代わられました。

これらの接続不良のコミュニティは、コミュニティ内の 2 つのノード グループ間の「ブリッジ」として機能していたノードが新しいコミュニティに移動され、古いコミュニティが切断されたときに発生します。古いコミュニティ内の残りのノードも再配置される可能性がありますが、「ブリッジ」ノードが削除されたにもかかわらず、コミュニティへの接続が十分に強い場合は、そのまま残ります。この例については、右の図を参照してください。ブリッジ ノード (ノード 0) が削除されたことで、赤いコミュニティが 2 つの独立したサブグループに分割されたことに注目してください。これは最悪のシナリオですが、Louvain アルゴリズムには、弱くしか接続されていないノードを使用してコミュニティが形成されるなど、不規則に接続不良のコミュニティにつながる可能性のある、その他のより微妙な問題があります。

Louvain アルゴリズムのもう 1 つの一般的な問題は、モジュール性の解像度の限界です。つまり、複数の小さなコミュニティが 1 つの大きなコミュニティにグループ化されることです。これにより、小さなコミュニティが非表示になります。この例については、右側の解像度の限界の図を参照してください。緑のコミュニティが青のコミュニティに吸収されてグラフのモジュール性が高まると、それが表していた小さなノード グループが失われることに注意してください。これらのノードを、すでに青のコミュニティにあったノードと区別する方法はもうありません。逆に、すでに青のコミュニティにあったノードは、緑のコミュニティにあったノードと区別できなくなりました。つまり、最初に別々のコミュニティに配置される原因となった違いが隠されているということです。

モジュール性の解決限界と、恣意的に不適切に接続したコミュニティの問題は、アルゴリズムの各反復によってさらに悪化します。最終的に、ルーヴァン アルゴリズムが保証するのは、結果として得られるコミュニティがそれ以上マージされないこと、つまり、それらが適切に分離されていることです。恣意的に不適切に接続したコミュニティとモジュール性の解決限界から生じる問題を回避するには、代わりにライデン アルゴリズムを使用することをお勧めします。このアルゴリズムの改良段階とその他のさまざまな調整によって、これらの問題が修正されています。^[5]

モジュール最適化手法を比較する場合、重要な2つの尺度は速度と結果として得られるモジュール値です。速度が高いほど、他の手法よりも効率的であることを示し、モジュール値が高いほど、コミュニティがより明確に定義されていることを示しているため、望ましいと言えます。比較対象となる手法は、Clauset、Newman、Mooreのアルゴリズム^[2]、 PonsとLatapy ^{[13] 、WakitaとTsurumi [14]}です。

表中の-/-は実行に24時間以上かかった方法を示しています。この表（^{[1] [16]}より）は、Louvain法がモジュール性と時間の両方のカテゴリで多くの同様のモジュール性最適化方法よりも優れていることを示しています。

• ライデンアルゴリズム
• モジュール性（ネットワーク）
• コミュニティ構造
• ネットワーク科学
• K平均法クラスタリング

• 「大規模ネットワークにおけるコミュニティ検出のためのルーヴァン法」 Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html