第３章 次数分布を固定したモデル ぱらぱらめくる『ランダム グラフ ダイナミクス』

• 次数分布
  • Erdos-Renyi ランダムグラフの次数分布はポアッソン分布
    • それをRで試してみる

library(igraph)
Nv <- 10000

E.m <- matrix(0,Nv,Nv)

lambda <- runif(1)*3
p <- lambda/Nv
E.m[which(upper.tri(E.m))] <- sample(c(0,1),length(which(upper.tri(E.m))),replace=TRUE,prob= c(1-p,p))

g <- graph.adjacency(E.m,mode = "undirected")

plot(degree.distribution(g))

• Newman-Strogatz-Watts のランダムグラフ
  • そうでない場合としてべき則のネットワークがある
  • 特定の次数分布を持つようなランダムグラフが作りたい
  • ノード数を与え、各ノードの次数を定め、各ノードから「生えている」(半)エッジをつなぎ合わせる方法がある。多重辺や自己ループができるが、多重辺や自己ループを持たないグラフ(単純グラフ)が生成される確率が0以外の正の値に収束することが知られているので、トライ・アンド・エラーを繰り返すにしても、そのような単純グラフを作ることはできる、という

Nv <- 10000
labmda <- 100
prob <- dexp(0:100,lambda)
prob <- prob/sum(prob)
deg <- sample(0:100,Nv,replace=TRUE,prob=prob)
hist(deg)
n.list <- c()
for(i in 1:Nv){
	n.list <- c(n.list,rep(i,deg[i]))
}

edges <- matrix(n.list[sample(1:length(n.list))],ncol=2)
g <- graph.edgelist(edges)
plot(g)
plot(degree.distribution(g),type="b")

• • このようなグラフについては、いくつかの基本的な特性が証明されているので、このようなグラフでモデル化された現象について、推定が可能となる
    • その例として、Newman-Strogatz-Wattsグラフでモデル化された感染症伝播のパーコレーションモデルがある
  • 冪則にフィットするかの検定(最尤法)。最尤法のほかにKolmogorov–Smirnov estimationもあるそうだ(こちら)

power.law.fit(degree(g)+1)

• • • べき則検定・推定についてはこちらのコメントも参照