1998年に、Wattsとその指導教員のStrogatzは本格的な複雑ネットワーク研究の幕開けとなる論文を発表しました。

彼らのモデルは、平均次数を大きくしすぎずに、小さい平均距離(L)と大きいクラスター係数(C)を同時に達成するネットワーク、すなわち、スモールワールド・ネットワークとなるものです。

WSモデルの作り方

(1)平均頂点Nと平均次数<k>を定める。<k>は偶数とする。

(2)拡張サイクルを作る。すなわち、頂点N個を輪状に置き、拡張点を輪の右隣<k>/2個までの頂点と隣接させる。拡張点の次数は<k>となる。

(3)枝は合計<k>N/2ある。そのうち、割合p(0=<p=<1)だけの枝、つまりp<k>N/2本を選ぶ。各枝は等確率で選ばれるとする。

(4)選んだ枝のそれぞれについて、片方の端点とはつないだままにして、もう片方の端点から切り離す。どちらの端点を切り離すかは半々の確率で決める。

(5)宙に浮いた各枝の新しい端点をネットワーク全体の中から等確率に1つ選び、枝を作る。この操作をつなぎかえ、新しい枝を近道またはショートカットと呼ぶ。新しい端点を選ぶときには、

(ⅰ)ループと多重辺を避け

(ⅱ)元の拡張サイクルの枝を復元してしまうような頂点をさける

こと。

####### RでWSモデルのシュミレーション############

####レギュラーグラフ(拡張サイクル)の作成関数の定義#####

regular.g <- function(n, k){

reg <- matrix(0, n, n)

for(i in 1 : n){

for(j in 1 : k){

if(i + j <=n)

reg[i, i+j] <- 1

else

reg[i, i+j-n] <- 1

}

}

(reg <- symmetrize(reg))

}

#######################################

#regular.g関数のテスト

test.g <- regular.g(20,4)

#グラフの描写

library(sna)

png("regular.png")

gplot(test.g, gmode="graph", mode="circle", main="Regular graph (n=20, k=4)")

dev.off()

#pを変化させて辺の架け替えを行う

g <- regular.g(20,4)

#p = 0

rew.g1 <- rewire.ws(g, 0)

#p = 0.2

rew.g2 <- rewire.ws(g1, 0.2)

#p = 1.0

rew.g3 <- rewire.ws(g1, 1.0)

#図示

png("ws1.png")

gplot(rew.g1, gmode="graph", mode="circle", main="p = 0")

dev.off()

png("ws2.png")

gplot(rew.g2, gmode="graph", mode="circle", main="p = 0.2")

dev.off()

png("ws3.png")

gplot(rew.g3, gmode="graph", mode="circle", main="p = 1.0")

dev.off()

pが小さいうちはレギュラーグラフに類似した構造で、p値を大きくするとランダムグラフに近づくことが定性的に理解することができます。

それでは、クラスター係数、平均距離、そして次数分布はpの値の変化に伴ってどのように変化しているのでしょうか。以下では、これらの値を計算し、可視化を行います。

【参考文献】

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

増田直紀　今野紀雄『複雑ネットワーク』2010 近代科学社  83-86pp