現実世界に実在する巨大なネットワークを解析するときは、個々の構成要素よりもネットワーク全体としての特徴が注目されます。その特徴とは主として、
- 平均距離
- クラスター係数
- 次数分布
の３つが挙げられまs。
今回はこれらのうち、クラスター係数の計算を行いたいと思います。
クラスター係数とは「中止となる点以外の各頂点間にどの程度つながりがあるかを示す指標」です。
具体的には、ある頂点を選んだときに、その頂点aと隣接する頂点すべてをピックアップします。これら隣接する頂点の間で張ることできるedgeの最大数をNとしたときに、実際に張られているedgeの数をnとします。そして、この頂点aに関するクラスター係数を n/N として定義します。
この計算を対象とするグラフの全vertexに対して行い、それらの平均値をとったものがグラフ全体のクラスター係数となります。
それではRを用いた具体的な計算です。
#igraphのロード
library(igraph)
####隣接行列を作成して、そこからグラフを作る####
A <- matrix(c(
0,1,1,1,1,0,0,0,0,
1,0,1,1,1,1,0,0,0,
1,1,0,1,0,0,1,0,0,
1,1,1,0,0,0,0,1,1,
1,1,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,
0,0,0,1,0,0,0,0,0),
nrow = 9)
#隣接行列よりグラフを作成
g <- graph.adjacency(A)
#グラフを描写
png("graph.png")
plot(g, main = "The graph for cluster coefficient calculation")
dev.off()
#####transitivity()を用いた計算方法#####
#vertexごとのクラスター係数を計算
clust <- transitivity(g, type = "local")
#次数が0や1の頂点はクラスター係数がNaNとなるため0に置換
clust[which(clust == "NaN")] <- 0
#クラスター係数の平均値を求める
mean(clust)
[1] 0.3185185
#####直接計算する方法#####
#vertexごとのクラスター係数を計算する関数を定義
clust.coeff <- function(matrix){
n <- nrow(matrix)
output <- rep(0,n)
for(i in 1 : n){
m <- sum(matrix[i, ])
output[i] <-
sum(t(matrix * matrix[i, ]) * matrix[i, ])/(m * (m - 1))
}
output[which(output == "NaN")] <- 0
output}
#すべてのvertexのクラスター係数の平均をとる
mean(clust.coeff(A))
[1] 0.3185185
【参考文献】
金明哲『Rで学ぶデータサイエンス 8 ネットワーク分析』2009 共立出版 序文、121 - 131pp
