Aritalab:Lecture/NetworkBiology/Link Analysis - Revision history

Adm at 00:02, 2 August 2017

2017-08-02T00:02:25Z

Adm: /* ネットワークの指標 */

2016-08-06T02:43:25Z

‎ネットワークの指標

Adm at 03:01, 3 August 2016

2016-08-03T03:01:14Z

Adm: /* PageRank */

2015-08-27T04:00:31Z

‎PageRank

Adm: /* HITS */

2011-05-12T00:33:46Z

‎HITS

Adm at 00:31, 12 May 2011

2011-05-12T00:31:15Z

Adm at 22:03, 11 May 2011

2011-05-11T22:03:29Z

Show changes

Adm at 00:50, 10 June 2010

2010-06-10T00:50:08Z

Adm: Draft:Link Analysis moved to Aritalab:Lecture/NetworkBiology/Link Analysis

2010-06-02T04:50:44Z

Draft:Link Analysis moved to Aritalab:Lecture/NetworkBiology/Link Analysis

Adm at 04:50, 2 June 2010

2010-06-02T04:50:27Z

@@ Line 1: / Line 1: @@
-{{Lecture/Header}}
+__TOC__
-−
-{| style="float:right"
-| __TOC__
-|}
 ==歴史==

@@ Line 9: / Line 9: @@
 * 1998 Apr: S. Brin, L. PageがPageRankを発表(7th WWW)
-==ネットワークの指標==
+==中心度 Centrality==
-===中心度 Centrality===
 無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality) といいます。ここでは記号 C であらわします。複数知られていますが、いずれの値も 0-1 の間をとるようにスケーリングします。有向グラフには次に述べる prestige を使います。
 ;次数中心度 Degree centrality
-辺数が多い点を中心と考えます。ここでは頂点 ''i'' の次数を ''deg'' ( ''i'' ) と書きます。
+辺数が多い点を中心と考えます。ここでは頂点 ''i'' の次数を deg( ''i'' ) と書きます。
-: C<sub>D</sub>( ''i'' )= ''deg'' ( ''i'' ) / (''n'' -1)
+: C<sub>D</sub>( ''i'' )= deg( ''i'' ) / (''n'' -1)
 ;近接中心度 Closeness centrality
@@ Line 23: / Line 22: @@
 ;媒介中心度 Betweenness centrality
-全頂点間の最短経路に多く使われる点を中心と考えます。ここでは頂点 ''j'' から ''k'' への最短経路の本数を ''p <sub>jk</sub>''、その中で ''i'' を通るものを ''p <sub>jk</sub>''( ''i'' ) と書きます。同じように、辺のbetweennessも定義できます。
+全頂点間の最短経路に多く使われる点を中心と考えます。ここでは頂点 ''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>
@@ Line 30: / Line 29: @@
 Betweenness は、グラフのクラスタリングによく使われます。Girvan-Newman algorithmは、betweenness の高い辺（頂点ではない）を順次ネットワークから取り除くことで、コミュニティを検出します。
-===傑出度 Prestige===
+==傑出度 Prestige==
 中心度と同じ概念を、有向グラフでは傑出度(prestige)といいます。
@@ Line 37: / Line 36: @@
 多くの入力辺がある点を傑出していると考えます。
-: P<sub>D</sub>( ''i'' ) = ''deg'' <sub>in</sub> ( ''i'' ) / (''n'' -1)
+: P<sub>D</sub>( ''i'' ) = deg<sub>in</sub> ( ''i'' ) / (''n'' -1)
 ; 近接傑出度 Proximity prestige
@@ Line 51: / Line 50: @@
 : P<sub>R</sub> = A<sup>T</sup> P<sub>R</sub>
-ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は A の固有ベクトルにあたります。
+ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は隣接行列の固有ベクトルにあたります。
 ==PageRank==

@@ Line 1: / Line 1: @@
 {{Lecture/Header}}
 ==歴史==
@@ Line 23: / Line 27: @@
 : 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===
@@ Line 45: / Line 51: @@
 : P<sub>R</sub> = A<sup>T</sup> P<sub>R</sub>
-ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は A の固有値にあたります。
+ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は A の固有ベクトルにあたります。
 ==PageRank==
@@ Line 74: / Line 80: @@
 ここから
 :'''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''' がそれぞれ収束するまで掛け算します。
