マルコフ連鎖とPageRank (追加メモ)
先日【Rメモ】マルコフ連鎖とPageRankといったメモを書いた。マルコフ連鎖の収束値とPageRankの値が一致するといった点についてふれたが、一致するのはdanmping=1の場合。danmping factorの違いによるPageRankの値を確認したのでちょっとだけ追加メモ。
wikiのページランンクを見ると、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。といった記述があるが、定義式を見るとdanmping factorが何をしているかすぐに分かる。定義式はwiki(English)が解りやすい。
d=0なら、1/N になるので均等な値になるってことです。Rのigraphパッケージのpage.rank()関数で確認。データは前回と同じこんな遷移確率の行列を準備。
V1 | V2 | V3 | V4 | V5 | V6 | |
---|---|---|---|---|---|---|
V1 | 0.700 | 0.360 | 0.070 | 0.040 | 0.100 | 0.040 |
V2 | 0.100 | 0.240 | 0.090 | 0.080 | 0.050 | 0.010 |
V3 | 0.080 | 0.300 | 0.700 | 0.400 | 0.180 | 0.070 |
V4 | 0.020 | 0.050 | 0.050 | 0.250 | 0.170 | 0.060 |
V5 | 0.030 | 0.030 | 0.020 | 0.130 | 0.270 | 0.130 |
V6 | 0.070 | 0.020 | 0.070 | 0.100 | 0.230 | 0.690 |
1.000 | 1.000 | 1.000 | 1.000 | 1.000 | 1.000 |
※実際にRにくわせるデータには行と列のヘッダー、最終行の1.000は不要です。
library(igraph) library(reshape) library(ggplot2) d1 <- as.matrix(read.table("遷移確率.txt", header=F)) # 遷移確率をmatrix形式で読込む # 遷移確率行列からグラフ形式データを準備 d3 <- d1 # 遷移確率をコピー rownames(d3) <- colnames(d3) # rownamesの設定 d3 <- as.data.frame(t(d3)) # from to 形式にする為の転置 d3 <- cbind(from=rownames(d3), d3) # 行名を列として設ける d3 <- melt(d3, id="from") # from to weight 形式に整形 head(d3) > head(d3) from variable value 1 V1 V1 0.70 2 V2 V1 0.36 3 V3 V1 0.07 4 V4 V1 0.04 5 V5 V1 0.10 6 V6 V1 0.04 g <- graph.data.frame(d3[1:2], directed=T) # graph形式に変換 E(g)$weight <- d3[[3]] # weightは遷移確率 df <- c(0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0) # 計算するdamping factor pr.all <- c() for(i in 1:length(df)){ pr.all <- rbind(pr.all, page.rank(g, directed=T, damping=df[i])$vector) # PageRank計算 } # ここからは描画 pr.all <- melt(data.frame(df=df, pr.all), id="df") # ggplot2用のデータ形式に変換 gg2 <- ggplot(pr.all, aes(x=reorder(df, df), y=value, fill=variable)) # 積上げ棒グラフ reorderで横軸順序を指定 gg2 <- gg2 + geom_bar(colour=I("black"), alpha=0.8, linetype=1, size=0.7) # ちょっとキレイにする plot(gg2) # 描画
棒グラフ右はdamping=1なのでマルコフ連鎖の収束値、左の棒グラフはdamping=0なので各系列が均等になっている様子、そしてdampingの違いによるPageRankの変化を確認できました。
参考
・Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)
・Google の秘密 - PageRank 徹底解説