Lx=d: SundayResearch (Japanese version)

付録 A: Unicode and Python 2.7.x 今回 Python 2 にて Unicode の処理をする必要が生じた．これは日本語の Web page やドイツ語の Web page の処理のためである．実際には英語の Web pageにも accent のある文字が出現することがあるので，Unicode は避けて通れなかった．プログラムの開発中に，UnicodeDecodeError と UnicodeEncodeError というexception に悩まされたので，これを解説しておく． How the Unicode encodes characters? Unicode は私の理解するところ，2つの map を使う coding system である．これはどのようにこの体系を理解するかにもよる．私はこの調査をするまではこのことを知らなかったので UTF-8 などという coding system があると誤解していた．UTF-8 というのは Unicode をどのように codeするのかという mapping の手法の一つであって，Unicode そのものではない． Unicode: a map from characters to code (numbers) UTF-X:   a map from Unicode encoded data to a specific data Unicode そのものは code point と呼ばれる番号と文字の Description の単一のmapである．たとえば. 0x0061 'a'; LATIN SMALL LETTER A である．ここで0x0061 という数字が code point である．これが font に map されると，図形としての文字が表示される．図形としての文字は glyph と呼ばれる．Unicodeのmap は bijection であるので，文字 a は code point 0x0061 へmap されるとも言える． この code point が Unicode，つまりある数を特定の文字への code している．しかし通常この Unicode の code point は使われない．通常使われないという意味は，...

結論 どの著者が Literature に影響を及ぼしているかを調べるため，Wikipedia のlink 構造を抽出し，それに PageRank アルゴリズムを適用した．その結果は表に示した通りである．また異なる言語の Wikipedia のデータを同じカテゴリ(今回の例では著者)に関して適用することで，各言語の Wikipedia 間の違いを見ることができた． 個人的に面白いなと思ったのは，たとえばイギリスの著作家に Winston Churchil や Issac Newton が入っていることである．今回始めて Winston Churchil はノーベル文学賞受賞者であることを知った． Computational Literature 私は最近，言語や文学を理解するために，情報科学あるいは数学的なアプローチを用いている．Bren'e Brown は彼女の TED talk で ``Maybe stories arejust data with a soul.'' と述べた．もしかしたらそうかもしれないと思う．ただし，私は soul が data にかすかな影を落としているように思えてならない．もちろん，現状ではこの影から soul を再構成することなど到底できそうにない．それでも，すばらしい作品は私の心を動かす．本を読むというのは，ある意味，ただ単なるデータ，シンボルの列，を読んでいるだけなのに，感動が起こることは確かにある．私はこの魂の影がデータの中にあるのではないかと思って，このようなアプローチを試してみることがある．今回の著者の文学界への影響というものも，その一種の試みである．私はこのアプローチを何と呼んで良いのかわからないのだが，他に良い名前を思いつくまで仮に，これを計算機を用いた文学へのアプローチという意味で， Computational literature と呼んでいる． Future work 議論で述べたこと含めてまとめておく． Wikipedia の著者による bias はあるのか どのように自動でデータを取得するか．カテゴリの問題を避ける方法はあるか． PageRank 以外のグラフ構造解析アルゴリズムを用いてはどうか． Marix が full rank でないこと...

