# Fast unfolding of communities in large networks > [!abstract] 概要 > 我々は大規模ネットワークのコミュニティ構造を抽出するための単純な手法を提案する。我々の手法はモジュラリティ最適化に基づくヒューリスティック手法である。この手法は計算時間の点で他の既知のコミュニティ検出手法をすべて上回ることが示される。さらに、いわゆるモジュラリティによって測定される、検出されたコミュニティの品質も非常に良い。これはまず、260万顧客からなるベルギーの携帯電話網における言語コミュニティの識別、および1億1800万ノードと10億リンク以上を持つWebグラフの分析によって示される。我々のアルゴリズムの精度は、アドホックなモジュラーネットワークでも検証される。 ## 論文情報 - タイトル: Fast unfolding of communities in large networks - 著者: Vincent D. Blondel(Université catholique de Louvain)、Jean-Loup Guillaume(Université catholique de Louvain / LIP6, Université Pierre et Marie Curie)、Renaud Lambiotte(Université catholique de Louvain / Imperial College London)、Etienne Lefebvre(Université catholique de Louvain) - 媒体: arXiv プレプリント(初版2008-03-04、v2 2008-07-25)、掲載誌 *J. Stat. Mech.* (2008) P10008 - arXiv ID: 0803.0476 - コード配布: http://findcommunities.googlepages.com(本文中の脚注 [20] に記載) ## 概要 大規模ネットワークにおけるコミュニティ検出のためのヒューリスティック手法(通称「Louvain法」)を提案する論文。モジュラリティ最適化を局所的な貪欲法で行うフェーズと、見つかったコミュニティを新たなノードへ凝集するフェーズを交互に繰り返すことで、階層的なコミュニティ構造を線形時間に近い計算量で抽出する。1億ノード超のWebグラフとベルギーの携帯電話網という2種の大規模実データで有効性を検証している。 ## 問題設定 - 入力: 重み付きネットワーク $G=(V,E)$(隣接行列 $A_{ij}$ に重みを持つ)。 - 出力: ネットワークのコミュニティへの分割(パーティション)、および各パスに対応する階層的な分割系列。 - モジュラリティ $Q$ の定義(式1、Newman 2004 [12] に基づく): $Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_i k_j}{2m}\right)\delta(c_i,c_j)$ ここで $A_{ij}$ はノード $i,j$ 間のエッジ重み、$k_i=\sum_j A_{ij}$ はノード $i$ に接続する重みの総和、$c_i$ はノード $i$ が属するコミュニティ、$\delta$ はクロネッカーのデルタ、$m=\frac12\sum_{ij}A_{ij}$。 - 前提: 厳密なモジュラリティ最適化はNP困難(文献[14])であり、大規模ネットワークには近似アルゴリズムが必須。従来最速だったClauset・Newman・Moore(CNM)法[8]は、超巨大コミュニティを生成してしまい100万ノード超のネットワークには適用不能という課題があった。 ## 提案手法 - **アーキテクチャ**: アルゴリズムは2フェーズからなる「パス」を、モジュラリティが増加しなくなるまで反復する。 **Figure 1: アルゴリズムのステップの可視化** ![[_attachments/arxiv-0803.0476/fig01-algorithm-steps.png]] (Figure 1. 各パスは2フェーズから構成される。第1フェーズは局所的な変更のみを許してモジュラリティを最適化する段階、第2フェーズは見つかったコミュニティを凝集して新しいコミュニティのネットワークを構築する段階。モジュラリティの増加が不可能になるまでパスが反復される。) - **フェーズ1(モジュラリティ最適化)**: 最初は各ノードに個別のコミュニティを割り当てる(N ノードなら N コミュニティ)。各ノード $i$ について、隣接ノード $j$ のコミュニティに $i$ を移した場合のモジュラリティ増分 $\Delta Q$ を計算し、増分が最大かつ正となる隣接コミュニティへ $i$ を移動する。正の増分が無ければ $i$ は元のコミュニティに留まる。これを全ノードについて改善が無くなるまで逐次・反復的に適用する。ノードの処理順序が最終モジュラリティに与える影響は小さいが、計算時間には影響しうると報告している。 - **増分計算式(式2)**: 孤立ノード $i$ をコミュニティ $C$ に移すことによるモジュラリティ増分 $\Delta Q$ は $\Delta Q=\left[\frac{\Sigma_{in}+k_{i,in}}{2m}-\left(\frac{\Sigma_{tot}+k_i}{2m}\right)^2\right]-\left[\frac{\Sigma_{in}}{2m}-\left(\frac{\Sigma_{tot}}{2m}\right)^2-\left(\frac{k_i}{2m}\right)^2\right]$ ($\Sigma_{in}$: $C$内部のリンク重みの総和、$\Sigma_{tot}$: $C$に接続するリンク重みの総和、$k_i$: ノード$i$に接続するリンク重みの総和、$k_{i,in}$: ノード$i$から$C$内ノードへのリンク重みの総和)。これにより増分を定数時間近くで評価でき、アルゴリズムの高速性の主因となっている。 - **フェーズ2(コミュニティの凝集)**: フェーズ1で見つかった各コミュニティを1つの新しいノードとする新ネットワークを構築する。2つのコミュニティ間のリンク重みは、元のネットワークでその2コミュニティ間にあったリンク重みの総和とする。同一コミュニティ内のリンクは、その新ノードの自己ループになる。 - **反復と階層構造**: フェーズ2完了後、得られた新しい重み付きネットワークに再びフェーズ1を適用できる。この2フェーズの組を「パス」と呼び、パスを重ねるごとにメタコミュニティ数が減少するため、計算時間の大半は最初のパスに費やされる。パス数は一般に小さく(本論文の例では常に5未満)、各パスの中間分割が階層構造の各レベルに対応する。 **Figure 2: 30個のクリークからなるリングへの適用例** ![[_attachments/arxiv-0803.0476/fig02-ring-of-cliques.png]] (Figure 2. Fortunato & Barthélemy [23] で論じられたリングを構成する30個のクリーク(各5ノード、単一リンクで相互接続)に本手法を適用した例。第1パスはネットワークの自然な分割を見つけ、第2パスはクリークを2個ずつのグループに結合したモジュラリティの大域的最大値を見つける。) ## 新規性 - 従来最速だったCNM法[8]は、コミュニティ併合を繰り返す貪欲法だが、モジュラリティ値がシミュレーテッドアニーリング[15]より有意に低く、また現実的な構造を持たない合成ネットワークでもノードの大部分を含む「超コミュニティ」を生成する傾向があり、計算を大幅に遅くして100万ノード超のネットワークには事実上適用できなかった。Wakita & Tsurumi[16]はコミュニティサイズのバランスを取るトリックでこれを回避し数百万ノード規模まで対応したが、バランス化ヒューリスティックのために低いモジュラリティ値しか得られない場合がある(ベルギー携帯電話網でWTのモジュラリティが低いことを本論文が指摘)。 - 本手法は計算のボトルネックが計算時間ではなく主記憶のストレージ容量になる点が従来法と質的に異なり、1億1800万ノードのネットワークでも152分で処理できる。 - モジュラリティ最適化には既知の「解像度限界問題」(小さいコミュニティを識別できない[23])があるが、本手法は第1フェーズで単一ノードずつの移動しか行わないため、2つの異なるコミュニティが単一ノード移動だけで併合される確率が非常に低く、この問題を本質的に回避しているとしている。 - 従来手法が単一の分割しか出力しないのに対し、本手法は各パスの中間分割を通じて完全な階層的コミュニティ構造を副産物として提供する。 ## 実験設定 - **比較対象**: Clauset・Newman・Moore(CNM)[8]、Pons & Latapy(PL)[7]、Wakita & Tsurumi(WT)[16]。 - **ベンチマークネットワーク**: Karate Club(34ノード/77リンク)[24]、Arxiv論文引用ネットワーク(9千ノード/2.4万リンク)[25]、インターネットのサブネットワーク(7万ノード/35.1万リンク)[26]、nd.eduドメインのWebページネットワーク(32.5万ノード/100万リンク)[27]、ベルギー携帯電話網(260万ノード/630万リンク)、.ukドメインのWebサブネットワーク(3900万ノード/7億8300万リンク)[28]、Stanford WebBaseクローラによるWebグラフ(1億1800万ノード/10億リンク超)[28,29]。 - **評価指標**: モジュラリティ $Q$(式1)と計算時間。アドホックネットワークでは正しく識別されたノードの割合と正規化相互情報量(normalized mutual information)。 - **アドホックネットワーク**: 128ノードを32ノードずつ4コミュニティに分割し、同一コミュニティ内は確率 $p_{in}$、異コミュニティ間は確率 $p_{out}$ でリンクするベンチマーク[30]。 - **実データ**: ベルギーの携帯電話会社の記録から構築した260万顧客のネットワーク[34]。6か月間の通話回数を重みとする。顧客ごとに年齢・性別・言語・郵便番号の属性が付与されている。 ## 実験結果 **Table 1. 数値結果の要約** （Figure/Table キャプション原文: Table 1. Summary of numerical results. This table gives the performances of the algorithm of Clauset, Newman and Moore [8], of Pons and Latapy [7], of Wakita and Tsurumi [16] and of our algorithm for community detection in networks of various sizes. For each method/network, the table displays the modularity that is achieved and the computation time. Empty cells correspond to a computation time over 24 hours.） | | Karate (34/77) | Arxiv (9k/24k) | Internet (70k/351k) | Web nd.edu (325k/1M) | Phone (2.6M/6.3M) | Web uk-2005 (39M/783M) | Web WebBase 2001 (118M/1B) | |---|---|---|---|---|---|---|---| | CNM | .38 / 0s | .772 / 3.6s | .692 / 799s | .927 / 5034s | -/- | -/- | -/- | | PL | .42 / 0s | .757 / 3.3s | .729 / 575s | .895 / 6666s | -/- | -/- | -/- | | WT | .42 / 0s | .761 / 0.7s | .667 / 62s | .898 / 248s | .56 / 464s | -/- | -/- | | 本手法 | .42 / 0s | .813 / 0s | .781 / 1s | .935 / 3s | .769 / 134s | .979 / 738s | .984 / 152分 | (値はモジュラリティ $Q$ / 計算時間。空欄は計算時間が24時間を超えたことを示す。) - 全てのベンチマークで本手法が最速かつ最高または同等のモジュラリティを達成。.uk-2005(3900万ノード)は738秒、WebBase(1億1800万ノード)は152分で計算完了。 - WTがベルギー携帯電話網で低いモジュラリティ(.56)しか得られない点について、著者はWTのヒューリスティックがバランスの取れたコミュニティを作る一方、本手法は不均衡なコミュニティ(実際のデータ構造に近い)を許容するためと考察している。 - アドホックベンチマーク[30](128ノード・4コミュニティ)では、正しく識別されたノードの割合が $z_{out}=8$ で0.67、$z_{out}=7$ で0.92、$z_{out}=6$ で0.98となり、Pons & Latapy[7]やReichardt & Bornholdt[31]と同程度の精度。Duch & Arenas[32]と初期のシミュレーテッドアニーリング法[15]のみが本手法より高精度だが、計算コストのため小規模ネットワークにしか適用できない。 - 別のベンチマーク[33]では、混合パラメータ $k_3$ が35までのマクロコミュニティでほぼ1の正規化相互情報量を達成し、$k_3$ が55前後で0.5まで低下する。 - Karate Clubでは3パスで収束: 第1パスで34ノードが6コミュニティに、第2パスで4コミュニティに、第3パスでは変化なしとなり終了する。 ### ベルギー携帯電話網への適用 **Figure 3: ベルギー携帯電話網から抽出されたコミュニティのネットワーク** ![[_attachments/arxiv-0803.0476/fig03-belgian-phone-network.png]] (Figure 3. 約200万顧客を表すコミュニティネットワークのグラフ表示。ノードサイズは対応するコミュニティの人数に比例し、色は赤緑スケールでコミュニティ内の主要言語を表す(フランス語が赤、オランダ語が緑)。100人超のコミュニティのみプロット。2つの主要言語クラスタの間に混色の中間コミュニティが存在する点に注意。高解像度でズームすると、この中間コミュニティは言語分離があまり明瞭でない複数のサブコミュニティで構成されていることが分かる。) - 260万顧客のネットワークで6階層のコミュニティ階層を検出。最上位層には100人超の顧客からなるコミュニティが261個存在し、これらが全顧客の約75%を占める。 - 261コミュニティの言語分析の結果、ネットワークは強く分節化(segregated)されており、ほとんどのコミュニティがほぼ単一言語である。10000人超のコミュニティは36個あり、2言語クラスタの境界にある1コミュニティを除く全てで、構成員の85%超が同一言語話者である。 **Figure 4: 大規模コミュニティにおける言語比率** ![[_attachments/arxiv-0803.0476/fig04-language-homogeneity.png]] (Figure 4. ベルギー携帯電話網の大規模コミュニティについて、コミュニティサイズと、そのコミュニティの支配的言語を話す顧客の割合をプロット。10000人超のコミュニティのうち1つを除く全てで、支配的言語の話者が85%を超える。) - 英語話者は全コミュニティにほぼ均等に分散する一方、ドイツ語話者の60%超が単一のコミュニティに集中している。これはドイツ語話者がドイツに近い一地域に集中している地理的要因によるものと考察されている。 - フランス語系コミュニティ間のリンク強度は、オランダ語系コミュニティ間のリンク強度より平均54%強く、両言語コミュニティの社会的構造が異なることを示唆している。 ## 考察 - 本手法の律速はストレージ容量であり計算時間ではないという性質の転換により、従来の500万ノード規模から1億ノード超規模へと扱えるネットワークサイズが飛躍的に拡大し、国全体やインターネットの大部分といった複雑系のモジュール構造の解明が現実的になった。 - 本論文では階層構造のうち最上位(最終)パーティションの精度のみを検証しており、中間パーティションの精度は未検証と明記している。中間パーティションが意味を持つ根拠として、(1) 各中間分割はその時点でのエンティティ(ノードまたは凝集済みノード集合)単位の局所最大値である、(2) 最終分割のモジュラリティ値が幅広いシステムサイズで高い、(3) 最終パスで見つかったコミュニティを新ネットワークとして再度アルゴリズムを適用すると類似のサブコミュニティが得られると期待される、という3点を挙げているが、著者ら自身「これらは定性的な議論に過ぎない」と留保している。 - 高速化のさらなる余地として、モジュラリティ増分がある閾値を下回った時点でフェーズ1を打ち切る、次数1のリーフノードを事前に除去し後で戻す、といったヒューリスティックを挙げているが、最終分割への影響は未検証としている。 ## 強み / 弱点・課題 - **強み**: 実装が直感的で容易、教師なし、$\Delta Q$ の定数時間近い評価により事実上線形時間、既存手法を凌駕する速度とモジュラリティを両立、階層構造を副産物として得られる。 - **弱点・限界(論文が明記するもの)**: - 中間(下位)階層の分割精度は本論文では未検証。 - ノード処理順序が計算時間に影響しうるが、順序選択の最適化は未解決の課題として残されている。 - ストレージ容量が実質的な規模の上限を規定する(計算時間ではなく主記憶容量がボトルネック)。 - 提案したさらなる高速化ヒューリスティック(閾値打ち切り、次数1ノードの一時除去)の最終分割への影響は未検証。