Aritalab:Lecture/NetworkBiology/Link Analysis

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m
 
(22 intermediate revisions by one user not shown)
Line 1: Line 1:
 +
__TOC__
 +
 
==歴史==
 
==歴史==
 +
* 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<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も定義できます。
 +
 +
: 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。
 +
 +
Betweenness は、グラフのクラスタリングによく使われます。Girvan-Newman algorithmは、betweenness の高い辺（頂点ではない）を順次ネットワークから取り除くことで、コミュニティを検出します。
 +
 +
==傑出度 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> は隣接行列の固有ベクトルにあたります。
 +
 +
==PageRank==
 +
Rank prestigeにおいて'''A'''を単なる隣接行列ではなく各頂点の次数(degree)で行方向にスケーリングした値、すなわち '''A'''<sub>ij</sub> = 1 / deg(i) としたものをPageRankと呼びます。
 +
つまり、行列'''A'''を、ウェブページを訪れるユーザがページ内のリンクを等確率でクリックして次ページに移動する遷移行列と考え、PageRankはその定常分布に相当します。
 +
 +
しかしこのままでは実用上以下の問題点が生じます。
 +
# 上記の定常分布（マルコフ過程）は、全ての状態が再帰的(recurrent)、つまり有限のステップで同じ状態に戻ってくることが可能でないと求まらない。つまり、どのページからも外に出るリンクがないとランクを付与できないページが生じる。
 +
# ページ間のネットワークが強連結(strongly connected)でないと定常分布における確率が0となる頂点が生じてしまう。
 +
# 遷移過程に周期性が存在すると、定常分布として収束しない。
 +
 +
これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定します。つまり、要素が全て1の正方行列 '''E''' を、ある割合で足しこみます。
 +
:<math>\textstyle \mathbf{P_R}=\left( (1- \alpha)\frac{1}{n}\mathbf{E}+\alpha\mathbf{A}^T\right) \mathbf{P_R}</math>
 +
 +
パラメータ&alpha;をdamping factorと呼び、実際は<math>d=0.85</math>程度が用いられます。
 +
 +
===利点と欠点===
 +
ページランクはパラメータを持たない固定値のため事前に計算しておくことが可能。スパムに対しても頑健。
 +
ただ、問い合わせの内容を一切考慮しないのは欠点ともいえます。
 +
 +
==HITS==
 +
Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズムです。オーソリティとは入力辺を多く持つページで多くのハブからリンクされます。ハブとは出力辺を多く持つページで、オーソリティにも多くリンクしています。ネットワークの隣接行列を '''L''' と書くと
 +
各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされます。
 +
 +
: '''h = La'''　(ハブの重要度はオーソリティからのリンク数で決まる)
 +
: '''a = L<sup>T</sup>h''' (オーソリティの重要度は自分を指しているハブの個数で決まる)
 +
 +
ここから
 +
:'''a = L<sup>T</sup>La, &nbsp; h = LL<sup>T</sup>h'''
 +
つまり'''a'''と'''h'''はそれぞれ '''L<sup>T</sup>L''' と '''LL<sup>T</sup>''' の固有ベクトルです。
 +
 +
HITSではクエリをもらったらまずランクの高いページを200程度集め、そのページからリンクされる、およびリンクするページを増やして初期集合を形成します。この集合から作成した引用行列 '''L''' を、単位ベクトルを初期値とした '''a''', '''h''' がそれぞれ収束するまで掛け算します。
 +
 +
;利点と欠点
 +
初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまいます。またスパムに対して弱くなります（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持ちます。
 +
 +
==共引用と書誌結合==
 +
文献計量学 (Bibliometrics) においては上記の'''L<sup>T</sup>L'''と'''LL<sup>T</sup>'''を共引用 (co-citation) および書誌結合 (bibliographic coupling) 行列と呼びます。
 +
 +
文献 ''i'' が ''j'' を引用するとき ''ij'' 成分を1、それ以外は0と定義した正方行列 '''L''' （引用行列）を考えます。文献 ''i'' と ''j'' を同時に引用する文献の数は
 +
:C<sub>ij</sub>=C<sub>ji</sub>=<math>\sum^n_{k=1}L_{ki}L_{kj}</math>
 +
これは '''L<sup>T</sup>L''' に対応し、C = '''L<sup>T</sup>L'''を共引用行列と呼びます。
  
