Aritalab:Lecture/NetworkBiology/Link Analysis

From Metabolomics.JP
< Aritalab:Lecture | NetworkBiology(Difference between revisions)
Jump to: navigation, search
m
Line 1: Line 1:
−
=歴史=
+
==歴史==
 
* 1998 Jan: J. KleinbergがHITSアルゴリズムを発表(9th ACM-SIAM DA)
 
* 1998 Jan: J. KleinbergがHITSアルゴリズムを発表(9th ACM-SIAM DA)
 
* 1998 Apr: S. Brin, L. PageがPageRankを発表(7th WWW)
 
* 1998 Apr: S. Brin, L. PageがPageRankを発表(7th WWW)
  
−
=Centrality=
+
==Centrality==
 
無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality)という。いずれの値も0-1の間をとるようにスケーリングする。有向グラフには次に述べるprestigeを使った方がよい。
 
無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality)という。いずれの値も0-1の間をとるようにスケーリングする。有向グラフには次に述べるprestigeを使った方がよい。
  
Line 15: Line 15:
 
:ただし<math>N_{path}</math>は<math>i</math>を除いたネットワーク中の最短経路<math>p</math>の本数で<math>(n-1)(n-2)/2</math>。
 
:ただし<math>N_{path}</math>は<math>i</math>を除いたネットワーク中の最短経路<math>p</math>の本数で<math>(n-1)(n-2)/2</math>。
  
−
=Prestige=
+
==Prestige==
 
有向グラフにおいて頂点の傑出具合を測る尺度を傑出度(prestige)という。
 
有向グラフにおいて頂点の傑出具合を測る尺度を傑出度(prestige)という。
 
* Degree prestige (次数傑出度)... 多くの入力辺がある点を傑出していると考える。
 
* Degree prestige (次数傑出度)... 多くの入力辺がある点を傑出していると考える。
Line 26: Line 26:
 
: ただし'''P<sub>R</sub>'''は長さ<math>n</math>の縦ベクトル、'''A'''は隣接行列。つまり'''P<sub>R</sub>'''は'''A'''の固有値にあたる。
 
: ただし'''P<sub>R</sub>'''は長さ<math>n</math>の縦ベクトル、'''A'''は隣接行列。つまり'''P<sub>R</sub>'''は'''A'''の固有値にあたる。
  
−
=PageRank=
+
==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はその定常分布に相当する。
Line 44: Line 44:
 
ただ、問い合わせの内容を一切考慮しないのは欠点ともいえる。
 
ただ、問い合わせの内容を一切考慮しないのは欠点ともいえる。
  
−
=HITS=
+
==HITS==
 
Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズム。
 
Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズム。
 
オーソリティとは入力辺を多く持つページで多くのハブからリンクされる。
 
オーソリティとは入力辺を多く持つページで多くのハブからリンクされる。
Line 59: Line 59:
 
初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまう。またスパムに対して弱い（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持つ。
 
初期集合を形成する際に、余計なページを含むことでTopic driftとよばれるテーマの移動が起こってしまう。またスパムに対して弱い（ハブを簡単に偽装できる）。そのかわり、与えられたキーワードについて関連する重要ページを発見できる利点を持つ。
  
−
=共引用と書誌結合=
+
==共引用と書誌結合==
 
文献計量学 (Bibliometrics) においては上記の'''L<sup>T</sup>L'''と'''LL<sup>T</sup>'''を共引用 (co-citation) および書誌結合 (bibliographic coupling) 行列と呼ぶ。
 
文献計量学 (Bibliometrics) においては上記の'''L<sup>T</sup>L'''と'''LL<sup>T</sup>'''を共引用 (co-citation) および書誌結合 (bibliographic coupling) 行列と呼ぶ。
  
Line 71: Line 71:
 
オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応する。
 
オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応する。
  
−
=ウェブコミュニティ=
+
==ウェブコミュニティ==
 
ハブとオーソリティの関係のように、特定のトピックについて密に関連したページ集合をコミュニティと呼ぶ。（定義はさまざまある。）
 
ハブとオーソリティの関係のように、特定のトピックについて密に関連したページ集合をコミュニティと呼ぶ。（定義はさまざまある。）
 
いくつかの例を挙げる。
 
いくつかの例を挙げる。

Revision as of 13:50, 2 June 2010

Contents

歴史

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

Centrality

無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality)という。いずれの値も0-1の間をとるようにスケーリングする。有向グラフには次に述べるprestigeを使った方がよい。

  • Degree centrality (次数中心度)... 辺数が多い点を中心と考える。ここでは頂点iの次数をdeg(i)と書く。
\textstyle C_D(i)=\frac{deg(i)}{n-1}
  • Closeness centrality (近接中心度)... 全頂点への平均最短距離が短い点を中心と考える。ここでは頂点iからjへの最短ステップ数をdist(i,j)と書く。
\textstyle C_C(i)=\frac{n-1}{\sum^n_{j=1}dist(i,j)}
  • Betweenness centrality (媒介中心度)... 全頂点間の最短経路に多く使われる点を中心と考える。ここでは頂点iからjへの最短経路の本数をp_{jk}、その中でiを通るものをp_{jk}(i)と書く。同じ値で辺のbetweennessを定義してもよい。
\textstyle 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 (次数傑出度)... 多くの入力辺がある点を傑出していると考える。
\textstyle P_D(i)=\frac{deg_{in}(i)}{n-1}
  • Proximity prestige (近接傑出度)... より多くの頂点から到達できる点を傑出していると考える。Degree prestigeの拡張になっている。
\textstyle P_P(i)=\frac{|I_i|/(n-1)}{\sum_{j\in I_i}dist(j,i)/|I_i|}
ただし>I_iはiより到達できる頂点集合。
  • Rank prestige (ランク傑出度)... 高いランクの頂点に指されている頂点もランクが高いと考える。
PR=ATPR
ただしPRは長さnの縦ベクトル、Aは隣接行列。つまりPRはAの固有値にあたる。

PageRank

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

しかしこのままでは実用上以下の問題点がある。

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

これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定する。

\textstyle \mathbf{P_R}=\left( (1-\alpha)\frac{\mathbf{E}}{n}+\alpha\mathbf{A}^T\right) \mathbf{P_R}
行列Eは要素が全て1の正方行列。

パラメータαをdamping factorと呼び、d=0.85程度が用いられる。

利点と欠点

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

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

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

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

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

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

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

ウェブコミュニティ

ハブとオーソリティの関係のように、特定のトピックについて密に関連したページ集合をコミュニティと呼ぶ。（定義はさまざまある。） いくつかの例を挙げる。

  • 二部グラフ ... 完全二部グラフを探すアルゴリズムで探索できる (HITS 1998)
  • 最大流　... 最大流アルゴリズムを用いてボトルネックを探し、ネットワークを切断してゆくことで探索できる (Flake et al. IEEE Computer 35(3) 2002)
  • 辺媒介度 ... betweennessが大きい辺から順番に除いていく
  • Newmanクラスタリング ... 任意の頂点ペアについて一定の評価関数値を満たす場合はマージしてゆく

いずれもコミュニティの定義がはっきりしないので適当な時点でイテレーションを停止するしかない。

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

Variants
Actions
Navigation
metabolites
Toolbox