@@ Line 91: / Line 97: @@
 :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>''' を書誌結合行列と呼びます。
-オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応しています。
+オーソリティ度は共引用行列の固有ベクトル、ハブ度は書誌結合行列の固有ベクトルに対応しています。
 <!----

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

@@ Line 69: / Line 69: @@
 各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされます。
-: ハブの重要度はオーソリティからのリンク数で決まる '''h = La'''
+: '''h = La'''　(ハブの重要度はオーソリティからのリンク数で決まる)
-: オーソリティの重要度は自分を指しているハブの個数で決まる　'''a = L<sup>T</sup>h'''
+: '''a = L<sup>T</sup>h''' (オーソリティの重要度は自分を指しているハブの個数で決まる)
 ここから

@@ Line 6: / Line 6: @@
 ==ネットワークの指標==
-===中心度 (Centrality)===
+===中心度 Centrality===
 無向グラフにおいて、頂点のネットワーク中心への近さを示す尺度を中心度(centrality) といいます。ここでは記号 C であらわします。複数知られていますが、いずれの値も 0-1 の間をとるようにスケーリングします。有向グラフには次に述べる prestige を使います。
@@ Line 43: / Line 43: @@
 ; ランク傑出度 Rank prestige
 高いランクの頂点に指されている頂点もランクが高いと考えます。
-: P<sub>R</sub> = A<sup>T</sup>P<sub>R</sub>
+: P<sub>R</sub> = A<sup>T</sup> P<sub>R</sub>
 ただしP<sub>R</sub>は長さ ''n'' の縦ベクトル、 A は隣接行列です。つまり P<sub>R</sub> は A の固有値にあたります。
@@ Line 57: / Line 57: @@
 これらの問題点を回避するため、ユーザはリンク先の無いページからは他の全ページに等確率で移動し、リンク先を持つページからも一定確率でランダムに他ページに移動すると仮定します。つまり、要素が全て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{1}{n}\mathbf{E}+\alpha\mathbf{A}^T\right) \mathbf{P_R}</math>
 パラメータ&alpha;をdamping factorと呼び、実際は<math>d=0.85</math>程度が用いられます。
@@ Line 66: / Line 66: @@
 ==HITS==
-Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズムです。
+Hypertext Induced Topic Search(HITS)はオーソリティおよびハブと呼ばれる二種の頂点集合からなる二部グラフを求めるアルゴリズムです。オーソリティとは入力辺を多く持つページで多くのハブからリンクされます。ハブとは出力辺を多く持つページで、オーソリティにも多くリンクしています。ネットワークの隣接行列を '''L''' と書くと
-オーソリティとは入力辺を多く持つページで多くのハブからリンクされます。
-ハブとは出力辺を多く持つページで多くのオーソリティへリンクします。
 各頂点におけるオーソリティとハブの次数をあらわす縦ベクトルはそれぞれ以下であらわされます。
-:'''a = L<sup>T</sup>h, &nbsp; h = La'''
-すなわち
+: ハブの重要度はオーソリティからのリンク数で決まる '''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>''' の固有値です。
@@ Line 77: / Line 78: @@
 HITSではクエリをもらったらまずランクの高いページを200程度集め、そのページからリンクされる、およびリンクするページを増やして初期集合を形成します。この集合から作成した引用行列 '''L''' を、単位ベクトルを初期値とした '''a''', '''h''' がそれぞれ収束するまで掛け算します。
-===利点と欠点===
+;利点と欠点
 初期集合を形成する際に、余計なページを含むことで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) 行列と呼びます。
-文献''i''が''j''を引用するとき''ij''成分を1、それ以外は0と定義した正方行列'''L'''（引用行列）を考えたとき、文献''i''と''j''を同時に引用する文献の数は
+文献 ''i'' が ''j'' を引用するとき ''ij'' 成分を1、それ以外は0と定義した正方行列 '''L''' （引用行列）を考えます。文献 ''i'' と ''j'' を同時に引用する文献の数は
-:<math>\textstyle C_{ij}=C_{ji}=\sum^n_{k=1}L_{ki}L_{kj}</math>
+: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'''を共引用行列と呼ぶ。
+これは '''L<sup>T</sup>L''' に対応し、C = '''L<sup>T</sup>L'''を共引用行列と呼びます。
-書誌結合関係とは共引用関係と対を成す概念である。文献''i''と''j''がともに同じ文献を引用するとき、''i''と''j''は書誌結合関係にあるという。文献''i''と''j''に同時に引用される文献の数は
+書誌結合関係とは共引用関係と対を成す概念です。文献 ''i'' と ''j'' がともに同じ文献を引用するとき、 ''i'' と ''j'' は書誌結合関係にあるといいます。文献 ''i'' と ''j'' に同時に引用される文献の数は
-:<math>\textstyle B_{ij}=B_{ji}=\sum^n_{k=1}L_{ik}L_{jk}</math>
+: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>'''を書誌結合行列と呼ぶ。
+これは '''LL<sup>T</sup>''' に対応し、'''B=LL<sup>T</sup>''' を書誌結合行列と呼びます。
-オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応する。
+オーソリティ度は共引用行列の固有値、ハブ度は書誌結合行列の固有値に対応しています。
 <!----

← Older revision		Revision as of 00:50, 10 June 2010
Line 1:		Line 1:
		+	{{Lecture/Header}}
		+
	==歴史==		==歴史==
	* 1998 Jan: J. KleinbergがHITSアルゴリズムを発表(9th ACM-SIAM DA)		* 1998 Jan: J. KleinbergがHITSアルゴリズムを発表(9th ACM-SIAM DA)

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