Lx=d: SundayResearch (Japanese version)

前回までに結果の上位 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   & 0.25 & 0   & 0.5 \\   \end{array}  \right] \end{eqnarray*} これが隣接行列から生成された S-Bahn の Markov Matrix である． octave

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 * 1000    600    400 これは前節の結果と一致する．何が違うかというと，固有値を求める方法では，M を 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    600.00    400.00 どうやらある一定の値に近付いているようだ．100 年たつと Berlin に 600 人，Potsdam

前回，時間の経過に共なって，人口の分布が一定の値に近づくことを見た．最後に考えた問題は，この結果が最初の人口の分布によって変化するかどうかであった．つまりこれは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 \\ &=& 120 \\ \mbox{Potsdam} \rightarrow \mbox{Berlin} &=& 400 * 0.3\\ &=&am

前回は隣接行列の拡張として 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 になることは既に見たが，それは住民全員を考えているからである．これが 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}

Eigenanalysis At which station am I? 隣接行列はグラフのトポロジ(接続関係)を示すものだった．しかし行列は接続関係を示すだけではなく，あるベクトルに作用して，他のベクトルを生成することもできた．たとえば，隣接行列を駅ベクトルに作用させることで次にどの駅に到達できるかを計算することができた．もう少しこの計算を続けてみよう．つまり，Weinmeisterstr に最初いるとして，各駅で乗り換えるかあるいは留まるということを繰り返す．その時，各駅に行く方法が幾通りあるかということが計算できる．ステップ数を増やしてみよう．まずは最初に Weinmeisterstr 駅にいる． \begin{eqnarray*} \begin{array}{|c|c|} \hline \mbox{Station} & \mbox{1 step} \\ \hline \mbox{Weinmeisterstr} & 1 \\ \mbox{Alexanderplatz} & 0 \\ \mbox{Hackescher Markt} & 0 \\ \mbox{Jannowitzbruecke} & 0 \\ \hline \end{array} \end{eqnarray*} 2 ステップでそれぞれの駅に行く方法の回数は，以下になる． \begin{eqnarray*} \begin{array}{|c|c|} \hline \mbox{Station} & \mbox{2 steps} \\ \hline \mbox{Weinmeisterstr} & 2 \\ \mbox{Alexanderplatz} & 2 \\ \mbox{Hackescher Markt} & 1 \\ \mbox{Jannowitzbruecke} & 1 \\ \hline \end{array} \end{eqnarray*} 3 steps, 5 steps, 10 steps を計算してみる． \begin{eqnarray*} \begin{array}

前回に続いて行列の計算についてみていこう．毎回同じ隣接行列を書くのはめんどうなので，駅の接続関係の隣接行列を\(M_{bahn}\)としよう．(Bahn はドイツ語で鉄道の意味) \begin{eqnarray*} M_{bahn} &= & \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \end{eqnarray*} \(M_{bahn}\) を一度駅ベクトルに掛けると隣接する駅が計算できる．二度掛けると2ステップで到達できる駅が計算できる．計算結果に出てくる数字は，各駅に到達できる道筋の数を示す．Weinmeisterstr にいるという駅ベクトルに二回\(M_{bahn}\) を掛けた結果は以下にようになる． \begin{eqnarray*} (M_{bahn})^2 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \end{eqnarray*} それぞれの要素が意味することは，それぞれの駅に 2 step で行く方法が何通りあるかということである． \begin{eqnarray*} \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \begin{array}{cccc} \mbox{Wein.} & \rightarrow & \mbox{Wein.} & \mbox{2 通り} \\ \mbox{Wein.} & \rig

