Aritalab:Lecture/NetworkBiology/Link Analysis

Revision as of 07:03, 12 May 2011

歴史

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。

傑出度 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^TP_R

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

PageRank

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

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

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

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

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

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

利点と欠点

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

HITS

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

a = L^Th, h = La

すなわち

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を同時に引用する文献の数は

$\textstyle C_{ij}=C_{ji}=\sum^n_{k=1}L_{ki}L_{kj}$

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

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

$\textstyle B_{ij}=B_{ji}=\sum^n_{k=1}L_{ik}L_{jk}$

これはLL^Tに対応し、B=LL^Tを書誌結合行列と呼ぶ。オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応する。

@@ Line 5: / Line 5: @@
 * 1998 Apr: S. Brin, L. PageがPageRankを発表(7th WWW)
-==Centrality==
+==ネットワークの指標==
-無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality)という。いずれの値も0-1の間をとるようにスケーリングする。有向グラフには次に述べるprestigeを使った方がよい。
+===中心度 (Centrality)===
+無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality) といいます。ここでは記号 C であらわします。複数知られていますが、いずれの値も 0-1 の間をとるようにスケーリングします。有向グラフには次に述べる prestige を使います。
-* Degree centrality (次数中心度)... 辺数が多い点を中心と考える。ここでは頂点<math>i</math>の次数を<math>deg(i)</math>と書く。
+;次数中心度 Degree centrality
-: <math>\textstyle C_D(i)=\frac{deg(i)}{n-1}</math>
+辺数が多い点を中心と考えます。ここでは頂点 ''i'' の次数を ''deg'' ( ''i'' ) と書きます。
-* Closeness centrality (近接中心度)... 全頂点への平均最短距離が短い点を中心と考える。ここでは頂点<math>i</math>から<math>j</math>への最短ステップ数を<math>dist(i,j)</math>と書く。
+: C<sub>D</sub>( ''i'' )= ''deg'' ( ''i'' ) / (''n'' -1)
-: <math>\textstyle C_C(i)=\frac{n-1}{\sum^n_{j=1}dist(i,j)}</math>
+;近接中心度 Closeness centrality
-* Betweenness centrality (媒介中心度)... 全頂点間の最短経路に多く使われる点を中心と考える。ここでは頂点<math>i</math>から<math>j</math>への最短経路の本数を<math>p_{jk}</math>、その中で<math>i</math>を通るものを<math>p_{jk}(i)</math>と書く。同じ値で辺のbetweennessを定義してもよい。
+全頂点への平均最短距離が短い点を中心と考えます。ここでは頂点 ''i'' から ''j'' への最短ステップ数を ''p'' ( ''i'' , ''j'' ) と書きます。
-: <math>\textstyle C_B(i)=\sum_{j<k, j\neq i, k\neq i}\frac{p_{jk}(i)}{p_{jk}} \times N_{paths}^{-1}</math>
-:ただし<math>N_{path}</math>は<math>i</math>を除いたネットワーク中の最短経路<math>p</math>の本数で<math>(n-1)(n-2)/2</math>。
-==Prestige==
+: C<sub>C</sub>( ''i'' ) = (''n'' -1) / <math>\sum^n_{j=1} p(i,j)</math>
-有向グラフにおいて頂点の傑出具合を測る尺度を傑出度(prestige)という。
-* Degree prestige (次数傑出度)... 多くの入力辺がある点を傑出していると考える。
+;媒介中心度 Betweenness centrality
-: <math>\textstyle P_D(i)=\frac{deg_{in}(i)}{n-1}</math>
+全頂点間の最短経路に多く使われる点を中心と考えます。ここでは頂点 ''j'' から ''k'' への最短経路の本数を ''p <sub>jk</sub>''、その中で ''i'' を通るものを ''p <sub>jk</sub>''( ''i'' ) と書きます。同じように、辺のbetweennessも定義できます。
-* Proximity prestige (近接傑出度)... より多くの頂点から到達できる点を傑出していると考える。Degree prestigeの拡張になっている。
-: <math>\textstyle P_P(i)=\frac{|I_i|/(n-1)}{\sum_{j\in I_i}dist(j,i)/|I_i|}</math>
+: C<sub>B</sub>( ''i'' )= <math>\sum_{j<k, j\neq i, k\neq i}\frac{p_{jk}(i)}{p_{jk}} \times N_{paths}^{-1}</math>
-: ただし><math>I_i</math>は<math>i</math>より到達できる頂点集合。
+:ただし<math>N_{path}</math>は ''i'' を除いたネットワーク中の最短経路 ''p'' の本数で (''n'' -1)(''n'' -2)/2。
-* Rank prestige (ランク傑出度)... 高いランクの頂点に指されている頂点もランクが高いと考える。
-: <big>'''P<sub>R</sub>=A<sup>T</sup>P<sub>R</sub>'''</big>
+===傑出度 Prestige===
-: ただし'''P<sub>R</sub>'''は長さ<math>n</math>の縦ベクトル、'''A'''は隣接行列。つまり'''P<sub>R</sub>'''は'''A'''の固有値にあたる。
+中心度と同じ概念を、有向グラフでは傑出度(prestige)といいます。
+; 次数傑出度 Degree prestige
+多くの入力辺がある点を傑出していると考えます。
+: P<sub>D</sub>( ''i'' ) = ''deg'' <sub>in</sub> ( ''i'' ) / (''n'' -1)
+; 近接傑出度 Proximity prestige
+より多くの頂点に短い距離で到達できる点を傑出していると考えます。ここでは頂点 ''i'' から到達可能な頂点の集合を <math>I_i</math> と書きます。
+: P<sub>P</sub>( ''i'' ) = <math>\frac{|I_i|}{(n-1)} \times \frac{1}{\sum_{j\in I_i}p(j,i)/|I_i|}</math>
+後半の式はスケーリングに相当し、各頂点への平均距離の逆数をかけています。
+次数傑出度の拡張になっています。
+; ランク傑出度 Rank prestige
+高いランクの頂点に指されている頂点もランクが高いと考えます。
+: P<sub>R</sub> = A<sup>T</sup>P<sub>R</sub>
+ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は A の固有値にあたります。
 ==PageRank==
