第５章 スモールワールド ぱらぱらめくる『ランダム グラフ ダイナミクス』

• Watts-Strogatzモデル
• 初期状態として、全ノードが同じ次数の対称なグラフを設定し、そこから、辺の片方の端点を指定の確率でつなぎかえるモデル
  • つなぎかえ確率が0ならば格子
  • つなぎかえ確率が1ならば「ランダム」なグラフだが、このランダムなグラフはErdos-Renyiのランダムグラフとは異なる

# Watts-Strogatz
n<- 100

k <-4
m <- matrix(0,n,n)
v <- rep(0,n)
v[2:(k/2+1)] <- 1

for(i in 1:n){
	if(i > 1){
		m[i,] <- v[c((n-i+2):n,1:(n-i+1))]
	}else{
		m[i,] <- v
	}
}
#m
m <- m + t(m)
#m[lower.tri(m)] <- 0
m.ori <- m
g <- graph.adjacency(m.ori,mode = "undirected")
plot(g,layout=layout.kamada.kawai)

p <- 0.1

# つなぎかえ
for(i in 1:(n-1)){
	for(j in (i+1):n){
		if(m[i,j] == 1){
			r <- runif(1)
			if(r < p){
				m[i,j] <- m[j,i] <- 0
				candidates <- which(m[i,] ==0)
				candidates <- candidates[-which(candidates == i)]
				s <- sample(candidates,1)
				m[i,s] <- m[s,i] <- 1
				
			}
		}
		#print(m)
	}
}

g.2 <- graph.adjacency(m,mode = "undirected")
plot(g.2,layout=layout.kamada.kawai)

degree(g)
degree(g.2)