Open in app

Sign in

Write

Sign in

アンサンブル・コミュニティー抽出

Osamu MORIMOTO, 森本 修
18 min readSep 25, 2024

--

今回はネットワーク分析におけるコミュニティ抽出手法とその課題、応用についての記事です。

どうも、DeNAでマーケティングリサーチャー／データマイナー／データサイエンティストなどなどをやってる森本と申します。

私の前回の記事ではネットワークの中心性指標について解説しました。

ネットワークの中心性指標

どうも、DeNAでマーケティングリサーチャー／データマイナー／データサイエンティストなどをやってる森本と申します。

medium.com

その中心性指標と並んでネットワーク分析の重要な概念となっているコミュニテイー抽出が今回のテーマです。また、従来のコミュニティー抽出手法をより安定させたアンサンブルコミュニティー抽出についても紹介します。

ネットワーク分析とは

まずはネットワーク分析について復習していきましょう。

ネットワーク分析とは、個々のノードとノードを結ぶエッジから成るネットワーク（グラフとも呼ばれます）を分析し、理解する手法やプロセスのことを指します。

ノードとは、個人、企業、ウェブページなどを指し、エッジとは人間関係、ウェブリンク、通信経路などを指します。

鉄道網であれば各駅がノードになり路線のつながりがエッジになります。

ネットワーク分析はすでに様々な分野で活用されており、以下のような目的で使われています。

  1. ソーシャルネットワークの研究: 友人関係やビジネス上の接点、協力関係などを可視化し、情報や影響の伝播パターンを把握する。
  2. インターネットネットワークの解析: ウェブページ間のリンク構造を理解することで、検索エンジンの最適化や情報拡散のモデル化を行う。
  3. 生物学的ネットワーク: 遺伝子、タンパク質、代謝物の相互作用ネットワークを解析し、生命現象の理解や新薬開発に役立てる。
  4. 経済ネットワーク: 貿易関係や金融システム内の資金流れを理解し、リスク管理や政策提言に対応する。

ネットワーク分析におけるコミュニティーとは

下図のようなネットワークを想定します。

直感的にはこのような3つのグループに分かれると考えられるでしょう。

こうしたグループ間よりもグループ内の方が接続の密度が高いグループを、ネットワーク分析ではコミュニティー、あるいはクラスター、モジュールなどと呼びます。

コミュニティー抽出（あるいはコミュニティー発見、クラスタリング）は教師なし分類問題とみなされます。ネットワーク全体から相対的に関係性が強い部分を抽出しようとするのがコミュニティー抽出の基本的な考え方です。

コミュニティーの構造を把握することは、ネットワーク全体がどのように構成されているか、小さなグループどのように結びついて大きなネットワークを作り上げているかを知る助けになります。企業の人間関係で言えば、部署ごとに小さなグループがあり、それらが階層的につながり合って会社全体のネットワークを構成している、といった具合です。

コミュニティ抽出手法

ネットワーク分析におけるコミュニティー抽出には様々な手法が提案されていますが、よく使われるのはLouvain法とInfomap法です。

Louvain法

Louvain法はモジュラリティー最適化手法の一つです。

モジュラリティー（Q）はコミュニティー分割の質を評価する指標で、すべてのコミュニティー内のエッジ数とランダムネットワークで期待されるコミュニティー内のエッジ数の差分で、高密度のグループをうまく抽出しているかどうかを示す指標です。

ここでeiiは同じコミュニティー内に張られたエッジの比率、aiはコミュニティーiに属するノードに接続するエッジの比率です。

このモジュラリティが最大化されるネットワークの分割を見つければよいのですが、ネットワークの可能な分割の数は膨大であり、計算時間が非常にかかります。これをより高速に処理できるようにしたのがLouvain法です。

Louvain法は無向グラフのための手法であり有向グラフには使えません。

Infomap法

Infomap法はネットワーク上の仮想的なランダムウォーカーの移動パターンに基づいてコミュニティを抽出します。