−
==Centrality==
+
書誌結合関係とは共引用関係と対を成す概念です。文献 ''i'' と ''j'' がともに同じ文献を引用するとき、 ''i'' と ''j'' は書誌結合関係にあるといいます。文献 ''i'' と ''j'' に同時に引用される文献の数は
−
各頂点がどれくらいネットワークの中心にあるかを測る尺度を中心度(centrality)という。いずれの値も0-1の間をとるように正規化する。有向グラフと無向グラフとで数式が少し異なるが意味する内容は同じ。
+
:B<sub>ij</sub>=B<sub>ji</sub> = <math>\sum^n_{k=1}L_{ik}L_{jk}</math>
 +
これは '''LL<sup>T</sup>''' に対応し、'''B=LL<sup>T</sup>''' を書誌結合行列と呼びます。
 +
オーソリティ度は共引用行列の固有ベクトル、ハブ度は書誌結合行列の固有ベクトルに対応しています。
  
−
* Degree centrality ... リンク数が多い点を中心と考える
+
<!----
−
* Closeness centrality ... 全頂点への平均最短距離が短い点を中心と考える
+
==ウェブコミュニティ==
−
* Betweenness centrality ... 全頂点間の最短経路に多く使われる点を中心と考える
+
ハブとオーソリティの関係のように、特定のトピックについて密に関連したページ集合をコミュニティと呼ぶ。（定義はさまざまある。）
 +
いくつかの例を挙げる。
  
−
{|
+
* 二部グラフ ... 完全二部グラフを探すアルゴリズムで探索できる (HITS 1998)
−
|-
+
* 最大流　... 最大流アルゴリズムを用いてボトルネックを探し、ネットワークを切断してゆくことで探索できる (Flake et al. IEEE Computer 35(3) 2002)
−
! Name || Undirected || Directed
+
* 辺媒介度 ... betweennessが大きい辺から順番に除いていく
−
|-
+
* Newmanクラスタリング ... 任意の頂点ペアについて一定の評価関数値を満たす場合はマージしてゆく
−
|Degree || <math>C_D(i)=\frac{d(i)}{n-1}</math> || <math>C_D(i)=\frac{d_{out}(i)}{n-1}</math>
+
−
|-
+
−
|colspan="3"|<small>
+
−
</small>
+
−
|-
+
−
|Closeness
+
−
|colspan="2"| <math>C_C(i)=\frac{n-1}{\sigma^n_{j=1}d(i,j)}</math>
+
−
|-
+
−
|colspan="3"|<small>
+
−
</small>
+
−
|-
+
−
|Betweenness
+
−
| <math>C_B(i)=\sigma_{j<k}\frac{p_{jk}(i)}{p_{jk}} \times N_{paths}^{-1}</math>
+
−
|-
+
−
|
+
−
|colspan="2"|<small>
+
−
ただしj,kはiと異なる頂点。iを除いた最短経路の本数は無向で<math>\frac{(n-1)(n-2)}{2}</math>、有向で<math>(n-1)(n-2)</math>。
+
−
</small>
+
−
|}
+
  
−
==Prestige==
+
いずれもコミュニティの定義がはっきりしないので適当な時点でイテレーションを停止するしかない。
 +
--->

Latest revision as of 09:02, 2 August 2017

Contents


[edit] 歴史

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

[edit] 中心度 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) / \sum^n_{j=1} p(i,j)
媒介中心度 Betweenness centrality

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

CB( 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 の高い辺（頂点ではない）を順次ネットワークから取り除くことで、コミュニティを検出します。

[edit] 傑出度 Prestige

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

次数傑出度 Degree prestige

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

PD( i ) = degin ( i ) / (n -1)
近接傑出度 Proximity prestige

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

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

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

ランク傑出度 Rank prestige

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

PR = AT PR

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

[edit] PageRank

Rank prestigeにおいてAを単なる隣接行列ではなく各頂点の次数(degree)で行方向にスケーリングした値、すなわち Aij = 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程度が用いられます。

[edit] 利点と欠点

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

[edit] HITS

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

h = La　(ハブの重要度はオーソリティからのリンク数で決まる)
a = LTh (オーソリティの重要度は自分を指しているハブの個数で決まる)

ここから

a = LTLa,   h = LLTh

つまりaとhはそれぞれ LTL と LLT の固有ベクトルです。

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

利点と欠点

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

[edit] 共引用と書誌結合

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

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

Cij=Cji=\sum^n_{k=1}L_{ki}L_{kj}

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

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

Bij=Bji = \sum^n_{k=1}L_{ik}L_{jk}

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


Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/NetworkBiology/Link_Analysis&oldid=315348"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox