遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

グラフの固有値

グラフ 固有値 クラスタリング R 連結 囲碁 Cheeger 
library(igraph)
#　適当にグラフを作る
g <- erdos.renyi.game(10, 3/10)
# 木グラフに興味があるので、木を作る
mst <- minimum.spanning.tree(g)
# 隣接行列
A <- as.matrix(get.adjacency(mst))
# ノードの次数
degs <- degree(mst)
# ノードの次数を対角成分とする行列
D <- diag(degs)
# グラフのラプラシアンは以下のようにして作れる
L <- D - A
# グラフ上の推移確率行列は次のようにして作れる
#P <- A/degs
P <- diag(1/degs) %*% A
# ３つの行列を固有値分解する
A.eigen.out <- eigen(A)
L.eigen.out <- eigen(L)
P.eigen.out <- eigen(P)
# 隣接行列の固有値の最大値は、次数の最大、最小、平均との間で以下のような関係がある
max.deg <- max(degs)
min.deg <- min(degs)
mean.deg <- mean(degs)
lambda.A.max <- max(A.eigen.out$values)
# 以下の不等式が任意のグラフで成り立つ
lambda.A.max >= max(mean.deg,sqrt(max.deg))
lambda.A.max <= max(degs)
# 連結グラフのときは、Aの固有値の最大値は重複がない
length(which(A.eigen.out$values == max(A.eigen.out$values)))

# Lの固有値の最小値は0である
min(L.eigen.out$values)
# 連結グラフのとき、最小固有値は１個だけ
length(which(L.eigen.out$values == min(L.eigen.out$values)))

# Pの固有値の最大値は１
max(P.eigen.out$values)
# 連結グラフのとき、その重複度は１
length(which(P.eigen.out$values == max(P.eigen.out$values)))
  • ２部グラフであることと固有値スペクトルの対称性
  • 最大固有値と第２最大固有値の差は連結性に関する情報を提供する
    • Discrete analogue of Cheeger's inequality in differential geometry...
      • より詳しくはこちらにありそうだ
      • 多様体のCheeger'sに関して言えばこちら
        • 多様体の広がり具合は、「だだっ広く広がっている〜ちょん切りにくい」という風にとらえれば「ちょん切りやすさ(２つにわける)」を評価することで、とらえられる(そのようにしてとらえる側面もある)
        • 多様体上の点に、「ちょん切りやすさ」をあらわす正の実数が定められて、それがCheeger's constantらしい。そして、それは、多様体のその点に定義できるラプラシアンの固有値の最小値との間で不等式の関係を持つことが知られていて、それがCheeger's inequality in differential geometryらしい
        • それをグラフに展開すると、「離散版」だよ、という話らしい
    • 脱線になるけれど、「ちょん切りやすさ」を「囲碁の石の連結の強弱の程度」になぞらえると、囲碁の石具合をグラフに見立てて、そこにグラフのラプラシアンをとって、固有値分解してやって、Cheeger's constant (離散版)の推定値を出したり、信頼区間を出すことが、「石の連結の確実さ」とかになったりするのかもしれない
    • さらに気になる、木グラフとCheeger(こちら)
    • グラフのExpanderという概念と固有値スペクトルの関係
      • Expanderというのは：グラフのノードのうち、たかだか半分までのノードを取り出して、そのノード対その他のノードという対応の図式を考える。そのとき取り出したノードセットから残りのノードセットへのエッジについて考えたときにに、そのようなエッジの本数が一番すくないのは何本かというのを定量化したもの
      • Connectivityのある側面を見ているわけだが、これと固有値スペクトルとの関係は？という話
    • 固有値の重複度や重複固有値の個数は、グラフの対称性と関係する
    • 固有値スペクトルと関連するいろいろ