Rでラプラシアン行列

 

最近複雑ネットワーク科学について勉強していて、その過程でRを用いて解析の練習などをしています。
スペクトルグラフ理論の章で登場したラプラシアン行列を求めるプログラムをRで書いてみました。
まあ定義をそのまま書き写したようなものなんですけどね 汗

まず、簡単にラプラシアン行列の説明です。
グラフ\(G\)の隣接行列を\(A\)として、
\begin{align}
A=(a_{ij})
\end{align}
とします。\(A\)のラプラシアン行列を\(L\)とすると、その\((i,j)\)成分\(l_{ij}\)は、
\begin{align}
l_{ij}=k_i \delta _{ij} - a_{ij}
\end{align}
で定められます。ここで\(k_{ij}\)はノード\(i\)の次数、\(\delta _{ij}\)はクロネッカーのデルタ、\(a_{ij}\)は隣接行列\(A\)の\((i,j)\)成分です。

ノード\(i\)の次数\(k_{i}\)は隣接行列\(A\)を用いて、
\begin{align}
k_{i} = \sum_{m=1}^{N} a_{im}
\end{align}
と書けるので
\begin{align}
l_{ij}=\delta _{ij} \sum_{m=1}^N a_{im} - a_{ij}
\end{align}
と表すこともできます。

以下が今回書いてみたRのコードです。

#隣接行列からラプラシアン行列を求めるプログラム
#まず隣接行列を定義
A <- matrix(c(
0,1,1,1,0,0,0,0,0,0,
1,0,1,0,0,0,0,0,0,0,
1,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,1,0,0,0,
0,0,0,0,1,0,1,0,0,0,
0,0,0,0,1,1,0,0,0,0,
0,0,0,0,0,0,0,0,1,0,
0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,0,0,0,0,0),
nrow = 10, ncol = 10, byrow = TRUE)

L <- matrix(1:100, nrow = 10, ncol = 10)
#Lのハコ用意完了

#次数k_iについて先に定義しておく
k <- numeric(10)
for (i in 1:10){
         k[i] <- sum(A[i,])
    }
#ベクトルkの第i成分がi番目のノードの次数
#クロネッカーのデルタは単位行列で用意すればOK
E <- diag(10)

for(i in 1:10){
      for(j in 1:10){
        L[i,j] <- k[i]*E[i,j] - A[i,j]
       }
    }  

クロネッカーのデルタの表現については単位行列を利用しました(個人的には割と気に入ってる発想です 笑)。
 

  • このエントリーをはてなブックマークに追加
  • Pocket

コメントを残す