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