GRAph ALigner Algorithm (GRAAL) (wiki)という、ネットワーク同士の相同性(align)を計算してくれるアルゴリズムがある。
# graph 1 edgelist 1 3 1 4 1 6 4 6 5 6
# graph 2 edgelist 1 3 1 4 1 6 2 3 2 4 4 6 5 3
これらを gw format に変換する。
# ターミナルで ./list2leda edgelist.txt >> graph.gw
GRAALを行う。スクリプトの実行権限をプロパティで設定しておかないと動かないところにはまった。
# ターミナルで # alpha は 0.8 推奨。ネットワーク1, ネットワーク2, 出力ファイル名 ./GRAALRunner.py 0.8 graph1.gw graph2.gw result
出力ファイルは
aln: graph1 と graph2 のノードの対応ファイル。
1 1 3 3 4 6 6 4 5 2
ealn: graph1 と graph2 のエッジの対応ファイル。行の中の前2つがgraoh1, 後ろ2つがgraph2のエッジ。
3 1 3 1 4 1 6 1 6 1 4 1 6 4 6 4 5 6 2 4
nealn: たぶんノードとエッジの対応。よくわからん。
3 3 1 1 4 6 6 4 5 2
result.results: 乱数の種と統計量の結果。EC が 100% なので graph1 は graph2 の完全なる一部分となる。
Alpha used: 0.8 Seed used for random number generator: 1384540927 Graph1 has: 5 nodes. Graph2 has: 6 nodes. Graph1 has: 5 edges. Graph2 has: 7 edges. Node Correctness is: 2; which is 40% of nodes Edge Correctness is: 5; which is 100% of edges Interaction Correctness is: 1; which is 20% of edges
対応するノードのレイアウト、エッジの色を同じにしている。
対応しなかったエッジは点線。
# 計算結果を R で描出 n1 <- graph.data.frame(read.delim("graph1.txt", header=FALSE), directed=FALSE) n2 <- graph.data.frame(read.delim("graph1.txt", header=FALSE), directed=FALSE) # 対応するノード aln <- read.table("result.aln", header=FALSE) node <- as.numeric(get.data.frame(n2, "vertices")$name) idx <- match(aln$V2[match(node, aln$V1)], node) # 対応するエッジ ealn <- read.table("result.ealn", header=FALSE) e1 <- get.data.frame(n1) e2 <- get.data.frame(n2) idx1 <- mapply(function(x) which(apply(e1[,1:2], 1, setequal, ealn[x, 1:2])), seq(nrow(ealn))) idx2 <- mapply(function(x) which(apply(e2[,1:2], 1, setequal, ealn[x, 3:4])), seq(nrow(ealn))) cols <- rainbow(length(idx2)) nonedgecolor <- grey(0.7) E(n1)$lty <- 2 E(n1)$lty[idx1] <- 1 E(n1)$color <- nonedgecolor E(n1)$color[idx1] <- cols E(n1)$width <- 3 E(n2)$lty <- 3 # 対応しないエッジは点線 E(n2)$lty[idx2] <- 1 E(n2)$color <- nonedgecolor E(n2)$color[idx2] <- cols E(n2)$width <- 3 par(mfrow=c(1, 2), mar=c(0,0,0,0)) lay <- layout.auto(n2) plot(n1, layout=na.omit(lay[idx,])) plot(n2, layout=lay)
ネットワークを変更してこんなのにすると変わる。
1 2 1 3 1 4 1 6 2 4 4 6 5 6
Alpha used: 0.8 Seed used for random number generator: 1384420981 Graph1 has: 6 nodes. Graph2 has: 6 nodes. Graph1 has: 7 edges. Graph2 has: 7 edges. Node Correctness is: 0; which is 0% of nodes Edge Correctness is: 4; which is 57.1429% of edges Interaction Correctness is: 0; which is 0% of edges