エッジの向きが考慮されるため有向グラフに使われますが、無向グラフも適用できます。

Louvain法とInfomap法の違い

2つの手法の違いを確認してみましょう。

下図のネットワークにLouvain法とInfomap法を適用してみます。

Infomap法は情報の流れに注目するため、矢印が循環している[A,B,C,D], [E,F,G,H], [I,J,K,L], [M,N,O,P]の組み合わせをコミュニティーとして抽出します。

これに対してLouvain法はグループの密度に注目するので、コミュニテイー内の密度が高くなる[A,B,E,H], [C,D,M,P],[N,O,K,L], [I,J,F,G]の組み合わせをコミュニティーとして抽出します。

このように2つの手法にはそれぞれの特徴があるため、違いをよく理解して使い分ける必要があります。

実践上の課題

これらのコミュニティー抽出手法を実際に利用するにあたって一つの課題があります。

K-means法などのクラスター分析と同様ですが、どちらの手法も乱数に依存するため、実行するたびに異なるコミュニティが抽出されてしまう場合があるのです。

以下は有名な Zachary’s karate club のネットワークでLouvain法を3回実行した例です。

3回の実行で少しずつコミュニティーの形が異なることが分かります。

アンサンブル学習を応用したコミュニティー抽出

この問題に対処するアイディアの一つがアンサンブル学習の応用です。

アンサンブル学習は単純に言うと、複数回の実行結果の多数決でコミュニティーを決める方法です。これによって通常のコミュニティー抽出手法よりも安定したコミュニティー構造を抽出することができます。

Zachary’s karate club のネットワークにアンサンブル学習を応用したLouvain法を適用した結果が下の図です。

同様にアンサンブル学習を応用したInfomap法を適用したのが下の図です。

実際にやっていることは以下の手順です。

  1. コミュニティー抽出をn回実行し、エッジの出現数をカウント。
  2. 各エッジの出現割合を計算。
  3. 出現割合の閾値を定め、エッジを取捨選択する。
  4. 残ったエッジで構築されたネットワークがコミュニティーとして抽出される。

もう少し具体的に説明しましょう。下図のネットワークを想定します。

コミュニティ抽出を4回実行した結果が以下の図だったとします。乱数の違いによりコミュニティー抽出の結果が異なります。

各コミュニティ内に存在するエッジを実行結果毎にまとめて、出現割合を計算します。

閾値を0.99とすると、出現割合の低い「c-d」「e-f」は取り除かれ、残りのエッジで構成されたネットワークがコミュニティーとなります。

注意点として、複数回の実行結果が必要なため処理には時間がかかること。また、閾値が大きいとクラスタ小さく細かくなる傾向があります。目的によって閾値を調整するとよいでしょう。

実装

Pythonの場合、こちらでアンサンブルLouvain法のパッケージが公開されています。

GitHub - boevkoski/ensemble-louvain: Enhanced Louvain for stable results

Enhanced Louvain for stable results. Contribute to boevkoski/ensemble-louvain development by creating an account on…

github.com

R言語では公開されている実装が今のところありません。

そこで、私の方で実装したのアンサンブルLouvain法の実装を掲載します。また、Infomap法に拡張したアンサンブルInfomap法も併せて掲載します。

まず実行例がこちらです。

cluster_ensemble_louvain()が実装されたアンサンブルLouvain法関数です。

入力はigraph形式のネットワーク、出力はコミュニティー番号です。

コミュニティー番号は整数型なので、因子型に変換してから元のネットワークのノードに属性として付値します。

library(conflicted)
library(tidyverse)
library(igraph)
library(furrr)

karate <- make_graph("Zachary")

V(karate)$color <- karate |>
  cluster_ensemble_louvain(matching_threshold = 0.50) |>
  as_factor()

karate |>
  plot()

以下がアンサンブルLouvain法を実行する関数 cluster_ensemble_louvain() の実装です。

事前にdplyr、igraph、furrrの各パッケージがインストールされている必要があります。

##### cluster_ensemble_louvain() #####
# network: igraph形式のグラフデータ。
# weights: エッジの重みを表す数値ベクトル
# partitions: ensembleに使うinfomapの実行回数
# matching_threshold: 2つのノードが同じコミュニティに属するか否かの出現率の閾値
# on_giant_component: TRUEの場合、ネットワーク全体ではなく最大コンポーネントのみを対象とする
# resolution: アルゴリズムが内部で使用するモジュラリティ関数の解像度パラメータを調整するためのものです。値が低いと、クラスターの数は少なく、クラスターのサイズは大きくなります。1に設定すると、モジュラリティの元の定義がそのまま再現されます。
# 
# 出力は各ノードの所属コミュニティ番号

cluster_ensemble_louvain <- function(
    network,
    weights = NULL,
    partitions = 100,
    matching_threshold = 0.99,
    resolution = 1,
    on_giant_component=FALSE
    ) {
  
  require(dplyr)
  require(igraph)
  require(furrr)
  
  # グラフの頂点名称属性が設定されていない場合は追加する
  if (is.null(V(network)$name)) {
    V(network)$name <- as.character(V(network))
  }
  
  # コミュニティ抽出を行い、両ノードが同じコミュニティに属するエッジを返す関数の定義
  run_partitions <- function(network, weights = NULL, resolution = 1) {
    partition <- cluster_louvain(network, weights = weights, resolution = resolution)
    V(network)$cluster <- membership(partition)
    df_graph <- igraph::as_data_frame(network, what = "both")
    df_nodes <- select(df_graph[["vertices"]], name, cluster)
    result <- df_graph[["edges"]] |>
      left_join(df_nodes, by = c("from" = "name")) |>
      rename(from_cluster = cluster) |>
      left_join(df_nodes, by = c("to" = "name")) |>
      rename(to_cluster = cluster) |>
      dplyr::filter(from_cluster == to_cluster) |>
      select(from, to)
    return(result)
  }
  
  # 最大コンポーネントの抽出
  if (on_giant_component) {
    network <- largest_component(network)
  }
  
  # 並列処理の開始
  plan("multicore")
  
  # run_partitions()をpartitions回実行
  matching_scores <- future_map_dfr(
    1:partitions,
    ~run_partitions(network, weights = weights, resolution = resolution),
    .progress = TRUE,
    .options = furrr_options(seed = TRUE)
  )
  
  # 並列処理の停止
  plan("sequential")
  
  # 出現率がmatching_threshold以上のエッジのみ残し、所属コミュニティを決定する
  partition <-  matching_scores |>
    group_by(from, to) |>
    summarise(n = n()/partitions, .groups = 'drop') |>
    dplyr::filter(n >= matching_threshold) |>
    graph_from_data_frame(directed = FALSE, vertices = V(network)$name) |>
    components() |>
    membership() |>
    as.integer()

  # 所属コミュニティ番号のベクトルを返す
  return(partition)
}

アンサンブルInfomap法の実装は以下です。

##### cluster_ensemble_infomap() #####
# network: igraph形式のグラフデータ。有向グラフではエッジの方向が考慮される。
# partitions: ensembleに使うinfomapの実行回数
# matching_threshold: 2つのノードが同じコミュニティに属するか否かの出現率の閾値
# on_giant_component: TRUEの場合、ネットワーク全体ではなく最大コンポーネントのみを対象とする
# e.weights: エッジの重みを表す数値ベクトル
# v.weights: ノードの重みを表す数値ベクトル
# nb.trials: ネットワークを分割する試行回数（1以上の整数）
# modularity: TRUEの場合、抽出されたコミュニティ構造のモジュラリティスコアを計算する
# 
# 出力は各ノードの所属コミュニティ番号