今回も結果に関する議論の続きである． No link found problem ドイツ語の Wikipedia での日本の作家には人物の Link 切れの問題が印象として残った．これは数を調べたわけではなく，調査中に見うけた問題である．伸ばす音の人物のリンクが切れていることが多いという印象を持った．たとえば，良寛(Ryōkan)に言及している page がリンクのキーを Ryokan にしたり，漱石(Sōseki)に言及している page が Soseki にリンクを張ったりしているため，リンク先の page が見つからない．このような伸ばす音のある作家へのリンク切れが目についた． Cross reference between Wikipedia ドイツ語と英語の Wikipedia では，同じ Latin 文字の表示を用いているため，cross reference を作成することが容易であった．しかし，日本語はイギリスの著作家であってもキーとして日本語の文字を利用しているため，Crossreference をプログラムで作成するには，日本語から英語への変換の map が必要である．これを正しく作成することは手間がかかるので，今回は見送った． Correlating with other data 友人と議論しているうちに，今回の結果と他のデータとの組合せをみたい項目がいくつかでてきた． Nobel prize winner と Pagerank の結果の関係 Wikipedia の著者と Pagerank の結果の関係．特に Wikipedia の著者による bias というものがあるのかどうかに興味がある． Johann Wolfgang von Goethe is 10th in Japanese Wiki Johann Wolfgang von Goethe が日本語の Wiki では10 位と意外な低さだったことである．しかし，日本語の ドイツ文学に関するPage でネットワークを構成するページはわずか 31 ページしかないので，わずかなページが強い影響を示す可能性がある．ちなみに日本語の Wiki でのドイツ文学者の一位は Gerhart Hauptmannである． 長かったこのテーマも終わりに...

Wikipedia's Category problem ここで言うカテゴリ問題とは，期待した人物が Wikipedia によっては異なるカテゴリに属しており，データの取得に失敗している問題である．以下のsubsection で示すような問題が判明した．これらに関しては何の処理もしていないので，たとえば，「Shakespeare が日本の Wikipedia 解析の結果では英国の文学者としては存在しない」というような問題でもそのまま結果に示した． 私は趣味でこのような調査をしているため，データの取得はできる限り自動で行いたい．そのため，今後どうやって自動でデータを取得するかは課題として残った． No Shakespeare in Japanese Wikipedia result Shakespeare はドイツ語，英語共に英国の著者としては一位であったが，日本語の Wikipedia の結果には Shakespeare が存在しない．調べた所，日本語のWikipedia では Shakespeare というカテゴリが存在し，イギリスの著作者に分類されていない．そのため，今回のようにroot page を指定した方法ではこれらの作家は存在しないことになってしまった． 図 7 にこの Page を示す． Figure 7: The category of English authors page in ja.wikipedia.org as of 2012-11-19. イギリスの小説家のカテゴリ ハーバート・ジョージ・ウェルズ シェイクスピア ジョージ・バーナード・ショウ ジョージ・ゴードン・バイロン ウィリアム・ブレイク オスカー・ワイルド これらが同列の階層に位置するため，ウェルズ，シェイクスピア，ショウ，バイロン，ブレイク，ワイルドはイギリスの小説家に分類されていない．これは日本語の Wikipedia 固有の問題であり，他の言語の Wikipedia にはない問題である．(ここで問題というのは，我々が「イギリスの小説家一覧」という一覧にこれらの人物も入っていると仮定したことから生じる．我々は実験を始める前にこの仮定は妥当だと考えた．) No Shiki Masaoka in the J...

前回までに結果の上位 40 位の表を掲載した．この表を眺めているといろいろと興味深いので，まずは名前をざっとご覧になられると良いと思う．ここからはこれまでに掲載した表などに関しての議論を述べる． 議論 Matrix rank 表 3 では，sink rank や外向きのみのリンクを持つノードを除いたにもかかわらず，matrix は full rank ではないことを示している．これはlink 関係に相互リンクのあるいくつかのグループが存在していることを意味する．このようなグループに関する調査は将来の課題とする． Japanese Wikipedia template bias 最初，日本の Wikipedia での pagerank 計算結果を見たところ，夏目漱石も芥川龍之介も三島由紀夫も森鴎外も全て 100 位以下であった．また，日本の著者に関する結果はドイツ語と英語の Wikipedia の結果とあまりにもかけ離れていた．調べた所，芥川賞受賞者が圧倒的に上位に入っていることが判明した．これは図 5 に示すように，芥川賞受賞者間では相互リンクが張られるからである．受賞者は全ての他の受賞者からリンクを受ける．これによってpagerank が高くなる．そこで今回の計算では受賞者の相互リンクは排除した．その結果が表 12 である． Figure 5: Award winner cross link bias problem. この芥川賞のリンクがどのような bias を生んでいるのか興味ある読者のために，まったく Postprocessing 処理をせずに PageRank を計算した結果を表 13 に示す．表 13 の全員が芥川受賞者である(注 1)．実際には芥川賞受賞者全員が上位に来る結果となった．この方式では 101 位に初めて芥川賞受賞者でない三島由紀夫が登場する．Bias を除くと，芥川賞受賞者のうち次の 8 人のみが Top 40 に入っている:大江健三郎，松本清張，吉行淳之介，開高健，丸谷才一，古井由吉，石原慎太郎，安岡章太郎． 図 6 にはこの postprocessing をした場合としない場合の Adjacency matrix を示しておく．Matrix の比較をすると，bias と考えられる内部の相互リンクがパ...