前回ちょっと言い忘れてしまったことがある．それは隣接行列の対角成分をどうするかである．今回は駅には駅自身が接続されていると考えてもかまわないと思う．Alexanderplatz から Alexanderplatz へ行く場合，必ずどこか他の駅に行かなくてはならない場合には，上記の隣接行列は有用である．しかし．Alexanderplatz から Alexanderplatz へ行く場合，その駅に留まっても良い場合，には以下の隣接行列が使えるだろう． \begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 1\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 1\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 1\\ \end{array} \right] \end{array} \end{eqnarray*} 隣接行列は接続を示すだけではない．行列の演算によってどの駅からどの駅に行けるかがわかるところがまたすばらしい．たとえば，Weinmeisterstr にいるとして，次にどこに行けるか計算してみよう．Weinmeisterstr にいるということを以下のベクトルで示すことができる．これはいまいる場所を 1 として他を0としたベクトルである． \begin{eqna

D 嬢はちょっと騒がしい．時々自分でお話を作ってそれを大声で話している．さて問題はそれをどこでもすることである．とはいっても私はお話を作ることのできる人を尊敬しているので，あんまり静かにしなさいと言いたくない．でも他の子供が集中できないのは困る．それでなんとか問題に集中して欲しい． 先日の D 嬢は Zahlenhaus で足し算の練習をしていた．初級では足し算と引き算の関係を教えようというので，Zahlenhaus は以下のような計算がある．図 1には Zahlenhaus の例を示している． Zahlenhaus: 7 = 4 + 3 これを見て以下の計算をする． \begin{eqnarray*}  4 + 3 &=&  \\  3 + 4 &=&  \\  7 - 3 &=&  \\  7 - 4 &=&  \\ \end{eqnarray*} もう一つの例は， \begin{eqnarray*}  1 + 6 &=&  \\  6 + 1 &=&  \\  7 - 1 &=&  \\  7 - 6 &=&  \\ \end{eqnarray*} である．つまりこれによって加算は Commutative であること，簡単に言えば足し算をひっくり返しても同じ \(1 + 6 = 6 + 1\) であることを教え，引き算ではHaus を見ることで，片方を取ってしまうともう片方が残ることを教える．後半では以下のような問題になっている． \begin{eqnarray*}  \begin{array}[t]{cccc}   1 & + & 6 & = \\   6 & + & 1 & = \\   &   - &   & = \\   &   - &   & = \\  \end{array} \end{eqnarray*} D 嬢はこれらの計算をまったく間違えない． 私は答えがあっていることはあんまり興味がない．どう彼女が理解しているのかが面白いことである．そこで，

隣接行列とグラフのトポロジ 前回，隣接行列に関して説明したので，今回は隣接行列とグラフの関係を詳しく見ていきたい． 隣接行列はそれを見ればどのように点が接続されているかがわかる．接続されているかどうかだけを気にする場合，数学ではトポロジという言葉を使う．たとえば，Berlin の S-Bahn, U-Bahn の Web site にある Liniennetz は実際に距離が近いかどうかではなく，電車が駅に行けるかどうかという図である．隣の駅までの距離はあまり関係なく，実際のBerlin の地図の上の線路とはずいぶん異なっている．しかし，トポロジ(=つながりの関係)は正しい．  図 7 に戻ってみよう．ここには Alexanderplatz に接続されている駅が書かれている． Figure 7: Graph example 2. Each node is a train station. この図の隣接行列は以下のようになる．以下の行列には駅名の最初の4文字のみ示した． \begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 0\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{arra

今回は 3人の関係を考えよう．3人の関係では，行列は \(3^2\) の 9 の関係が生じる．以下図 10 の例を用いて説明しよう． Figure 10: A graph examples represents a relationship among three nodes. 3つの点の関係は以下の 3x3 行列によって示される． \begin{eqnarray*} \left[ \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{array} \right] \end{eqnarray*} 図 10 (a) は点1から点2への矢印がある．この時，行列の\(a_{12}\) 要素が 1 になる．したがって，この場合の隣接行列は以下のようになる． \begin{eqnarray*} M_{(a)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*} 以下，図 10 (b), (c) の例を示す． \begin{eqnarray*} M_{(b)} = \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{array} \right] \end{eqnarray*}  \begin{eqnarray*} M_{(c)} = \left[ \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ \end{array} \right] \end{eqnarray*} 図 10

前回の Alice 一人の場合は自分が好きなら1，嫌いなら0，ととても簡単だった．これではあまりに簡単すぎるので，Cheshire catにも登場してもらおう． Figure 9: Graphs representing relationships between Alice and Cheshire cat. 図 9(a) にはAlice は自分は好きだが，Cheshire を好きではなく，Cheshire は自分も Alice も好きではない場合を示す．その行列は以下のようになる．ここで注意することは登場人物の数の二乗の関係が生じていることである．2人の場合は，\(2^2\)，つまり 4 つの関係がある． \begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \left[ \begin{array}{c} 1 \\ 0 \\ \end{array} \right. & \left. \begin{array}{c} 0\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*} 図 9 (b) のグラフではCheshireは自分は嫌いかもしれないが，物語の中では Alice にはちょっとだけ優しかった気がする．だからCheshire は Alice を好きかもしれない．とりあえず Alice は Cheshireをそんなに好きではないとしよう．その場合の隣接行列は次のようになる． \begin{eqnarray*} \begin{array}{ccc} & \mbox{Alice} & \mbox{Cheshire}\\ \begin{array}{c} \\ \mbox{Alice}\\ \mbox{Cheshire}\\ \end{array} & \le

今回は Alice に登場してもらおう．(Alice に登場してもらおうというのは，前回説明したように，私が勝手に決めたことの例)  図 8 (a) はAlice の点を示し，また辺がないので Alice はAlice 自身を好きではない．図 8 (b) では Alice は Aliceへの辺があるので，Alice はAlice を好きである． Figure 8: Graphs representing relationships between Alice and herself. Alice 一人の場合，Alice が自分を好きではない場合(図 8 (a))の隣接行列は次のようになる． \begin{eqnarray*} \begin{array}{cc} & \mbox{Alice}\\ \mbox{Alice} & \left[ \begin{array}{c} 0\\ \end{array} \right] \\ \end{array} \end{eqnarray*} Alice が自分を好きな場合(図 8 (b)) の隣接行列は次のようになる． \begin{eqnarray*} \begin{array}{cc} & \mbox{Alice}\\ \mbox{Alice} & \left[ \begin{array}{cc} 1 \\ \end{array} \right] \\ \end{array} \end{eqnarray*} 今回は Alice 一人しか登場しないので，関係と言っても簡単だった．次回はもう少し現実味のある関係の話をしよう．

隣接行列 行列は数を二次元のます目上に並べたものである．これは数の表のように見える．ある規則で数を並べると，それがグラフを示すことと同じことになる．それを説明しよう．行列はグラフを表現するだけではなく，さらにいろいろなことができるのだが，ここでは特にグラフの表現をすることに集中して説明する．行列に関してもっと詳しく知りたい人には，文献 [1] をお勧めする． 行列について述べる動機はグラフを記述することにある．ここでいうグラフを表現する方法の一つとして隣接行列がある．ここでその定義を述べておこう． Definition of adjacency matrix:  n 個の点を持つグラフは \(n \times n\) の大きさの隣接行列で表現することができる．ここで，点\(i\) と点 \(j\) 間に有向辺がある場合，行列の成分 \(a_{i,j}\) を \(1\) とし，辺がない場合には \(0\) とする． これだけである．つまり隣接する点(= 辺で接続されている点)の要素を 1，そうでない要素を 0 とするような行列を隣接行列と呼ぶ． 例として人間関係のグラフを考え，好きか嫌いかの関係を隣接行列で示そう．好きという関係がある場合には点の間に辺を置くとここでは決める．嫌いな場合に辺を置くとしても良いが，私は嫌いな関係よりも好きな関係を知りたいので，今回は好きな関係とする．注意して欲しいのはこういう部分は私が勝手に決めることができるということである．これは事実とかではなくて，問題を解こうとしている人が矛盾が起きない限り，勝手に決めることができる．もし私が，「定義する」とか「仮定する」とか「と，考えてみよう」と言ったら，それは私が決めたことであって，読者には賛成してもらいたいと思っている．もし読者が賛成しない場合，その後の議論は意味をなさない． 次回は具体的なグラフと隣接行列の例としてアリスに登場してもらい，その人間関係を示そう． 参考文献 [1] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition'', Wellesley-Cambridge Press,  2009