官 斌

(武漢市74223信箱 武漢 430074)

1 引言

隨著互聯(lián)網(wǎng)絡(luò)的日益迅猛增長(zhǎng),互聯(lián)網(wǎng)絡(luò)已成為世界上規(guī)模最大的信息源之一。在如此巨大的數(shù)據(jù)海洋中尋找用戶所需要的信息已不是人力所能勝任的工作了,因而搜索引擎已經(jīng)作為互聯(lián)網(wǎng)上最有效的信息獲取工具而為人們廣泛接受。

不同于傳統(tǒng)的信息檢索(圖書館資源檢索),互聯(lián)網(wǎng)不僅包含了大量的內(nèi)容信息(包括文字、圖像、聲音、視頻),而且還包含了復(fù)雜的結(jié)構(gòu)信息(如超鏈接關(guān)系,網(wǎng)站的組織結(jié)構(gòu)等等)。對(duì)互聯(lián)網(wǎng)結(jié)構(gòu)信息的利用能夠很大程度上決定一個(gè)搜索引擎性能的好壞。因此,鏈接分析(link analysis)已成為互聯(lián)網(wǎng)檢索領(lǐng)域一個(gè)很熱的話題,吸引了眾多研究者的關(guān)注。本文介紹了從1998年以來(lái)鏈接分析技術(shù)的進(jìn)展,并在此基礎(chǔ)上指出了進(jìn)一步的研究方向。

2 鏈接分析的興起:兩大經(jīng)典算法的提出

1998年是互聯(lián)網(wǎng)搜索歷史上最有紀(jì)念意義的一年。鏈接分析的兩大經(jīng)典算法都于該年提出:HITS和PageRank。正是由于鏈接分析的運(yùn)用,是互聯(lián)網(wǎng)搜索的準(zhǔn)確程度有了一個(gè)質(zhì)的飛躍。下面我們簡(jiǎn)單介紹一下這兩個(gè)算法。

2.1 PageRank算法

PageRank[2]是由斯坦福大學(xué)的兩個(gè)博士研究生Sergey Brin和Lawrence Page于1998年提出,Google即為該論文的原型系統(tǒng),如今已發(fā)展成為世界上最好的搜索引擎。

PageRank算法的基本思想相當(dāng)簡(jiǎn)單。PageR-ank認(rèn)為,每個(gè)網(wǎng)頁(yè)的重要程度是不一樣的。如果一個(gè)網(wǎng)頁(yè)被很多網(wǎng)頁(yè)指向,那么該網(wǎng)頁(yè)很可能非常重要;另外,一個(gè)重要的網(wǎng)頁(yè)所指向的網(wǎng)頁(yè)也很可能非常重要。PageRank的基本原理可以用馬爾可夫隨機(jī)游走模型來(lái)解釋。PageRank模仿一個(gè)用戶在互聯(lián)網(wǎng)上瀏覽行為,在當(dāng)前時(shí)刻,該用戶以一定的概率q跳轉(zhuǎn)到任意一個(gè)網(wǎng)頁(yè),或者以概率1-q跳轉(zhuǎn)到當(dāng)前網(wǎng)頁(yè)所指向的某一網(wǎng)頁(yè)。該過(guò)程可以用一個(gè)馬爾可夫鏈來(lái)建模,互聯(lián)網(wǎng)中的每一個(gè)網(wǎng)頁(yè)就是馬爾可夫鏈中的一個(gè)狀態(tài)。該馬爾可夫鏈平穩(wěn)時(shí)每個(gè)狀態(tài)停留的概率即反映了相應(yīng)網(wǎng)頁(yè)的重要程度。