日本の著者の結果 Table 10: Japanese author rank result in de wikipedia. Table 11: Japanese author rank result in en wikipedia. Table 12: Japanese author rank result in ja wikipedia. 次回はこの結果に関する議論を行う．

イギリスの著者の結果 Table 7: English author rank result in de wikipedia. Table 8:English author rank result in en wikipedia. Table 9: English author rank result in ja wikipedia. (Our page rank implementation can only find 29 valid authors.)

今回から3回は遂にPageRank(Eigen analysis)結果を示す． ドイツの著者の結果 Table 4: German author rank result in de wikipedia. ``en'' is en wikipedia's rank result. Table 5: German author rank result in en wikipedia. Table 6: German author rank result in ja wikipedia. (Our page rank implementation can only find 31 valid authors.)

今回はどんな matrix が生成されたかについて述べる． 実装 今回以下の 4 つのプログラムを実装した． Link_Vector_Extractor: 作家のリストベクトルを作成する Graph_Extractor: 隣接行列を作成する Page_Rank: PageRank の計算を行う Remapper: PageRank 結果を作家のリストベクトルに map する 実験に利用した計算機環境は CPU: Intel(R) Core(TM) DUO CPU P8400, 2 Cores, OS: 64bit Linux 3.2.0.32, Kubuntu 12.04. である．プログラミング環境としては Python 2.7.3, Beautiful Soup 4.0.2, matlab R2006a, octave 3.2.4を用いた． Adjacency matrix Adjacency matrix がどんな形になっているのかを図 2, 3, 4 に示す．この図では隣接関係がある著者間に点がうたれている． Figure 2: Adjacency matrices. Top to bottom: German authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org. Figure 3: Adjacency matrices. Top to bottom: English authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org. Figure 4: Adjacency matrices. Top to bottom: Japanese authors in de.wikipedia.org, en.wikipedia.org, ja.wikipedia.org. German author の en.wikipedia.org に規則的なパターンが見られるが，これに関しては後に述べる template bias の可能性が高い(注1)．また，en.wikipedia.org はもう一つ変わった点として著者への平均リンク数が他に比較してずいぶん高いことがある．...

実験 実験に用いたデータを表 1 に示す．幸い，どの Wikipedia にも各言語の作家のリストが存在したので，そのリストを Root page として直接リンクされている作家の page を download した．Download に際しては 15 秒に 1 pageのスピードで download し，サーバへの負担にならないように注意した．ここで利用したWikipedia のページのうち，日本語の「石原慎太郎」は例外的にファイルが圧縮されていたため，実験においては展開して利用した．Root page に関しては，他にも候補はあったが，表 1 にあるものを利用した．例えば，ドイツ語 Wikipedia におけ英語の著者として，Liste_englischsprachiger_Schriftsteller ではなく，Liste_britischer_Schriftsteller を利用している．これは私が任意に選んだだけであって，こちらでなくてはいけないという理由はない．なお，実験に使用したファイルは全て 2012-5-30 に download したものである． Table 1: Experimental data set.

今回から Part 2 の実験編である．これまではどうやって最初の疑問，「どの著者がもっとも人々に影響を与えたのか?」について考えてきた．Part 2 ではついにこの答えについて述べる． 著者間の関係の解析 著者グラフの作成方法 著者間の関係を eigenanalysis を用いて実際に解析してみる．まずは著者間の隣接関係を作成する必要がある．もちろん私が手で作成しても良いのであるが，日本の著名な著者だけでもおそらく千人は下らない人数がいるであろう．その著者間の関係を調べ挙げるだけで，私の生涯の趣味の時間では不足するだろう．このグラフのデータを簡単に入手することはできないだろうかと考えた．Web 上のデータで使えるものはないかと考えた時，Wikipedia の Link 関係が良いのではないかと思い，これを利用してみた． 本実験の前提 Wikipedia の著者の Page にある Link 関係は著者間の関係を示していると仮定する． この前提に異論があることは確実であろう．まず，著者間の関係とは何か，というような問題に戻ることになる．したがって，ここでは著者間の関係はWikipedia の Link 関係として与えられるものと定義する．直感的には，「Wikipedia の筆者らが link を張った著者間には，Wikipedia の筆者らが，著者間に関係があると考えたからである．」と考えても良いと我々は思ったからである．この仮定が認められない場合には以下の議論は全て成立しない．今後，より良い手法が出てきた際にはこの前提を再考する必要があるであろう． この前提に基き，Wikipedia のリンクの関係を著者間の隣接関係として，固有値問題を解くことにする． この方法には次のような利点と欠点がある． 利点: 大量のデータが既に利用可能 ある程度の review がなされている 人間によって書かれているので，リンク構造には意味があることが予想できる 欠点: リンク構造の誤りがある可能性がある 特定の Wikipedia の著者による bias がある可能性がある Wikipedia の編集方針による bias がある可能性がある ここで私は大量のデータが既に利用可能であるという利点を最大限に活用することに...

Google PageRank ここで PageRank という手法 [2] を紹介する．Web page 間の影響力というものをどう考えるかについて，Sergey Brin と Lawrence Page という二人は，Web page のリンクを隣接関係として考え，その固有値問題を解くことでWeb の重要度を計算し，それを Web page のサーチの基礎として利用することを提案した．後にこの二人はこのアルゴリズムを使ったサーチエンジンの会社Google を設立する．この論文には，Jon Kleinberg が既に Web 環境を用いて引用関係をリンクによって表現する場合，これを固有値問題として考えることを提案していると記されている．固有値問題そのものは線形代数で基本的なものとして長年研究されてきた．では PageRank そのものは新しくなく，この二人は運が良かっただけではないかというと私はそうは思わない．シンプルでソリッドなアイデアを実際に世界規模で使えるように実装したというところがすごいことだと思う．また，Web のサイズを考えれば，単に固有値を求めるということも単純ではない． ここでの私の説明は，文献 [9] の書法に従っているが，PageRank の論文[2] ではちょっと違う書法を用いているので注意しておく． PageRank の論文中, page 4, 2nd paragraph では固有値が，\(R=cAR\)となる c となっている．ここでは\(Mx = \lambda x\) の \(\lambda\)と記述した．したがって，\(\lambda = \frac{1}{c}\) である． PageRank の論文では，Web のグラフは不完全であるため，そのまま固有値計算をすることはできないことを説明している．たとえば，リンク切れを除くことや，リンクがループしている場合などを挙げ，その対策を述べている．基本的にはユーザがリンクをランダムにクリックしていくが，時々リンクとはまったく関係ないランダムなページにも移動するという考えを用いている．すなわち，PageRank は，Web をスキャンして隣接行列を作成し，リンク切れやループなどの処理を行なった後，ランダムに移動する項を加え，Markov matrix を作成して，固有値問題...

Again, at which station am I? 2つの街の人口の移動の関係を用いて Eigenanalysis に関して説明してみた．これは Berlin の S-Bahn の例に用いることもできる．その方法を示そう． 街の人口の推移と同様，駅間での人の移動ということを考えることができる．隣の駅に行く可能性はどの場合も同じとしてみよう．この場合，隣かそうでないか，つまりトポロジが人の移動形態を決定する．この移動可能性を示す行列は隣接行列のカラムを正規化することで作ることができる．もしある駅が2つの駅に接続されていたならば，各駅に移動する可能性は 1/2 づつになる．同様に3つの駅に接続されている場合には各接続されている駅に移動する可能性は 1/3 である．これは最初に隣の駅に行く可能性をどの駅でも同じと仮定したからである．違うモデルを用いることもできる．駅の隣接行列をこの可能性の行列に各カラムを確率として\(L_1\)で正規化すると，以下のようになる．(細かいことになるが，ここでは確率を考えているので，\(L_1\)ノルムを使用した．) \begin{eqnarray*}  \left[   \begin{array}{cccc}    1 & 1 & 0 & 0 \\    1 & 1 & 1 & 1 \\    0 & 1 & 1 & 0 \\    0 & 1 & 0 & 1 \\   \end{array}  \right]  \rightarrow  \left[   \begin{array}{cccc}    0.5 & 0.25 & 0   & 0 \\    0.5 & 0.25 & 0.5 & 0.5 \\    0   & 0.25 & 0.5 & 0 \\    0   ...

How to compute the eigenvectrors? これまで，固有ベクトルがどのようなものかは説明してきたが，計算方法については述べてこなかった．実際に固有値ベクトルをどう計算するかのアルゴリズムはここでは述べず，既にあるフリーソフうウェアを使うことにする．octave では eig という関数が教えてくれるのでこれを使おう． 計算してみよう． octave:34> [L V] = eig(M) L =    0.83205  -0.70711    0.55470   0.70711 V = Diagonal Matrix    1.00000         0          0   0.50000 以前私は固有値が matrix と同じに見えると言った．確かにそうであるが，一つの数字で matrix を完全に表すことはできない．もしできるのならば，matrixは不要になってしまう．実は通常の matrix は複数の固有値と複数の固有ベクトルを持つ．それでも matrix の要素の数 \(n^2\) に比較して \(n\) しか固有値は存在しないのでかなり簡単になる． この Matrix の固有値は 1 と 0.5, 対応する固有ベクトルは (0.83205,0.55470) と (-0.70711, 0.70711) である．ここでは 0.5 の固有値は無視する．なぜなら，この固有値は Markov matrix がどのように収束するかついては教えてくれないからである．詳しく知りたい読者は Matrix diagonalization について調べてみて欲しい．固有値が 1 の固有ベクトルが，Markov matrix がどのような値に収束するのかを教えてくれる．それを計算して，総人口1000 人の分布を見ると以下のようになる． octave:38> x1 = L(:,1)/ sum(L(:,1))    0.60000    0.40000 octave:39> x1 * 100...

前々回には，Berlin の人数と Potsdam の人数がいかなるものであっても，その無限回の操作の結果は一定に落ちつくことを見た． この Berlin 600 人，Potsdam 400 人というベクトルはこの Matrix にとって特殊なベクトルであって固有ベクトルという名前がついている．このベクトルを図12 の上に書いてみると，図 13 になる．見事に固有ベクトル上に人口の分布が並んでいるではないか． Figure 12: Population history with various initial conditions. Figure 13: Population history of Berlin and Potsdam with $y =\frac{400}{600}x$ line. 固有ベクトル \(\vec{x}\)は matrix \(M\) に対して， \begin{eqnarray*} M\vec{x} &=& \lambda \vec{x} \end{eqnarray*} となる特殊なベクトルである．ここで \(\lambda\) はスカラ値である．このスカラ値にも固有値という名前がついている． ここでは次式のように \(\lambda = 1\) である． \begin{eqnarray*} M \left[ \begin{array}{c} 600 \\ 400 \\ \end{array} \right] &=& \left[ \begin{array}{c} 600 \\ 400 \\ \end{array} \right] \end{eqnarray*} ここでのベクトルは定数倍しても変化しないので， \begin{eqnarray*} M \left[ \begin{array}{c} 6 \\ 4 \\ \end{array} \right] &=& \left[ \begin{array}{c} 6 \\ 4 \\ \end{array} \right] \end{eqnarray*}...

前回，「数学が数について考えなくなる」ことを述べた．これに関しての話をしよう． ある種のすぐれた文学や音楽の中に時に数学に関する深い洞察をみつけることがある．バッハの音楽にみられる数学的形式，俳句に見られる厳密なパターン，夏目漱石の数学的洞察，そしてそれを感情のゆさぶる粋にまで高める芸術性．数学を学んだおかげで驚くべき一面を見ることができたのは楽しい． 中島敦の「名人伝」という作品をご存知だろうか．私は「弟子」も「李陵」も好きだが，この「名人伝」がとても好きだ．矢の名人が更にその段階を越えていき，名人の中の名人から次の言葉を聞く．「それは所詮射の射というもの，そなたはいまだ不射の射を知らぬと見える．」弓を持って矢を射るのでは所詮弓矢の世界を越えられぬ．その世界を越えるには，弓を持たずして矢を射る世界に入るのである． この中国の古典を元にした日本の作品を人々に説明すると冗談と思われてしまうことが多々あり，私は説明に苦労する．日本語では数学は数の学問であるが，この時点に来た時，我々は数を忘れる．「数を使って数学をするのでは所詮数の数に過ぎぬ．そなたいまだに不数の数を知らずとみえる．」数学が数の操作ではなく数を忘れ，操作そのもの(演算子)の可能性について論じ始めた時，数学は転換期を迎えた．引き算が生まれた時，人々はできない引き算があることに気がついた．たとえば，3 - 5 は計算できない．これはマイナスの数が発明されるまで問題であった．できない計算があると気がつくと，これまでの演算にも疑いが生じる．足し算はいつもできるのか? 大きな数になると足せないことがあるのかもしれない．知っている特定の数だけではなく，全ての数に関して足し算はできるのだろうか? 割り算にもやはり演算ができない場合があった．3/5 は分数がなければ計算できない．マイナスの数を発明しても 3/5 は計算できない．いったいこれはどこまで続くのか? 一つの演算子だけではない，全ての演算子について考えることはできるのだろうか．一つの数だけでなく，全ての数について考えたように．操作の結果の集合が何であるかについて考えることを提案したガロアの仕事が革命的であったのは，彼が数の数学から，操作の数学へと飛翔したからであると私は思う．計算機科学でも同じである．プログラムで数を与えて数を返す基本的な関数から，...

前回は隣接行列を拡張した人口の移動の行列を紹介した．今回は前回までの仮定から，人口は未来にどうなるかを予想してみる． まず，計算する前にいくつかの仮説を立て，それについて考えてみよう．私が数学で楽しいのはいろいろ予想してそれを後で確かめることである．思った通りになると楽しい． 一つ確実なことは総人口は 1000 人のままということである．これは誰も生まれず，誰も死なず，全ての人々はどちらかの街にいる．という仮定から導かれる． 仮説1 Berlin に留まる人の割合(0.8)の方が Potsdam に留まる人の割合(0.7)よりも大きいので，いつかは全ての人が Berlin に移動する． この仮説は残念ながら正しくないようだ．というのも，Berlin の人口が増加すると，その2割が Berlin から流出するので，900人の時には 180 人が Berlin から流出するが，Potsdam の人口は最初 100 人なので，その 3 割が Berlin に移ったとしても，30 人しか流出しない．実際，一年後と二年後の結果では Potsdam の人口が増加している． 仮説2 この二年の変化を見ていると，Potsdam の人口は\(100 \rightarrow 250 \rightarrow 325\) と推移してきた．しかし，ある時点で，Potsdam の人口が十分多くり，流出の割合も大きいことが効いてきて，Potsdam の人口が減少に転ずるであろう．そうすると，今度は Berlin の人口が多くなるのではないだろうか．これを繰り返すという人口の振動が発生するのではないだろうか． この仮説が正しいかどうかちょっと計算してみよう． octave:5> M^3 * p    637.50    362.50 octave:6> M^4 * p    618.75    381.25 octave:7> M^10 * p    600.29    399.71 octave:8> M^100 * p    60...

前回，時間の経過に共なって，人口の分布が一定の値に近づくことを見た．最後に考えた問題は，この結果が最初の人口の分布によって変化するかどうかであった．つまりこれはmatrix の性質なのか，matrix と初期状態の両方を合わせた性質なのだろうか． 仮説3 初期条件によって将来は変化して一概には決まらない．例えば，ここまでの例では Berlin に最初 900 人，Potsdam に 100 人いたが，Berlin に最初 0 人，Potsdam に 1000 人いた場合には違った結果になるだろう． これも計算してみよう．Berlin には最初誰もおらず，1000人全員が Potsdam にいるとしよう． octave:10> p = [0 1000]'; octave:11> M * p    300    700 octave:12> M^2 * p    450.00    550.00 octave:13> M^3 * p    525.00    475.00 octave:14> M^10 * p    599.41    400.59 octave:15> M^100 * p    600.00    400.00 なんと，初期条件を変えても結果は同じになってしまった．様々な人数の初期状態でどのように人口が推移するかを示したのが図 12 である．何かのパターンが見える．そしてパターンを考えるのが数学である． Figure 12: Population history with various initial conditions. ところで，この Berlin 600 人，Potsdam 400 人というのは特別な数であることに気がついただろうか．移動の人数を計算してみると， \begin{eqnarray*} \mbox{Berlin} \rightarrow \mbox{Potsdam} &=& 600 * 0.2 \\ ...

前回は隣接行列の拡張として Markov matrix を導入した．ここで具体的な Markov matrix \(M\) の例を以下のように考える． \begin{eqnarray*} M &=& \left[ \begin{array}{cc} 0.8 & 0.3 \\ 0.2 & 0.7 \\ \end{array} \right] \end{eqnarray*} \(M\)の要素の意味を具体的に書くと，以下のようになる． \begin{eqnarray*}  M &=&  \left[   \begin{array}{cc}    \mbox{Stay Berlin}       & \mbox{P $\rightarrow$ B} \\    \mbox{B $\rightarrow$ P} & \mbox{Stay Potsdam}      \\   \end{array}  \right] \end{eqnarray*} ここで，\(\mbox{B $\rightarrow$ P}\) は Berlin から Potsdam に引っ越す人の割合，\(\mbox{P $\rightarrow$ B}\) は Potsdam から Berlin に引っ越す人の割合を示す．つまり，一年たって，Berlin に 8 割の人がそのまま Berlin に住み，2 割の人は Berlin から Potsdam に移動する．全ての人に関して考えているので，カラムは合計 1となるように(0.8 + 0.2 = 1.0) なっている．Potsdamの場合も同じである．7割の人は一年後も Potsdam に住み，3割の人がBerlin に引っ越す．この場合にも，カラムは合計 1 となっている． 「何割の人が移動する」ということを示す Matrix なので，要素は全て 0 以上であり，1 以下である．たとえば，マイナスの割合の人が移動するということはない．また，カラムの合計が 1 になることは既に見たが，それは住...

Markov matrix 駅の接続関係の例では，自分がいた場所から，何度か電車を乗り継ぐことによってどの駅に到達できるかということが示された．隣接行列は駅間を電車で移動するという操作をしていると考えることができる．ここではもう少し単純化して，移動ということに着目してみよう． Berlin の中心から S-Bahn で 40 分ほど離れた場所に Potsdam という街がある．街が近いので人の移動も多い．Berlin から Potsdam に引っ越す人もいればその逆もある．これらの街が接続されていると考えれば，隣接行列で示すと以下のようになる． \begin{eqnarray*}  \left[   \begin{array}{cc}    1 & 1 \\    1 & 1 \\   \end{array}  \right] \end{eqnarray*} 一応この隣接グラフが何を接続しているかを示しておく． \begin{eqnarray*} \begin{array}{ccc} & \mbox{Berlin} & \mbox{Potsdam} \\ \begin{array}{c} \\ \mbox{Berlin} \\ \mbox{Potsdam} \\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ \end{array} \right. & \left. \begin{array}{c} 1\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*} この行列では到達できるかどうかということだけだったので，どちらの街にも行けるし，どちらの街にも留まることができるという意味ではあまり面白い例ではない．しかし，これに人の移動の割合というものを入れてみよう． 人口を示すベクトルとして，以下を考える． \begin{eqnarray*} \left[ \begin{array}{c} p_{b} \\ p_{p} \\ \end{array}...