ランダムグラフの性質を調べる



現実世界に実在する巨大なネットワークを解析するときは、個々の構成要素よりもネットワーク全体としての特徴が注目されます。その特徴とは主として、
  1. 平均距離
  2. クラスター係数
  3. 次数分布
の3つが挙げられます。
今回はランダムグラフを生成して、これら3つの性質を調べてみたいと思います。
※snaパッケージを使用します。snaパッケージはネットワークの情報を隣接行列で管理するような仕様となっています.


###snaパッケージを使用します####
#snaのインストール
install.packages("sna")
#ロード
library(sna)

#vertexが100個、p = 0.01のランダムグラフ(無向グラフ)を作成.
rg <- rgraph(100, tprob = 0.05, mode = "graph")

#####グラフの描写####
png("random_graph.png")
gplot(rg, main = "random graph : p = 0.05, vertex = 100", gmode="graph")
dev.off()



#####(1)平均距離を調べる####
distance <- geodist(rg)$gdist
#edgeを持たない頂点は平均距離が無限大になってしまうので、無限大の場合はのぞいて計算します
#対角にある0の値をのぞいて計算します
mean(distance[-c(which(distance == Inf), which(distance == 0))])
[1] 2.888283

#結果の解釈
平均距離が3程度ということは、このグラフから任意の二つの頂点を選択したとき、その二点の距離は平均して3程度であるということです。100個もvertexがあるのにも関わらず、案外小さな距離で任意の二点間を行き来することができます。





#####(2)クラスター係数を調べる####

#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}

#ネットワークのクラスター係数を計算
#各頂点に定義されるクラスター係数の平均値を取ればよい
mean(clust.coeff(rg))
[1] 0.05315657

#結果の解釈
#クラスター係数が0.05ということは、ある頂点に隣接する2つの頂点の間に辺がある確率が5%であるということです。これはグラフ全体で2つの頂点間にedgeのある確率(p = 0.05)と同じです。以上より、このグラフではグラフ内部に密度の高い集団(cluster)が形成されていないと結論づけることができます。






#####(3)次数分布を調べる####
#無向グラフであるため、度数表のカウントが2倍になることを考慮
degree <- degree(rg)/2
#ヒストグラムに描写
png("degree-dsit.png")
hist(degree, xlab = "degree", ylab="Frequency")
abline(h=0)
dev.off()

#結果の解釈
次数が3-5のあたりにピークがあることがわかります。これは明らかにスケールフリーネットワークで登場するベキ乗分布とは異なる性質です。


【まとめ】
一般的にランダムグラフは、頂点間の平均距離が短く、クラスター度が低く、次数分布にピークが見られるという傾向があるとされています。今回のシミュレーションでも同様の性質が確認できました。


【参考文献】
金明哲『Rで学ぶデータサイエンス 8 ネットワーク分析』2009 共立出版 序文、121 - 131pp