Download presentation
Presentation is loading. Please wait.
1
The Web as a graph 末次 寛之 清水 伸明
2
目標 wwwのリンク構造をグラフ化し， HIT，Hab ＆ Authority，PageRank等の アルゴリズムを利用して，解析する
3
Hubs＆Authorities Hubs Authorities
4
Hubs＆authorities Hubs Authorities
5
The HITS algorithm 1 a sampling step 探したいクエリに対して関係すると思われるwebページを約２００探す
その２００のページからリンクを何度かたどり１０００～３０００のページを集める
6
The HITS algorithm 2 a weight-propagation step
sampling stepで集めたサイトを隣接行列にしhubやAuthorityにweightをつけていく hubやAuthorityを見つける
7
Hubs＆Authorities 高い 高い Hubs weight Authorities weight 低い 低い
8
Updated of hubs and authority
Non-negative authority weight : Xp Non-negative hub weight :Yp (each page p∈V) Xp = Σ Yq ←authority weight increased Yp = Σ Xq ← hub weight increased q→p q→p
9
Update hubs and authority
A : adjacency matrix (隣接行列) x = (x1,x2,…,xN) y = (y1,y2,…,yN) x = A y ←update rule y = Ax ←update rule x ← A y← A Ax = (A A)x y ← Ax← AA y = (AA )y T T T T T T
10
Hubs ＆ Authorities adjacency matrix （隣接行列） A １ ０ １ １ ０ ２ ０ ０ １ １
１ ０ １ １ ０ ２ ０ ０ １ １ ３ ０ ０ ０ １ ４ ０ ０ ０ ０ adjacency matrix （隣接行列） 1 3 A ＝ 2 4
11
Hubs ＆ Authorities Hub authority Weight weight １ ２ ０ １ １ ０ １
１ ２ ０ １ １ ０ １ ２ ２ ０ ０ １ １ １ ３ １ ０ ０ ０ １ １ ４ ０ ０ ０ ０ ０ １ Hub authority Weight weight 1 3 ＝ 2 4
12
Hubs ＆ Authorities A authority Hub ＝ 1 3 2 4 ＝ １ ０ ０ ０ ０ ０ ２
１ ０ ０ ０ ０ ０ ２ ２ ２ １ ０ ０ ０ ２ ３ ４ １ １ ０ ０ １ ４ ３ ０ １ １ ０ ０ authority Hub weight weight １ ０ ０ ０ ０ ２ １ ０ ０ ０ ３ １ １ ０ ０ ４ ０ １ １ ０ ＝ 1 3 T 2 4 A ＝
13
Authorities weight ０ ０ ０ ０ ０ １ １ ０ ０ １ ２ １ ０ ０ １ ２ ０ ０ ０ ０ １ ６１ １９ ６ ２ １ １３６ ４２ １３ ４ １ １０８ ３３ １０ ３ １ 1 3 T A A ＝ 2 4 … ← ← ← ← ←
14
Authority Weightの正規化 Authority Weight が無意味に増大しないように毎回の正規化（Hub Weightについても同様） Authority weight a Initialize a = (1,…1) For I = 0,1,2,… a i+1 = A A a i Normalize a s.t. || a i+1||=1 → → T → → T → →
15
検索エンジンの種類 ロボット型 ロボットがWEB上を自動的に巡回してwebページを収集し、データベースを作成する ディレクトリ型 エディタ、サーファーなどと呼ばれる人間の閲覧者がwebサイトを審査し、ユーザーにとって有益であると認めたサイトをデータベースに登録する 複合型 ロボット型とディレクトリ型を複合して検索を行う ほとんどの検索エンジンポータルで、使われている
16
ロボット型検索エンジンの運営プロセス クローラー（スパイダー）と呼ばれるプログラムがWWW上のドキュメントを自動的に巡回する
クローラーで集めた情報をインデクサと呼ばれるプログラムでデータベース（インデックス）を作成する 与えられてた検索キー（クエリ）に対して、検索アルゴリズムに従ってデータベースの中を検索し、与えられた検索キーに対する適合度の高い順にURLをリストする
17
自身が情報源を持っているもの ： 背景に着色
R ： ロボットの検索結果 D ： ディレクトリーの検索結果 PPC ： ペイパークリック 破線 ： 結果の一部を提供 検索結果で優先して表示されるもの ： 赤字 自身が情報源を持っているもの ： 背景に着色 E-japan(株)調べ
18
-PageRank- ５０ １００ ５４ ５０ ４ １２ ５０ ４ ４ ページＡからページＢへのリンクをページＡからページＢへの支持投票とみなし その票数からそのページの重要度（PageRank）を算出する
19
-PageRank- web pageをノード，hyper-linkを有向辺とし www全体を有向グラフとみなす
Ｒａｎｋ（u）：ページvへのリンクをもつのuのPageRank Nu : ページ u からの外向きのリンク数 Bv : vを指しているページの集合 i : 更新の回数 u1 u2 v u3
20
-PageRank- web pageをノード，hyper-linkを有向辺として www全体を有向グラフとみなす 初期値を１ A0 1
C0 1 A C = B
21
-PageRank- １．リンク先に重要度を均等に分配 ２．分配された和を重要度として更新 Ai+1 1/2 0 1/2 Ai A
Bi /2 Bi Ci / Ci １．Aは重要度をAとBに均等に分配 ２．Ai+1 = 1/2 Ai+1 + 1/2 Ci+1 A B = C
22
-PageRank- i = 0 初期値 ＝ １ 均等に分配 A=1 B=1 C=1
23
-PageRank- i = 1 1/2 分配された和を 均等に配分 A=1 1/2 1/2 B=1/2 1 C=3/2 1/2
24
-PageRank- i = 2 1/2 分配された和を 均等に配分 A=5/4 3/4 1/2 B=3/4 1/2 C=1 3/4
25
-PageRank- i = 3 5/8 分配された和を 均等に配分 A=8/9 1/2 5/8 B=1/2 3/4 C=11/8 1/2
26
-PageRank- A=5/4 B=11/16 C=17/16 i = 4 9/16 分配された和を 均等に配分 11/16 9/16
1/2 C=17/16 11/16
27
-PageRank- lim … A0 1 B0 1 C0 1 = Ai+1 1/2 0 1/2 Ai A Bi+1 0 0 1/2 Bi
Ci / Ci Ai 6/5 5/ / / Bi 3/5 11/ / /4 1/ Ci 6/5 17/ / / = A B = C lim … = i→∞
28
-PageRank- Spider Trap lim … Ai+1 1/2 0 1/2 Ai Bi+1 0 0 1/2 Bi
Ci / Ci Ai / / / Bi / /4 3/ Ci / / /2 1/ Spider Trap A B = C 1 lim … = i→∞
29
-PageRank- Dead End lim … Ai+1 1/2 0 1/2 Ai Bi+1 0 0 1/2 Bi
Ci / Ci Ai / / / Bi / / /4 1/ Ci / / /2 1/ Dead End A B = C lim … = i→∞
30
-PageRank- lim … Dead End 効果の回避 Spider Trapの回避 税金の再配分 重要度の1部を 税金として徴収
Ai / / Ai Bi+1 （1-tax） / Bi +tax 1 Ci / Ci sample tax = 0.2 Ai 7/ Bi 21/ Ci 5/ = Dead End 効果の回避 税金の再配分 Spider Trapの回避 重要度の1部を 税金として徴収 lim … = i→∞
31
-PageRank- Ｒａｎｋ（ｖ）：ｖのPageRank Ｒａｎｋ（u）：ページvへのリンクをもつのuのPageRank
Nu : ページ u からの外向きのリンク数 Bv : vを指しているページの集合 N : ノードの総数 c : dampening factor (通常0.1～0.2に設定) i : 更新の回数
Similar presentations
