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

問題: 著者の影響を解析する (2)

私は影響の大きさや内容ということはとりあえず忘れ，関係のあるなしから全体への影響の大きさを考えるという方法から始めることにする．幸い，このような関係のあるなしを基礎にしている数学の理論や，実際に利用されてきた方法がある．その方法とはグラフ理論と線形代数という数学を使うものである．この方法は長年の間多岐に渡って利用されてきた．Web の時代になり，Web page間の関係を知るためにも用いられている．影響力の大きなPage は興味ある Pageであるだろうから，サーチの結果の上位に示せば探している Page をみつけやすいだろうということで，どのように影響力の大きな Pageを求めるかが考えられてきた．

おそらく現在最も利用されている手法は，Web page の影響力を，Web page 間が関係しているかいないか，つまりリンクは張られているかいないか，だけをもとにして計算する方法であろう．この方法は Web page の内容はまったく理解せずに影響力を考えることができる方法であり，画期的であった．この方法はGoogleという会社が初めて Web page のサーチの基準として用いたことで有名である[bib:pagerank]．内容を理解しなくても良いということで，どの言語でも，どの分野でも利用可能であり，自動化が可能である．人間が内容を元にランクをつけた方が精度は良い可能性は高いが，何千，何万という計算機を使って自動で行えるという方法は人間よりも高速で安価であり，人間がランクを決めていた方式にたちまちとってかわった．

Web に応用する手法は特に PageRankと呼ばれているが，その基礎には線形代数の固有値問題がある．

ここではまずグラフ理論を概観し，それを実際の著者間の影響を計算する方法として応用してみる．

というわけで次回はグラフ理論入門である．

Comments

共有メモリによるプロセス間通信

Unix の共有メモリを使ったプロセス間通信について調べて実験をしてみた．対象は1つのホスト上での複数のプロセスである．ネット上でいくつか例題はないかと探したが，どうも良い例となるコードが見当たらなかった．結局はある解説記事と，Stack Overflow の議論と，man page を見て作ってみたものになったので，例をここに置くのも有用かと考え，この記事を書く．(もしかしたら探し方が悪くて良いコード例をみつけられなかっただけかもしれない．) mmap を使うかどうかという話がいくつもでていたが，POSIX の方向としては，shmem_open と mmap を使うという方向があるということだったので，それを信じてその形での実装を試してみた．基本的なコードの流れは次のようになる．共有メモリ領域を1つのプロセスが shm_open() を使って作成する．その際に，プロセス間で共通の文字列を識別子(``identifier'')とする．(Linux ではこれが /dev/shm/identifier のように見える．) 共有メモリ領域を mmap() でメモリにマップする．共有メモリポインター (shared_ptr)が得られる． shared_ptr を使って複数のプロセスで通信をする．利用終了後は munmap() をつかってマップを消す．共有メモリオブジェクトを shm_unlink() によって消す．以下に示すプログラムは，server と client の2つのプロセスが共有メモリを使って通信をするものである．ここで，server プロセス数と client プロセス数は共に 1 を仮定する．server と client は自分の領域にしか値を書き込まないことで，ロックを避けている．互いに相手の値を読み，それよりも1大きい数を一定の期間ごとに自分の領域に書くという例題である．シンプルではあるが，共有メモリで通信をする基本としては十分なものだと思う．ソースコード(shmem_test.cpp)を以下に付加する．ソースコードのコメントにコンパイル方法とどのように利用するかを書いておく． /* Shared memory inter process communication minimal exa...

複数の線を持つ線グラフを Jenkins の plot plugin で描く方法

私は毎夜のソフトウェアテストを自動化するために Jenkins というツールを使っています．今回は， valgrind を使ってメモリーリークのテストを自動化することにしました．その際，エラーの数の結果をグラフとして表そうと思って， Plot plugin を使うことにしました． Plot plugin の例図からは，複数のデータラインを描くことができるのは明らかなのですが，どうやったらいいのかは参照のページや，例としてあった Perl script，plugin 中の help からは私にはよくわからなかったのです．ここで重要な考えは，それぞれのデータラインにはそれぞれの出力ファイルが必要ということでした．私はこれを誤解していました．例として，ビルドの時に次の property データファイルを出力します．それぞれのファイルが1つのデータラインを表します． valgrind_trunk_result.definitely.property valgrind_trunk_result.indirectly.property valgrind_trunk_result.possibly.property それぞれのデータの中身は1行のデータ点です．たとえば， valgrind_trunk_result.definitely.property ファイルの中身は次のような1行です． YVALUE=0 このファイルを ${WORKSPACE} ディレクトリ以下に出力します．ここで，" WORKSPACE " は jenkins が提供する環境変数です．図1が私の plot plugin の設定を示しています．これは jenkins の config 画面です．3つの data series があって，それぞれにデータファイルがあります． Figure 1: Plot plugin configuration in Jenkins 図2が結果です．複数の線が描かれているのがわかります．(実際には 3 本の線がありますが，最初の線と2番目の線が同じデータなので，重ねって見えません．) Fugure 2: Plot data with multiple data lines

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

隣接行列行列は数を二次元のます目上に並べたものである．これは数の表のように見える．ある規則で数を並べると，それがグラフを示すことと同じことになる．それを説明しよう．行列はグラフを表現するだけではなく，さらにいろいろなことができるのだが，ここでは特にグラフの表現をすることに集中して説明する．行列に関してもっと詳しく知りたい人には，文献 [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

Lx=d: SundayResearch (Japanese version)

Search This Blog