下面我們介紹一下PageRank算法的具體實(shí)現(xiàn)。如果整個(gè)網(wǎng)絡(luò)有n個(gè)網(wǎng)頁(yè),將這個(gè)網(wǎng)絡(luò)看成有n個(gè)節(jié)點(diǎn)的有向圖,圖上的每條有向邊代表了互聯(lián)網(wǎng)上一個(gè)超鏈接。該圖的鄰接矩陣A記為:將鄰接矩陣的每一行行和歸一化,我們可以得到該隨機(jī)跳轉(zhuǎn)(馬爾可夫鏈)的概率轉(zhuǎn)移矩陣 ˉA。為了保證該馬爾可夫鏈能夠收斂到一個(gè)平穩(wěn)狀態(tài),該馬氏鏈必須滿足非周期不可約兩條性質(zhì)。然而對(duì)于一個(gè)實(shí)際的網(wǎng)絡(luò),并不一定能夠滿足這兩個(gè)條件。這里PageRank算法對(duì)概率轉(zhuǎn)移矩陣ˉA進(jìn)行了平滑處理其中U是一個(gè)n*n的矩陣,并且每一個(gè)元素都為1/n。其中α是一個(gè)經(jīng)驗(yàn)常數(shù)[2],建議使用0.85。進(jìn)行了平滑之后,就能夠確保隨機(jī)跳轉(zhuǎn)的平穩(wěn)狀態(tài)存在且唯一。將該馬氏鏈平穩(wěn)狀態(tài)每個(gè)節(jié)點(diǎn)停留概率記為πi,那么πi就體現(xiàn)了網(wǎng)頁(yè)的重要程度。πi越大,該網(wǎng)頁(yè)越重要。πi可以由如下公式計(jì)算得到

也就是說(shuō),整個(gè)網(wǎng)絡(luò)的PageRank向量就是平滑后的概率轉(zhuǎn)移矩陣最大的左特征向量。由于鄰接矩陣的規(guī)模相當(dāng)龐大(對(duì)于現(xiàn)在的互聯(lián)網(wǎng),網(wǎng)頁(yè)的數(shù)量都在十億的規(guī)模),因此人們一般不是直接求的特征向量,而是采用如下的冪法迭代

直到收斂為止。

2.2 HITS算法

不同于PageRank算法用一個(gè)量來(lái)衡量一個(gè)網(wǎng)頁(yè)的重要性,HITS用兩個(gè)量來(lái)衡量一個(gè)網(wǎng)頁(yè)的好壞:Hub值和 Authority值。直觀的理解,Authority值反映了網(wǎng)頁(yè)本身質(zhì)量的好壞,如果該網(wǎng)頁(yè)自己的內(nèi)容很好,則她的Authority值就可能很高;Hub放映了網(wǎng)頁(yè)本身作為路由的好壞,如果該網(wǎng)頁(yè)所指向的很多網(wǎng)頁(yè)的質(zhì)量都很高,那么該網(wǎng)頁(yè)本身的Hub值就可能很高。如果我們記網(wǎng)絡(luò)的Hub向量為h,Authority向量為a(和 PageRank向量類似,hi和ai分別表示了網(wǎng)頁(yè)i的Hub值和Authority值),那么這兩者之間的關(guān)系可以表示為

通過(guò)以上兩式迭代達(dá)到最終收斂時(shí),就可以得到整個(gè)網(wǎng)絡(luò)的Hub向量h和Authority向量a。

3 鏈接分析的高潮:兩大算法的各種變種

隨著兩大算法的提出,人們發(fā)現(xiàn)他們的確對(duì)搜索性能有很大的提高,因而大大激發(fā)了人們對(duì)鏈接分析研究的熱情,對(duì)PageRank和HITS進(jìn)行了廣泛的研究,提出了各種各樣的推廣和變種。由于該方面的文獻(xiàn)很多,這里只是選取其中幾個(gè)最有代表性的工作進(jìn)行介紹。

3.1 主題敏感的PageRank

在前面我們提到PageRank算法不依賴于查詢?cè)~,對(duì)每一個(gè)網(wǎng)頁(yè)只計(jì)算一個(gè)PageRank值來(lái)表示它的重要性,這樣整個(gè)網(wǎng)絡(luò)只有一個(gè)PageRank向量[5]。提出了主題敏感的PageRank算法。該算法的基本思想是選定一定數(shù)量的主題,(對(duì)每一個(gè)主題計(jì)算一個(gè)PageRank向量,這樣每一個(gè)網(wǎng)頁(yè)相應(yīng)于每一個(gè)主題都有一個(gè) PageRank值。當(dāng)來(lái)了一個(gè)查詢?cè)~后,根據(jù)該查詢?cè)~和每個(gè)主題的相關(guān)程度將任意一個(gè)網(wǎng)頁(yè)對(duì)應(yīng)于不同主題的PageRank值組合起來(lái),就得到該網(wǎng)頁(yè)相應(yīng)于這個(gè)特定詞的PageRank值。需要指出的是,不同查詢?cè)~的組合方式不同,需要在搜索時(shí)實(shí)時(shí)計(jì)算。

可以看到,主題敏感的PageRank對(duì)不同的查詢?cè)~區(qū)別對(duì)待,因此計(jì)算出來(lái)的PageRank值會(huì)比標(biāo)準(zhǔn)的PageRank值更加準(zhǔn)確。

3.2 塊級(jí)別的鏈接分析

鏈接分析的大部分工作都是網(wǎng)頁(yè)級(jí)別的,也就是把每一個(gè)網(wǎng)頁(yè)當(dāng)作圖中的一個(gè)節(jié)點(diǎn),然后考察每個(gè)節(jié)點(diǎn)的屬性。實(shí)際互聯(lián)網(wǎng)中的網(wǎng)頁(yè)往往含有多種意義,網(wǎng)頁(yè)的不同部分所反映的內(nèi)容不同。例如每個(gè)網(wǎng)頁(yè)的中間部分的內(nèi)容往往是該網(wǎng)頁(yè)所想表達(dá)的真正意思,網(wǎng)頁(yè)的最下面往往都是一些網(wǎng)站的版權(quán)信息,網(wǎng)頁(yè)的左右的側(cè)邊欄則往往是一些導(dǎo)航鏈接或者廣告。因此文獻(xiàn)[3]認(rèn)為網(wǎng)頁(yè)的每一部分的重要性程度不同,他們提出了塊級(jí)別的鏈接分析算法。塊級(jí)別的鏈接分析算法的基本思想實(shí)現(xiàn)對(duì)每個(gè)網(wǎng)頁(yè)分塊,然后網(wǎng)頁(yè)中的每一個(gè)塊作為一個(gè)節(jié)點(diǎn)構(gòu)造塊級(jí)別的圖,然后在該圖上應(yīng)用PageRank或HITS算法。

塊級(jí)別的鏈接分析算法由于對(duì)網(wǎng)頁(yè)的每一部分區(qū)分對(duì)待,因此能夠很大程度上抑制噪聲的影響。特別是一些網(wǎng)頁(yè)經(jīng)常在邊沿部分添加大量的惡意鏈接,而塊級(jí)別的鏈接分析算法恰好能夠把網(wǎng)頁(yè)的這些部分和重要內(nèi)容部分區(qū)別對(duì)待。

3.3 考慮網(wǎng)絡(luò)層次結(jié)構(gòu)的鏈接分析

無(wú)論是網(wǎng)頁(yè)級(jí)別的鏈接分析還是塊級(jí)別的鏈接分析,他們都把網(wǎng)絡(luò)看成一個(gè)平片結(jié)構(gòu),網(wǎng)絡(luò)中的節(jié)點(diǎn)本身是無(wú)法區(qū)分的,除了他們連接的邊不同之外。然而實(shí)際的互聯(lián)網(wǎng)是層次化結(jié)構(gòu)的,近年來(lái)有很多文獻(xiàn)[4,11～12]利用該特點(diǎn)來(lái)更好地進(jìn)行鏈接分析。

將萬(wàn)維網(wǎng)看成平面化的網(wǎng)絡(luò)進(jìn)行連接分析有兩個(gè)問(wèn)題:第一是每個(gè)節(jié)點(diǎn)(網(wǎng)頁(yè))的連接很稀疏;第二是無(wú)法很好的處理新出現(xiàn)的網(wǎng)頁(yè),因?yàn)楹苌贂?huì)有鏈接指向一個(gè)剛剛出現(xiàn)的網(wǎng)頁(yè),盡管這個(gè)網(wǎng)頁(yè)的內(nèi)容可能會(huì)很好。因此文獻(xiàn)[11]提出了一種鏈接分析的算法,綜合利用了萬(wàn)維網(wǎng)的層次化結(jié)構(gòu)和超鏈接結(jié)構(gòu)。他們構(gòu)建出的萬(wàn)維網(wǎng)拓?fù)浣Y(jié)構(gòu)如圖1所示。該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)主要有兩層,上層反映的是站點(diǎn)之間的鏈接關(guān)系,下層反映的是每個(gè)站點(diǎn)內(nèi)部的層次結(jié)構(gòu)關(guān)系。根據(jù)該拓?fù)浣Y(jié)構(gòu),他們定義了一個(gè)新的隨機(jī)游走模型。

圖1 層狀互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)

4 鏈接分析的深入:計(jì)算與理論

隨著鏈接分析算法的日益增多,人們不再局限于僅僅是對(duì)PageRank算法和HITS算法進(jìn)行簡(jiǎn)單的推廣或改動(dòng),進(jìn)而開始研究算法本身的一些性質(zhì),主要是兩方面的內(nèi)容:計(jì)算和理論。在第一節(jié)中我們已經(jīng)指出,相對(duì)而言PageRank算法更具理論基礎(chǔ),因此鏈接分析的深入研究主要是針對(duì)PageRank算法。

4.1 PageRank的快速計(jì)算

PageRank算法由于是在整個(gè)萬(wàn)維網(wǎng)上進(jìn)行迭代計(jì)算,因此計(jì)算的規(guī)模相當(dāng)龐大,如何進(jìn)行快速的計(jì)算是一個(gè)非常重要的問(wèn)題。

文獻(xiàn)[6]中提出了一種二次外推法來(lái)加速PageRank的計(jì)算。正如在第一節(jié)中所述,原始的PageRank的計(jì)算采取的是乘冪迭代法,最后迭代收斂到概率轉(zhuǎn)移矩陣的最大特征值所對(duì)應(yīng)的特征向量。文獻(xiàn)[6]中的二次外推法從迭代向量中周期性減去非最大特征向量的成分,因而能夠大大加快PageRank的收斂速度。Sepandar D.Kamvar等人在文獻(xiàn)[6]中巧妙的利用概率轉(zhuǎn)移矩陣的最大特征值為1這一特點(diǎn)來(lái)計(jì)算其他的非最大特征向量。他們的實(shí)驗(yàn)表明,在一個(gè)8千萬(wàn)網(wǎng)頁(yè)的互聯(lián)網(wǎng)上,該算法對(duì) PageRank的計(jì)算可以加速到 25%～300%。

文獻(xiàn)[9]中提出了另外一種方法來(lái)加速PageRank的計(jì)算。他們的核心思想是在PageRank的每一次迭代中相鄰節(jié)點(diǎn)間傳遞的不再是各個(gè)節(jié)點(diǎn)的概率值,而是節(jié)點(diǎn)概率的改變值。這樣一種方法使得節(jié)點(diǎn)在更新它們的概率值是有很大的自由度,并將該問(wèn)題轉(zhuǎn)化為矩陣優(yōu)化問(wèn)題,這樣就帶來(lái)了一系列的好處,如快速收斂性,高效的增量式更新,以及穩(wěn)定的分布式實(shí)現(xiàn)?！中實(shí)驗(yàn)表明,在一個(gè)3千4百萬(wàn)網(wǎng)頁(yè)的互聯(lián)網(wǎng)上,該算法能夠有效提升PageRank計(jì)算的性能。

4.2 PageRank的理論分析

由于PageRank算法的計(jì)算是要通過(guò)不停的迭代直到收斂為止,這樣就產(chǎn)生了很多數(shù)學(xué)分析上的理論問(wèn)題:該迭代的收斂性能如何?收斂速度如何?對(duì)擾動(dòng)的敏感程度如何?目前已經(jīng)開始有研究人員注意到這些問(wèn)題,并做出了一些很好的工作。

從式(2)可以看出,PageRank中的馬氏鏈的概率轉(zhuǎn)移陣是由兩部分共同決定的,一部分是網(wǎng)絡(luò)本身的結(jié)構(gòu)即ˉA,另一部分則是均勻矩陣U,而經(jīng)驗(yàn)常數(shù)α則決定了這兩部分之間的比重。文獻(xiàn)[2]中雖然建議α取0.85,但是并沒有解釋為什么要選擇這樣一個(gè)值,并且人們也發(fā)現(xiàn),不同的α不僅對(duì)最終每個(gè)網(wǎng)頁(yè)的PageRank值會(huì)帶來(lái)很大的影響,甚至?xí)まD(zhuǎn)網(wǎng)頁(yè)之間相對(duì)重要的順序文獻(xiàn)[8,10]。那么α究竟該如何選擇?有沒有什么理論依據(jù)?文獻(xiàn)[1]中將最終的PageRank向量作為α的一個(gè)函數(shù),首次對(duì)PageRank向量隨著α的改變進(jìn)行了嚴(yán)密的數(shù)學(xué)分析。

