2011-10-16

グラフにおける相関（３）グラフを比べる

グラフ

こちらの続き
グラフにはノードとエッジがある
今、連結されたノードについて考える
エッジは２つのノードの関係を表していると見る
エッジで直接つながっていない２ノードについて、２通りの見方をすることができる
- 直接につながっていない→関係がない
- 直接につながっていないけれども、パスはある→パスが関係を表している
後者で考える
すべてのノードが相互にパスを持っているようなグラフのノードペア間の最短距離の行列(最短距離行列)を考えよう
今、あるノードのセットがあって、そのノードセットに関して２つの全域グラフ(すべてのノードペア間にパスがある)があるときに、その２つのグラフの違いを、そのグラフの最短距離行列を用いて
- $\sum_{i,j}^{N,N} \abs{M_1(i,j)-M_2(i,j)}$ で表すことにする
- ここで、最短距離行列は、有向であることを仮定し(無向であっても、対称行列であると便宜上、仮定し)ておこう
このような統計量を「最短距離行列差総和」とでも呼ぶことにする
「最短距離行列差総和」が統計量として、いい感じ、であるためには、単純な２グラフを比較したときに納得しやすい結果が得られることが最低限、満足されるべき条件である
単純な２つのグラフ、と言えば、どちらも１本鎖なグラフの場合がよいだろう

縦軸と横軸に値が取れる。これが相互に「よく似ている」というのは、グラフ１の値(横軸)とグラフ２の値(縦軸)との線形回帰とか、その上での相関とかの良しあしのことである

N<-100
X1<-sort(runif(N))
X2<-sort(runif(N))
plot(X1,X2,type="l")

では、このような場合に、線形相関の残差の平方和と、先に挙げた「最短距離行列差総和」とが、「まあまあ、いい感じ」になっていたらよいわけで、それを確かめてみる

N<-100
X1<-sort(runif(N))
X2<-sort(runif(N))
plot(X1,X2,type="l")
#X1<-1:N
#X2<-1:N
# 標準化しよう
OriX1<-X1/(max(X1)-min(X1))
OriX2<-X2/(max(X2)-min(X2))
# よく相関した状態から、ある程度崩したデータをNiter回作って
# それぞれの場合の線形回帰の残差平方和と「最短距離行列差総和」とがどういう関係になるかを見る
Niter<-100
# ２種類の統計量の格納庫
S1<-S2<-rep(0,Niter)
# シミュレーション
for(j in 1:Niter){
	X1<-OriX1
	X2<-OriX2
# 入れ替える数を1個のみから、全部までいろいろにする
	n<-sample(1:N,1)
# 入れ替える分の入れ替えパターンを決める
	s<-sample(1:n)
	X2[1:n]<-X2[s]
# 鎖状のグラフの隣接行列(重み付き)を作る
	M1<-M2<-matrix(0,N,N)
	for(i in 1:(N-1)){
		M1[i,i+1]<-abs(X1[i+1]-X1[i])
		M2[i,i+1]<-abs(X2[i+1]-X2[i])
	}
# グラフオブジェクトにする
	g1<-graph.adjacency(M1,weighted=TRUE)
	g2<-graph.adjacency(M2,weighted=TRUE)
# 最短距離行列を作る
	sh.path1<-shortest.paths(g1)
	sh.path2<-shortest.paths(g2)
# 最短距離行列差(の行列)を作る
	diff.path<-sh.path1-sh.path2
# 最短距離行列差総和を計算する
	S1[j]<-sum(abs(diff.path))
	#plot(X1,X2)
# 線形回帰して残差平方和を計算する
	lm.out<-lm(X2~X1)
	S2[j]<-sqrt(sum((X2-lm.out[[5]])^2))
}
# ２統計量を比較する
plot(S1,S2)