最近友人に薦められて、今日が最終回らしい「凪のあすから」を見ています。今６話なのですが、恋愛関係が大変複雑です。「深夜の昼ドラ？　アニメ『凪のあすから』の人物相関図つくったよ」というページがあったので、引用しますと、こんな感じ。

うーん、グラフ理論って感じだ。そう思ってからピクシブの非公式カップリングのページを見てしまうと、もはや隣接行列か何かにしか見えなくなってきた…。

隣接行列…グラフ理論…はっ！ページランク求めようページランク！

というわけで、今まで一回ぐらいやってみようと思っていた、ページランクの計算を実際にやってみました。こちらの「Google の秘密 – PageRank 徹底解説」を参考にしました。人間をページに見立てて、好意をリンクに見立てます。

ページランクとは結局何なのか

昔私が読んだ本だと、

全てのページはページランク値PRを持っていて、
他のリンクしているページそれぞれににPR/N（Nはページ内のリンク総数）を与えており、
ページランクの値PRはリンクされた他のページから貰ったページランク値の和に等しい

というのを読んだ気がします。つまり、貰ったページランク＝あげたページランク＝そのページのページランクという等式が成り立つということです。

元の論文にもそんな図が載っています。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, ‘The PageRank Citation Ranking: Bringing Order to the Web’, 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

これをグラフ理論と確率過程の話で表現すると、こうなります。

各ページから他のページへ移動する確率の表を用意する（とりあえずすべてのリンクで等確率＝1/リンク総数とする）
その表に従ってあるページから出発してリンクをたどり続ける
すると、どのページから出発しても、N回リンクをたどった時にあるページPに居る確率がN+1回目のそれと変わらなくなってくる（これを定常状態と呼びます）
その時の、N回目でそれぞれのページに居る確率がページランクです。

これがホントに元の話と一緒なのか？ということなのですが、

“もらうページランク”＝（自分も含めた他のページにN−1回目に居る確率＊それぞれの遷移確率）の和＝N回目にそのページにいる確率
“あげるページランク”＝（N回目にそのページにいる確率 * そのページから他のページへの遷移確率）の和＝N回目にそのページにいる確率1

なので、もらうページランク＝あげるページランクという関係は確かに成り立ちます。

求めてみる

ページ遷移確率表＝行列

実際にもとめてみましょう。まずは、鍵となるページ遷移確率表を用意します。さっきの表を見ながら、ひーくんからまなかへ遷移する確率は１…みたいな感じで行列を作るとこうなります。一応、今回は友情は無視して恋愛関係だけ考えます。

M =
　ひーくん　ちさき　　まなか　　　要　　　　さゆ　　　美海　　　つむぐ　　あかり　　至　　　　みをり　←好き　↓好かれる
   0.00000   1.00000   0.00000   0.00000   0.00000   1.00000   0.10000   0.00000   0.00000   0.00000　ひーくん
   0.00000   0.00000   0.00000   1.00000   0.00000   0.00000   0.10000   0.00000   0.00000   0.00000　ちさき
   1.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.00000   0.00000　まなか
   0.00000   0.00000   0.00000   0.00000   1.00000   0.00000   0.10000   0.00000   0.00000   0.00000　要
   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.00000   0.00000　さゆ
   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.00000   0.00000　美海
   0.00000   0.00000   1.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.00000   0.00000　つむぐ
   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.50000   0.00000　あかり
   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   1.00000   0.00000   1.00000　至
   0.00000   0.00000   0.00000   0.00000   0.00000   0.00000   0.10000   0.00000   0.50000   0.00000　みをり

普通、ページには複数のリンクがありますが、このアニメだと思い人が二人以上居るのは不倫と勘違いされて殴られた至だけです。

あと６話時点ではつむぐは誰も好きではないので、つむぐの行が全部０になるはずなのですが、そうしてしまうとページランクが求まりません2。

これを元論文ではdangling pageと呼んでいます。元論文では「あんまり重要じゃないから削除して計算しています」と無視してしまっているのですが、つむぐくんを無視するのはかわいそう（？）なのと、仮につむぐくんを消してしまうと今度はまなかがdangling pageになって…となって最終的に大人組しか居なくなってしまうので、次に紹介するrandom surferモデルに習って、みんなを平等に好きなことにしました。

計算は掛け算するだけ

元の定義通り、「あるページからスタートしてリンクをたどり続けた時に、それぞれのページに居る確率が一定になってくる」まで遷移させ続けます。

たとえば、ひーくんからはじめましょう。はじめはひーくんに居ると仮定しているので、ひーくんに居る確率は１で、他みんな確率０とします。

１回リンクをたどると、グラフを見るとひーくんはまなかが好きなので、まなかの確率が１になるはず。

これを我々が先ほど作った行列を使って計算しようとするなら、先ほどの行列Mに、ひーくんを１としたベクトルPを掛ければよいです。

octaveでやるとこんな感じです。

octave:95> M=[ 0 1 0 0 0 1 1/10 0 0 0 ; 0 0 0 1 0 0 1/10 0 0 0; 1 0 0 0 0 0 1/10 0 0 0; 0 0 0 0 1 0 1/10 0 0 0 ; 0 0 0 0 0 0 1/10 0 0 0 ; 0 0 0 0 0 0 1/10 0 0 0; 0 0 1 0 0 0 1/10 0 0 0 ; 0 0 0 0 0 0 1/10 0 1/2 0; 0 0 0 0 0 0 1/10 1 0 1; 0 0 0 0 0 0 1/10 0 1/2 0 ]
(略)
octave:96> P = [1; 0; 0; 0; 0; 0; 0; 0; 0; 0]　←ひーくんに居る確率を１としたベクトル
octave:97> M*P
ans =

   0
   0
   1
   0
   0
   0
   0
   0
   0
   0

というわけで、まなかは三番目の要素で、それが１となったので、見事正しい結果を得られています。これを沢山続けてみましょう。10000回ぐらい掛けると変わらなくなってきます。

octave:98> (M^10000)*P
ans =

   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.00000
   0.22222
   0.55556
   0.22222

…あれぇ？最後の３人、つまり大人組以外ゼロ？なんか間違ったかなぁ？

ランダム・サーファー・モデル

こうなってしまった原因は、大人組から子供組へ繋がっていないことです。つむぐくんは全員が好きだと仮定したので、子供組から大人組へはつむぐくんから遷移することが出来るのですが、その後は大人組の間でぐるぐるぐるぐる巡り続けることになります。ひーくんからはじめても長い目で見ればいつかは大人組に入ってしまい、そこで定常状態となるので、子供組の確率がすべて０になってしまったのです。グラフ理論の言葉でいうと、グラフを辿ると元の位置に必ず戻ってこれる大人組のような部分を再帰類と呼び、そうではなく元に戻れない子供組のような部分を非再帰と呼ぶそうですが、あまりこれ自信をもって解説できないので、しません…。

元の論文ではこれをRank sinkと読んでいて、そのためにランダム・サーファー・モデルというのを考慮しています。これはどういうモデルかというと、「時々はまったくリンクされていない別のページに飛ぶ」と考慮しているモデルです。具体的には、新しい遷移確率行列を次のように定義します。

octave:99> M2=(M*1/1.15)+((1/10)*0.15/1.15)

これは、まず今までの確率を少し下げた上で、あるページから他のページへ僅かな確率で飛ぶようにした、ということです。凪のあすからの言葉を使えば、ひょっとするとひーくんは他の女の子（や男の子）にも興味を持つかもしれないよねというモデルです。

この修正したモデルでは、あるページから他のページへ少ない確率ながら必ずジャンプできるので、Rank sinkのような問題は起こりません。

早速、計算してみましょう。

octave:100> (M2^10000)*P
   0.095976　ひーくん
   0.060684　ちさき
   0.106569　まなか
   0.043208　かなめ
   0.023111　さゆ
   0.023111　美海
   0.115780　つむぐ
   0.135981　あかり
   0.259599　至
   0.135981　みをり

やはり両思いは強いのですね！（？）　子供組を見ると、やはり特に重要そうなキャラクターであるひーくん、まなか、つむぐの三人のページランクが高いので、おおよそページランクの妥当性を示せたと言っていいんでしょうか！？とりあえず、この三人に注目して今後は視聴を続けたいと思います！

蛇足：固有値・固有ベクトルを使って求める

なんか10000回も行列を掛け算するのは…という感じしますか？元の論文だとその方法で計算してると書いてあるのですが、これは行列の固有値・固有ベクトルを使っても求めることが出来ます。

固有値・固有ベクトルをおさらいしておくと、

ある行列Mに対する、
固有値μ・固有ベクトルVは、
次のような関係を満たすものです
MV = μV

ここで、固有値μ＝１なら、MV=Vとなって、N回目とN+1回目でのそれぞれのページに居る確率が全く同じという事になり、ちょうど私達が求めたかったベクトルと一致しますね！

octaveで求めるとこんな感じになります。

octave:142> eig(M2)
ans =
   1.00000 + 0.00000i　←求めたい、固有値１の固有ベクトルは１番目だと分かる
   0.78950 + 0.00000i
   0.19713 + 0.55213i
   0.19713 - 0.55213i
  -0.86957 + 0.00000i
  -0.59237 + 0.00000i
  -0.25222 + 0.45314i
  -0.25222 - 0.45314i
   0.00000 + 0.00000i
   0.00000 + 0.00000i

octave:143> [V, D] = eig(M2);　←固有値と固有ベクトルを再度格納
octave:144> V(:,1)　←固有ベクトル１番目を取得する
ans =
   0.252078
   0.159383
   0.279899
   0.113484
   0.060701
   0.060701
   0.304091
   0.357146
   0.681825
   0.357146
↑固有ベクトルは整数倍しても固有ベクトルで、octaveはベクトルの大きさを１に正規化するので、さっきの結果と合わない
octave:146> V(:,1) ./ sum(V(:,1))　←ベクトルの要素の合計が１となるようにすると…
ans =
   0.095976
   0.060684
   0.106569
   0.043208
   0.023111
   0.023111
   0.115780
   0.135981
   0.259599
   0.135981
↑先ほどの結果と一致する！

こんな感じで計算できます。固有値ってこんなのにも使えるんですね〜。ちなみに、この行列の固有値のうち、絶対値が一番大きいものはかならず１になることがペロン＝フロベニウスの定理から言えるらしいのですが、よくわからないので解説できません…。