Link Analysis
click to edit
以hyperlink來ranking
(很多人link到它) -> 重要的link，but
有時會失準，因結構、或$(SEO)
Anchor Text(錨文字、註解、hashtag)
以web search來說好用(但是其中一個因子)
因有時首頁文字不一定完整呈現實際內容 -> 用其他anchor text
有時會抓多一點anchor text附近的字
PageRank
給一Web Graph(有方向性)，幫每個node(web page)，給一個分數
1.有link指過去，類似投票。
2.但hyper link是有投票權重
-> 菁英型投票
v：有指向u的網頁
x(v)：連向u的成績
deg(v)：網頁v推薦多少網站(權重程度，爛好人成績越低)
使用矩陣transition probability matrix
P
指向別人的表格
Pt
其他點指回自己的表格
第1列：1沒指到1，2、3必指到1
eigenvalue為1的eigenvector
所需特性：
eigenvector從哪來?
Makov chain
描述發生流程一系列的time step
包含N個State
每個time step
Web Surfing
相當於Makov chain
先從隨意一個Node當起點，在隨機選一條路徑
現象
有些點較容易走到(很多Node指向他)
可能有很多in-link
這個點比較重要
加總為1
x0，表示在t=0的起始點
x1 = Pt * X0
x2
= Pt x1
= (Pt) ^ 2 x0
= (P ^ 2)t * x0
Q1：不同出發點會不會造成不同結果?(這種eteratives能不能收斂，口試請注意)
Q2：N要幾次算多?
click to edit
Perron-Frobenius Theorem
irreducible & aperiodic Markov chain
n很大時，P ^ n = P ^ (n+1)...
不論怎麼逛，從哪個點出發都一樣
irreducible：任2個Node都互通
aperiodic
period di of state i
從node出發，繞一圈又回來
gcd = 1的period
makov chain是aperiodic表示：
所有Node都是aperiodic
web surfing不一定具有irreducible、aperiodic
解法-加入teleport：可以有跳到其他Node的機會(機率低)
a大約在0.1-0.2
是一個query-independent measure
與user輸入的query無關
是其中一個因子
HITS(Hyperlink-Induced Topic Search)
是query-dependent
認為網路上有2種類型的網頁
authorities page(內容)
hub page(像目錄)
假設網路上的子集合有一數量的authority pages：a(v)
& hub pages：h(v)
why不是等號：有正規化
用相鄰矩陣
AAt為一nn矩陣 -> 相當於一個eigenvalue的eigenvector
iterative方法
會收斂嗎?
let z = ((1/n)1/2, (1/n)1/2, ..., (1/n)1/2) in Rn
如何得到網頁的子集合?
For an eigenvalue, we have an infinite number of corresponding eigenvectors
if ω is an eigenvector of λ, then M(kω) = kMω = kλω = λ(kω)
1.如果有個對稱矩陣，一定有eigenvector
2.if M = BBT or M = BTB(對稱矩陣), the corresponding eigenvalues must be non-negative!!
將最大的eigenvalue eigenvector稱為principal eigenvector
1.如果有對稱矩陣為非0矩陣，則其principal eigenvector唯一非0值
2.如果有個v與principal eigenvector為非正交，經過幾次(約20次)後會到principal eigenvector
設找一個query q，則Sq應要有特性
1.Sq要小
2.Sq與q相關
3.Sq包含很多authorities
1、2容易取得(以全文檢索)
3.解法Base set：
a.將指出去的page全抓進來
b.將部分指回來的page抓進來(隨機數量)
有些link是intrinsic(固有的)