スペクトラルクラスタリングを用いたコミュニティ検出

Morimoto Osamu

Published in

DeNAデータ分析ブログ

8 min readJan 9, 2024

この記事ではネットワーク分析におけるコミュニティ検出手法の一つであるスペクトラルクラスタリングについて解説します。

R言語による実行コードも掲載しています。

現実のネットワークは全体が均一の構造をしているのではなく、ある程度の偏りを持つ場合があります。ネットワーク分析ではこの偏った密な部分、ノード同士が他のグループに属するノードよりも高い確率で結合している部分をコミュニティと呼びます。

このコミュニティをネットワークのデータから見つけ出す手法をコミュニティ検出と呼びます。これは通常のテーブルデータの分析におけるクラスター分析に相当する考え方です。

全体のネットワークからコミュニティを抽出することは、ネットワークの大きな構造の把握や、各ノードの性質の違いを理解するうえで役に立ちます。

スペクトラルクラスタリング

スペクトラルクラスタリングはネットワークをラプラシアン行列と呼ばれる行列表現に落とし込み、これを固有値分解してクラスタリングする手法です。これによってノード間の連結性に注目したグループ分けが行えます。

まず、テーブルデータを使ってスペクトラルクラスタリングの特徴を確認します。

下図のような渦巻き状の分布を持つ2次元データを考えます。

このデータに対して一般的なクラスタリング手法であるK-Means法を適用すると左図のようにつながりを考慮しないグループ分けがされます。これに対してスペクトラルクラスタリングでは右図のように各点のつながりを考慮したグループ分けがなされます。

library(conflicted)
library(tidyverse)
library(kernlab)

data(spirals)

sp_df <- spirals |>
  as.data.frame()

sp_df |>
  ggplot(aes(x = V1, y = V2)) +
  geom_point() +
  labs(title = "spirals")

res_kmeans <- kmeans(spirals, 2)

res_spec <- specc(spirals, 2)

spec_clust <- bind_rows(
  sp_df |>
    mutate(
      type = "K-Means Clustering",
      clust = res_kmeans$cluster |> as.factor()
    ),
  sp_df |>
    mutate(
      type = "Spectral Clustering",
      clust = res_spec |> as.factor()
    )
)

spec_clust |>
  ggplot(aes(x = V1, y = V2, color = clust)) +
  geom_point() +
  facet_wrap(vars(type)) +
  theme(legend.position = "none")

ネットワークのコミュニティ検出にスペクトラルクラスタリングを適用する手順を見てゆきます。ここでは以下のようなシンプルなネットワークで試してみましょう。

1)まずこのネットワークを隣接行列で表現します。隣接行列は行と列にそれぞれのノードを置き、ノードがつながっている場合は1を、つながっていない場合は0で表現したものです。このネットワークの隣接行列は以下のようになります。

2)次にこの隣接行列の符号をマイナスにして、対角成分に各ノードの次数を格納します。これをラプラシアン行列と呼びます。これがテーブルデータのクラスター分析における距離行列に相当します。

3)このラプラシアン行列を固有値分解し、その固有ベクトルをK-Means法などでグループ化します。

4)結果として数の色分けのようにグループ化されました。

library(igraph)

g3 <- g2 <- g1 <- make_full_graph(4) |>
  delete_edges(c("1|2", "3|4","1|4"))

g <- g1 %du% g2 %du% g3 |>
  add_edges(c(04, 05, 05,09, 09,04))
plot(g)

# スペクトラルクラスタリングの実行
res_sc <- g |>
  cluster_leading_eigen()

# 結果をノードの色に反映
res_sc <- g |>
  set_vertex_attr("color", value = res_sc$membership)

# 結果のネットワーク図
set.seed(1)
res_sc |>
  plot(layout = layout_with_fr)

有名な空手クラブのデータでも試してみましょう。

スペクトラルクラスタリングの結果がこちらです。

library(igraph)

karate <- make_graph("Zachary")

# 元データのネットワーク図
set.seed(1)
karate |>
  plot(layout = layout_with_fr)

# スペクトラルクラスタリングの実行
res_sc <- karate |>
  cluster_leading_eigen()

# 結果をノードの色に反映
karate_sc <- karate |>
  set_vertex_attr("color", value = res_sc$membership)

# 結果のネットワーク図
set.seed(1)
karate_sc |>
  plot(layout = layout_with_fr)