cluster_ensemble_infomap <- function(
    network,
    partitions = 100,
    matching_threshold = 0.99,
    on_giant_component=FALSE,
    e.weights = NULL,
    v.weights = NULL,
    nb.trials = 10,
    modularity = TRUE
    ) {
  
  require(dplyr)
  require(igraph)
  require(furrr)
  
  # グラフの頂点名称属性が設定されていない場合は追加する
  if (is.null(V(network)$name)) {
    V(network)$name <- as.character(V(network))
  }
  
  # コミュニティ抽出を行い、両ノードが同じコミュニティに属するエッジを返す関数の定義
  run_partitions <- function(network, e.weights = e.weights, v.weights = v.weights, nb.trials = nb.trials, modularity = modularity) {
    partition <- cluster_infomap(network, e.weights = e.weights, v.weights = v.weights, nb.trials = nb.trials, modularity = modularity)
    V(network)$cluster <- membership(partition)
    df_graph <- igraph::as_data_frame(network, what = "both")
    df_nodes <- select(df_graph[["vertices"]], name, cluster)
    result <- df_graph[["edges"]] |>
      left_join(df_nodes, by = c("from" = "name")) |>
      rename(from_cluster = cluster) |>
      left_join(df_nodes, by = c("to" = "name")) |>
      rename(to_cluster = cluster) |>
      dplyr::filter(from_cluster == to_cluster) |>
      select(from, to)
    return(result)
  }
  
  # 最大コンポーネントの抽出
  if (on_giant_component) {
    network <- largest_component(network)
  }
  
  # 並列処理の開始
  plan("multicore")
  
  # run_partitions()をpartitions回実行
  matching_scores <- future_map_dfr(
    1:partitions,
    ~run_partitions(network, e.weights = e.weights, v.weights = v.weights, nb.trials = nb.trials, modularity = modularity),
    .progress = TRUE,
    .options = furrr_options(seed = TRUE)
  )
  
  # 並列処理の停止
  plan("sequential")
  
  # 出現率がmatching_threshold以上のエッジのみ残し、所属コミュニティを決定する
  partition <-  matching_scores |>
    group_by(from, to) |>
    summarise(n = n()/partitions, .groups = 'drop') |>
    dplyr::filter(n >= matching_threshold) |>
    graph_from_data_frame(directed = FALSE, vertices = V(network)$name) |>
    components() |>
    membership() |>
    as.integer()
  
  # 所属コミュニティ番号のベクトルを返す
  return(partition)
}

アンサンブル・抽出の課題

アンサンブル・コミュニティー抽出手法では閾値の設定により抽出されるコミュニティーの形が変わります。閾値を高く設定するとコミュニティが細かくなる傾向もあります。そのため、適切な閾値をどう設定するのかが課題になります。

K-means法など従来のクラスター分析におけるクラスタ数の設定ではSilhouette法や疑似F統計量といった指標が提案されていますが、同じようにアンサンブルコ・ミュニティー抽出手法における最適な閾値を探る指標が必要かもしれません。

今回の記事は以上です。

参考文献

鈴木努(2017)『Rで学ぶデータサイエンス8 ネットワーク分析 第2版』共立出版

村田剛志(2019)『Pythonで学ぶネットワーク分析』オーム社

F.メンツァー・S.フォルトゥナート・C.A.デービス著、笹原和俊監訳(2023)『ネットワーク科学入門』丸善出版

A.L.バラバシ著、池田裕一・井上寛康・谷澤俊弘監訳(2019)『ネットワーク科学』共立出版

村上弥夢, 橋本康弘(2022). 「COVID-19ワクチン関連リツイートネットワークにおけるフローを考慮した／考慮しないコミュニティ検出手法の比較」『人工知能学会全国大会論文集』第36回.

Network Analysis
Social Network Analysis
Python
Network Science
R

--

--

Osamu MORIMOTO, 森本 修

Written by Osamu MORIMOTO, 森本 修

1 Follower

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams