でたぁっ 感動と失敗の備忘録

データ解析を担当することになったサラリーマンの備忘録

マルコフ連鎖とPageRank (追加メモ)

 先日【Rメモ】マルコフ連鎖とPageRankといったメモを書いた。マルコフ連鎖の収束値とPageRankの値が一致するといった点についてふれたが、一致するのはdanmping=1の場合。danmping factorの違いによるPageRankの値を確認したのでちょっとだけ追加メモ。

 wikiのページランンクを見ると、作為的にページランクを上げようとする者に対しては、より小さい値に設定される。といった記述があるが、定義式を見るとdanmping factorが何をしているかすぐに分かる。定義式はwiki(English)が解りやすい。

f:id:deta:20130531052445p:plain

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) # 描画

f:id:deta:20130531054135p:plain
 棒グラフ右はdamping=1なのでマルコフ連鎖の収束値、左の棒グラフはdamping=0なので各系列が均等になっている様子、そしてdampingの違いによるPageRankの変化を確認できました。


参考
Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)
Google の秘密 - PageRank 徹底解説