注意α的取值為半開區(qū)間[0,1)。給定一個(gè)α值,我們就可以得到一個(gè) PageRank向量r(α)。文獻(xiàn)[1]中首先證明了如下極限的存在

進(jìn)而文獻(xiàn)[1]文發(fā)現(xiàn)雖然當(dāng)α趨近1時(shí),該馬氏鏈越來(lái)越接近準(zhǔn)確的網(wǎng)絡(luò)連接圖,但是得到PageRank向量卻并不能帶來(lái)很好的網(wǎng)頁(yè)排序。另外,文獻(xiàn)[1]文還給出了PageRank向量r(α)對(duì) α的任意階倒數(shù)的解析形式,為PageRank算法的理論分析提供了堅(jiān)實(shí)的基礎(chǔ)。

5 鏈接分析的展望:搜索引擎的優(yōu)化與作弊

由于鏈接分析算法在搜索引擎中占到了很重要的作用,導(dǎo)致了很多人專門針對(duì)網(wǎng)站的超鏈接進(jìn)行優(yōu)化或者作弊,并給搜索引擎的性能帶來(lái)惡劣的效果。Google作為全球最大最成功的搜索引擎,已經(jīng)把如何應(yīng)對(duì)搜索引擎作弊列為當(dāng)前最重要的挑戰(zhàn)。

我們可以看出,鏈接分析這幾年來(lái)取得了很大的進(jìn)展,但是也遇到了一些問(wèn)題。例如很多搜索引擎優(yōu)化或作弊專門針對(duì)不同的鏈接分析出發(fā):為了提高一個(gè)網(wǎng)頁(yè)的PageRank值在很多網(wǎng)頁(yè)上發(fā)布自己的網(wǎng)址,這樣就可以增加指向自己的鏈接;同樣為了提高網(wǎng)頁(yè)的Hub值而在網(wǎng)頁(yè)上增加很多和內(nèi)容完全不相關(guān)的超鏈接,這樣來(lái)增加網(wǎng)頁(yè)指出去的鏈接。

因此我們預(yù)言,鏈接分析算法下面一個(gè)很重要的研究問(wèn)題就是如何有效地抵制搜索引擎優(yōu)化或作弊。具體說(shuō)來(lái),我們認(rèn)為可以從以下兩個(gè)角度來(lái)進(jìn)行研究:

1)改進(jìn)現(xiàn)有鏈接分析算法,使之能夠發(fā)現(xiàn)作弊的網(wǎng)頁(yè);

2)提出新的鏈接分析算法,而這些因?yàn)榭紤]到了搜索引擎作弊的可能而很難被一般的作弊方法干擾。

[1]P.Boldi,M.Santini,S.Vigna.PageRank as a function of the damping factor[C].WWW2005

[2]S.Brin,L.Page.The anatomy of a large-scale hypertextual Web search engine[C].WWW1998

[3]D.Cai,X.F.He,JR Wen,et al.block level link analysis.SIGIR2004

[4]G.Feng,T.Liu,X.Zhang,et al.Level-Based Link Analysis[C].APWeb2005

[5]T.H.Haveliwala.Topic-Sensitive PageRank[C].WWW2002

[6]S.D.Kamvar,T.H.Haveliwala,C.D.Manning,et al.Extrapolation Methods for Accelerating PageRank Computations[C].WWW2003

[7]Kleinberg,J.Authoritative Sources in a Hyperlinked Environment[J].Journal of the ACM,1999,46(5)

[8]A.N.Langville,C.D.Meyer.Deeper inside PageRank[J].Internet Mathematics,2004,1(3)

[9]Frank McSherry.A uniform approach to accelerated PageRank computation[C].WWW2005

[10]L.Pretto.A theoretical approach to link analysis algorithms[D].2002

[11]G.Xue,Q.Yang,H.Zeng,et al.Exploiting the Hierarchical Structure for Link Analysis.SIGIR2005

[12]H.Yan,T.Qin,T.Liu,et al.Calculating Webpage Importancewith SiteStructureConstraints[C].AIRS2005