Friday, December 28, 2012

マルコフ行列の中の著者達 Part 2 (3): どの著者がもっとも人々に影響を与えたのか? 実験編


今回はどんな 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 はもう一つ変わった点として著者への平均リンク数が他に比較してずいぶん高いことがある.ここでのリンク数は Wikipedia 内での著者に分類されている Page にリンクがあるかないかであって,Page 中にある全てのリンク数ではない.例えば,同内容他言語Page へのリンクや,self link,著者ベクトルにないリンクは除外してある.したがって,著者でない人へのリンクが多くあってもそのリンクは数に入っていない.表 2 には matrix にサイズに関するデータを示した.

Table 2: Matrix size, non zero elements, and the average number of  links between authors. Wiki ``en'' means en.wikipedia.org.
これらの matrix は PageRank algorithm [1] に従って rank sink node を除いた.これに共なう link も除いたので,いわゆる dangling link (文献 [1] 2.7節)も除かれている.また,外への link しかない node も除いた.外向きのlink しかない node は PageRank では意味がないが,原論文 [1] では除かれていない.これは原論文では Webを対象にしていたため,外向きの link しかない node であるかどうかを判断することが困難であるからだと思われる.一方で我々の実験では全ての page の規模自体が小さいので これを判断することが可能である.このリンクを除くかどうかの違いはnormalization 部分に出るのだが,normalization はPageRank 値よりも行列の性質を改善するものであり,また PageRank の絶対値は相対値に比較してそんなに重要ではない.我々にとっては,誰の影響力が他の誰かよりも高いかが重要であって,PageRank 絶対値にはあまり興味がない.したがって,normalization の値の違いは我々の目的としてはあまり影響がないと考えられる.これは PageRank の原論文でもそのように考えられている.

この結果縮小された matrix の大きさとその rank を表 3 に示す.

Figure 3: Adjacency matrices: original size, reduced size, and its rank.

次回はようやく Wikipedia 的に誰が重要な著者かの結果である.

注1: この記事を連載していた当時(2012-12-29) 友人の Joerg M. より指摘がありこの箇所を更新した.

No comments:

Post a Comment