Aritalab:Lecture/NetworkBiology/Link Analysis

歴史

• 1998 Jan: J. KleinbergがHITSアルゴリズムを発表(9th ACM-SIAM DA)
• 1998 Apr: S. Brin, L. PageがPageRankを発表(7th WWW)

中心度 Centrality

無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality) といいます。ここでは記号 C であらわします。複数知られていますが、いずれの値も 0-1 の間をとるようにスケーリングします。有向グラフには次に述べる prestige を使います。

次数中心度 Degree centrality

辺数が多い点を中心と考えます。ここでは頂点 i の次数を deg( i ) と書きます。

C_D( i )= deg( i ) / (n -1)

近接中心度 Closeness centrality

全頂点への平均最短距離が短い点を中心と考えます。ここでは頂点 i から j への最短ステップ数を p ( i , j ) と書きます。

C_C( i ) = (n -1) / $\sum^n_{j=1} p(i,j)$

媒介中心度 Betweenness centrality

全頂点間の最短経路に多く使われる点を中心と考えます。ここでは頂点 j から k への最短経路の本数を p _jk、その中で i を通るものを p _jk( i ) と書きます。同じように、辺のbetweennessも定義できます。

C_B( i )= $\sum_{j<k, j\neq i, k\neq i}\frac{p_{jk}(i)}{p_{jk}} \times N_{paths}^{-1}$

ただし$N_{path}$は i を除いたネットワーク中の最短経路 p の本数で (n -1)(n -2)/2。

Betweenness は、グラフのクラスタリングによく使われます。Girvan-Newman algorithmは、betweenness の高い辺（頂点ではない）を順次ネットワークから取り除くことで、コミュニティを検出します。

傑出度 Prestige

中心度と同じ概念を、有向グラフでは傑出度(prestige)といいます。

次数傑出度 Degree prestige

多くの入力辺がある点を傑出していると考えます。

P_D( i ) = deg_in ( i ) / (n -1)

近接傑出度 Proximity prestige

より多くの頂点に短い距離で到達できる点を傑出していると考えます。ここでは頂点 i から到達可能な頂点の集合を $I_i$ と書きます。

P_P( i ) = $\frac{|I_i|}{(n-1)} \times \frac{1}{\sum_{j\in I_i}p(j,i)/|I_i|}$

後半の式はスケーリングに相当し、各頂点への平均距離の逆数をかけています。 次数傑出度の拡張になっています。

ランク傑出度 Rank prestige

高いランクの頂点に指されている頂点もランクが高いと考えます。

P_R = A^T P_R

ただしP_Rは長さ n の縦ベクトル、 A は隣接行列です。つまり P_R は隣接行列の固有ベクトルにあたります。

PageRank

Rank prestigeにおいてAを単なる隣接行列ではなく各頂点の次数(degree)で行方向にスケーリングした値、すなわち A_ij = 1 / deg(i) としたものをPageRankと呼びます。 つまり、行列Aを、ウェブページを訪れるユーザがページ内のリンクを等確率でクリックして次ページに移動する遷移行列と考え、PageRankはその定常分布に相当します。

しかしこのままでは実用上以下の問題点が生じます。

1. 上記の定常分布（マルコフ過程）は、全ての状態が再帰的(recurrent)、つまり有限のステップで同じ状態に戻ってくることが可能でないと求まらない。つまり、どのページからも外に出るリンクがないとランクを付与できないページが生じる。
2. ページ間のネットワークが強連結(strongly connected)でないと定常分布における確率が0となる頂点が生じてしまう。
3. 遷移過程に周期性が存在すると、定常分布として収束しない。

これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定します。つまり、要素が全て1の正方行列 E を、ある割合で足しこみます。

$\textstyle \mathbf{P_R}=\left( (1- \alpha)\frac{1}{n}\mathbf{E}+\alpha\mathbf{A}^T\right) \mathbf{P_R}$

パラメータαをdamping factorと呼び、実際は$d=0.85$程度が用いられます。

利点と欠点

ページランクはパラメータを持たない固定値のため事前に計算しておくことが可能。スパムに対しても頑健。 ただ、問い合わせの内容を一切考慮しないのは欠点ともいえます。

HITS

Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズムです。オーソリティとは入力辺を多く持つページで多くのハブからリンクされます。ハブとは出力辺を多く持つページで、オーソリティにも多くリンクしています。ネットワークの隣接行列を L と書くと 各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされます。

h = La　(ハブの重要度はオーソリティからのリンク数で決まる)

a = L^Th (オーソリティの重要度は自分を指しているハブの個数で決まる)

ここから

a = L^TLa,   h = LL^Th

つまりaとhはそれぞれ L^TL と LL^T の固有ベクトルです。

HITSではクエリをもらったらまずランクの高いページを200程度集め、そのページからリンクされる、およびリンクするページを増やして初期集合を形成します。この集合から作成した引用行列 L を、単位ベクトルを初期値とした a, h がそれぞれ収束するまで掛け算します。

利点と欠点

初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまいます。またスパムに対して弱くなります（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持ちます。

共引用と書誌結合

文献計量学 (Bibliometrics) においては上記のL^TLとLL^Tを共引用 (co-citation) および書誌結合 (bibliographic coupling) 行列と呼びます。

文献 i が j を引用するとき ij 成分を1、それ以外は0と定義した正方行列 L （引用行列）を考えます。文献 i と j を同時に引用する文献の数は

C_ij=C_ji=$\sum^n_{k=1}L_{ki}L_{kj}$

これは L^TL に対応し、C = L^TLを共引用行列と呼びます。

書誌結合関係とは共引用関係と対を成す概念です。文献 i と j がともに同じ文献を引用するとき、 i と j は書誌結合関係にあるといいます。文献 i と j に同時に引用される文献の数は

B_ij=B_ji = $\sum^n_{k=1}L_{ik}L_{jk}$

これは LL^T に対応し、B=LL^T を書誌結合行列と呼びます。 オーソリティ度は共引用行列の固有ベクトル、ハブ度は書誌結合行列の固有ベクトルに対応しています。