-Rank prestigeにおいて'''A'''を単なる隣接行列ではなく各頂点の次数(degree)で行方向にスケーリングした値、すなわち<math>\textstyle A_{ij}=\frac{1}{deg(i)}</math>としたものをPageRankと呼ぶ。
+Rank prestigeにおいて'''A'''を単なる隣接行列ではなく各頂点の次数(degree)で行方向にスケーリングした値、すなわち<math>\textstyle A_{ij}=\frac{1}{deg(i)}</math>としたものをPageRankと呼びます。
-つまり、行列'''A'''を、ウェブページを訪れるユーザがページ内のリンクを等確率でクリックして次ページに移動するマルコフ過程の遷移行列と考え、PageRankはその定常分布に相当する。
+つまり、行列'''A'''を、ウェブページを訪れるユーザがページ内のリンクを等確率でクリックして次ページに移動する遷移行列と考え、PageRankはその定常分布に相当します。
-しかしこのままでは実用上以下の問題点がある。
+しかしこのままでは実用上以下の問題点が生じます。
-# マルコフ過程の定常分布は、全ての状態が再帰的(recurrent)、つまり有限のステップで同じ状態に戻ってくることが可能でないと求まらない。つまり、どのページからも外に出るリンクがないとランクを付与できないページが生じる。
+# 上記の定常分布（マルコフ過程）は、全ての状態が再帰的(recurrent)、つまり有限のステップで同じ状態に戻ってくることが可能でないと求まらない。つまり、どのページからも外に出るリンクがないとランクを付与できないページが生じる。
 # ページ間のネットワークが強連結(strongly connected)でないと定常分布における確率が0となる頂点が生じてしまう。
 # 遷移過程に周期性が存在すると、定常分布として収束しない。
-これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定する。
+これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定します。つまり、要素が全て1の正方行列 '''E''' を、ある割合で足しこみます。
 :<math>\textstyle \mathbf{P_R}=\left( (1-\alpha)\frac{\mathbf{E}}{n}+\alpha\mathbf{A}^T\right) \mathbf{P_R}</math>
-: 行列'''E'''は要素が全て1の正方行列。
-パラメータ&alpha;をdamping factorと呼び、<math>d=0.85</math>程度が用いられる。
+パラメータ&alpha;をdamping factorと呼び、実際は<math>d=0.85</math>程度が用いられます。
 ===利点と欠点===
 ページランクはパラメータを持たない固定値のため事前に計算しておくことが可能。スパムに対しても頑健。
-ただ、問い合わせの内容を一切考慮しないのは欠点ともいえる。
+ただ、問い合わせの内容を一切考慮しないのは欠点ともいえます。
 ==HITS==
-Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズム。
+Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズムです。
-オーソリティとは入力辺を多く持つページで多くのハブからリンクされる。
+オーソリティとは入力辺を多く持つページで多くのハブからリンクされます。
-ハブとは出力辺を多く持つページで多くのオーソリティへリンクする。
+ハブとは出力辺を多く持つページで多くのオーソリティへリンクします。
-各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされる。
+各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされます。
 :'''a = L<sup>T</sup>h, &nbsp; h = La'''
 すなわち
 :'''a = L<sup>T</sup>La, &nbsp; h = LL<sup>T</sup>h'''
-つまり'''a'''と'''h'''はそれぞれ'''L<sup>T</sup>L'''と'''LL<sup>T</sup>'''の固有値。
+つまり'''a'''と'''h'''はそれぞれ '''L<sup>T</sup>L''' と '''LL<sup>T</sup>''' の固有値です。
-HITSではクエリをもらったらまずランクの高いページを200程度集め、そのページからリンクされる、およびリンクするページを増やして初期集合を形成する。この集合から作成した引用行列'''L'''を、単位ベクトルを初期値としたた'''a''', '''h'''がそれぞれ収束するまで掛け算する。
+HITSではクエリをもらったらまずランクの高いページを200程度集め、そのページからリンクされる、およびリンクするページを増やして初期集合を形成します。この集合から作成した引用行列 '''L''' を、単位ベクトルを初期値とした '''a''', '''h''' がそれぞれ収束するまで掛け算します。
 ===利点と欠点===
-初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまう。またスパムに対して弱い（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持つ。
+初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまいます。またスパムに対して弱くなります（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持ちます。
 ==共引用と書誌結合==
@@ Line 73: / Line 92: @@
 オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応する。
+<!----
 ==ウェブコミュニティ==
 ハブとオーソリティの関係のように、特定のトピックについて密に関連したページ集合をコミュニティと呼ぶ。（定義はさまざまある。）
@@ Line 83: / Line 103: @@
 いずれもコミュニティの定義がはっきりしないので適当な時点でイテレーションを停止するしかない。
+--->

Aritalab:Lecture/NetworkBiology/Link Analysis

Revision as of 07:03, 12 May 2011

Contents

歴史

ネットワークの指標

中心度 (Centrality)

傑出度 Prestige

PageRank

利点と欠点

HITS

利点と欠点

共引用と書誌結合

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox