方 奇，劉奕群，張 敏，茹立云，馬少平

(智能技術(shù)與系統(tǒng)國家重點實驗室 清華信息科學(xué)與技術(shù)國家實驗室(籌) 清華大學(xué)計算機系，北京 100084)

1 引言

網(wǎng)頁瀏覽器是Web服務(wù)的客戶端瀏覽程序(以下簡稱瀏覽器)。用戶通過使用瀏覽器得以訪問各種Web資源，可以說瀏覽器是用戶與萬維網(wǎng)的接口。收藏夾是瀏覽器中一個與用戶聯(lián)系緊密的功能部件。用戶使用收藏夾收藏感興趣的網(wǎng)頁，同時通過點擊收藏夾中節(jié)點實現(xiàn)快速訪問。

由于收藏夾的特殊性，如果我們能從用戶收藏行為中挖掘出有效信息，將為許多研究提供幫助。根據(jù)收藏夾數(shù)據(jù)的產(chǎn)生方式和存儲結(jié)構(gòu)特點，我們認(rèn)為研究用戶收藏行為具有以下重要意義。

首先，收藏夾大部分?jǐn)?shù)據(jù)都是用戶在Web瀏覽過程中主動搜集添加的。區(qū)別于一般網(wǎng)絡(luò)資源，收藏夾數(shù)據(jù)經(jīng)過用戶認(rèn)證，對用戶有特殊意義，或是常用工具，或是對其內(nèi)容有偏好，需要存儲下來備忘。而當(dāng)前用戶行為分析領(lǐng)域中最常用的兩種日志，Web訪問日志[1-2]和搜索引擎查詢?nèi)罩綶3]則主要記錄用戶點擊行為。實際上，由于點擊操作只表示用戶開始瀏覽該網(wǎng)頁，并不能準(zhǔn)確反映出用戶瀏覽完該網(wǎng)頁后的反饋情況。與上述兩種日志相比，收藏夾數(shù)據(jù)更能體現(xiàn)用戶的興趣特點，用戶收藏的網(wǎng)頁應(yīng)該具有更高的質(zhì)量。因此，從網(wǎng)頁粒度上看，可以將用戶收藏行為分析應(yīng)用到網(wǎng)頁質(zhì)量評估[1-2]、反垃圾[4-5]工作中；將收藏夾中的文本看成是用戶對網(wǎng)頁的描述，可以像鏈接文本一樣，應(yīng)用到信息檢索領(lǐng)域，幫助提高搜索引擎性能[6]。從用戶層面上看，收藏夾信息將為用戶個性化研究[7]、廣告投放[8]提供另一種數(shù)據(jù)來源。

其次，收藏夾數(shù)據(jù)和其他Web日志數(shù)據(jù)相比，最大的區(qū)別是擁有結(jié)構(gòu)信息。傳統(tǒng)的網(wǎng)絡(luò)信息一般是半結(jié)構(gòu)化數(shù)據(jù)，盡管具有鏈接結(jié)構(gòu)，但鏈接結(jié)構(gòu)呈現(xiàn)的是一種自組織的小世界網(wǎng)絡(luò)形式；對于用戶組織信息的過程而言，收藏夾的樹狀結(jié)構(gòu)無疑更加自然與便利。如果能從中挖掘出高質(zhì)量的結(jié)構(gòu)信息，將對研究網(wǎng)絡(luò)資源相互關(guān)系的工作提供十分重要的幫助。例如，可以基于結(jié)構(gòu)信息計算出網(wǎng)頁之間的相關(guān)度，甚至成為大規(guī)模網(wǎng)頁目錄構(gòu)建[9]的基礎(chǔ)。同時，收藏夾的結(jié)構(gòu)特征體現(xiàn)了用戶的使用習(xí)慣。由于現(xiàn)階段瀏覽器用戶在使用收藏夾時采用的是瀏覽查找加點擊的方式，從開始查找到完成點擊，樹狀結(jié)構(gòu)中不同位置的節(jié)點所需耗費的時間代價是不一樣的。一個組織紊亂的收藏夾將影響用戶體驗。用戶是否會根據(jù)自己對不同網(wǎng)頁的訪問頻度調(diào)整收藏夾的組織結(jié)構(gòu)，什么樣的樹結(jié)構(gòu)能最大限度地幫助用戶提高瀏覽效率，這都是值得關(guān)注的問題。

目前，針對網(wǎng)絡(luò)用戶收藏行為的研究工作不多，本文試圖通過對真實數(shù)據(jù)統(tǒng)計分析，回答以下三個核心問題：

(1) 用戶怎樣收藏網(wǎng)頁；

(2) 用戶傾向于收藏哪些網(wǎng)頁；

(3) 收藏夾用戶有什么興趣特點。

2 數(shù)據(jù)格式與預(yù)處理

本文實驗所使用的瀏覽器收藏夾數(shù)據(jù)是由國內(nèi)一家著名搜索引擎公司通過其瀏覽器搜集并提供的。為了保護用戶隱私，數(shù)據(jù)是在“用戶體驗改進計劃”的參與者中抽取的，數(shù)據(jù)收集經(jīng)過了用戶的同意，并刪除了用戶的IP、用戶名等個人信息。數(shù)據(jù)使用樹結(jié)構(gòu)進行存儲。具體格式如下。

表1 數(shù)據(jù)格式

所有用戶ID相同的節(jié)點構(gòu)成了一個用戶的收藏夾樹。收藏夾樹包含兩種節(jié)點： 網(wǎng)頁節(jié)點和目錄節(jié)點。其中目錄節(jié)點URL字段為空。樹中所有中間節(jié)點均為目錄節(jié)點，網(wǎng)頁節(jié)點必定是葉子節(jié)點。為敘述方便，我們形式化定義相關(guān)概念。

定義1收藏夾樹的集合用T表示，即數(shù)據(jù)全集。樹節(jié)點集合用V表示，邊集用E表示。T=。

定義2樹t(usrID)表示用戶usrID的收藏夾。其中t∈T。

定義3樹節(jié)點u(usrID,nodeID)表示用戶usrID的收藏夾中標(biāo)識為nodeID的節(jié)點(u∈V)，由二元組表示u=。其中URL和text分別表示為URLu和textu。

在此基礎(chǔ)上，我們定義一些本文使用的基本函數(shù)。

表2 本文定義的函數(shù)

真實的數(shù)據(jù)中往往存在許多噪聲。實驗的第一步是進行預(yù)處理，過濾掉無用或者有干擾的數(shù)據(jù)。

首先，我們將只包含目錄節(jié)點的收藏夾過濾掉。這類用戶并沒有存儲任何網(wǎng)頁信息，對研究沒有幫助。其次，我們刪除在整個數(shù)據(jù)集T中大量重復(fù)出現(xiàn)且深度大于等于2的子樹。我們發(fā)現(xiàn)有許多桌面軟件和網(wǎng)站未經(jīng)用戶許可擅自在瀏覽器收藏夾中添加信息。這部分?jǐn)?shù)據(jù)不是用戶主動添加的，不能反映用戶真實意圖，會對我們的分析造成干擾，因此需要被過濾。為避免誤刪有用數(shù)據(jù)，我們判斷兩棵子樹相同，當(dāng)且僅當(dāng)兩棵子樹同構(gòu)，并且對應(yīng)節(jié)點的URL和text完全相同。

原始數(shù)據(jù)集包含277 948個用戶，23 845 787個節(jié)點。經(jīng)過上述兩步過濾，預(yù)處理之后剩下273 168個用戶，20 009 308個節(jié)點。其中，去除掉的噪聲用戶為1.7%，噪聲節(jié)點為16%。

3 收藏夾結(jié)構(gòu)分析

3.1 深度和節(jié)點數(shù)特征

深度和節(jié)點數(shù)量是衡量一棵樹的重要特征。對于收藏夾而言，深度表示用戶構(gòu)建目錄的最大層數(shù)；節(jié)點數(shù)量則等于用戶收藏網(wǎng)頁數(shù)量與構(gòu)建目錄數(shù)量之和。兩者反映了收藏夾的規(guī)模。?t∈T，計算深度height(t)和節(jié)點數(shù)量|Vt|，分別統(tǒng)計出現(xiàn)比例，得到圖1。

圖1 深度和節(jié)點數(shù)

從圖1(a)可以看出，深度為2的用戶最多，占48%，這部分用戶在收藏夾中建立了一層目錄。第二多的是深度為1的用戶，占36%，這表示用戶并沒有使用目錄，而是直接把網(wǎng)頁存在根節(jié)點下。除去深度為1的數(shù)據(jù)，有64%的用戶習(xí)慣至少建立一層目錄，說明從中還是能得到不少結(jié)構(gòu)化信息。如果將深度小于等于2的樹看成是“扁平型”，將深度大于等于5以上的樹看成是“縱深型”，那么結(jié)果表明用戶更傾向于“扁平型”的收藏夾，占84%，只有約2%的收藏夾屬于“縱深型”。

圖1(b)顯示，用戶收藏的網(wǎng)頁數(shù)量分布比較分散(從1到1 300)，并沒有出現(xiàn)明顯的峰值。整體而言，包含網(wǎng)頁數(shù)量越高，對應(yīng)的用戶越少。有4%的用戶只收藏了1個網(wǎng)頁， 有80%的收藏夾包含不到100個網(wǎng)頁。對比廣泛使用的Web訪問日志，收藏夾數(shù)據(jù)規(guī)模較小，用戶傾向于收藏少量訪問過的頁面。

3.2 收藏夾瀏覽點擊模型

瀏覽器用戶在使用收藏夾的時候采用順序瀏覽查找加點擊的方式，如目標(biāo)網(wǎng)頁在較深層目錄下，則需將路徑上的父輩節(jié)點逐一點擊展開。不同的樹狀組織結(jié)構(gòu)將影響收藏夾的使用效率。為了評估收藏夾的使用效率，我們提出了基于收藏夾的瀏覽點擊模型BBCM(Bookmarks Browse Click Model)。

3.2.1 耗時與耗時期望

收藏夾瀏覽點擊模型建立在用戶順序瀏覽和點擊展開兩種行為模式上。

定義4ST(Search Time)表示用戶在當(dāng)前節(jié)點u下查找一個兒子節(jié)點所需的平均時間。不失一般性，我們認(rèn)為用戶順序瀏覽節(jié)點的間隔時間相同，因此ST與當(dāng)前節(jié)點包含的兒子節(jié)點數(shù)量成正比，令ST=α×|childSet(u)|，α為常量。

定義5CT(Click Time)表示用戶點擊一個節(jié)點所需時間。不失一般性，我們認(rèn)為用戶執(zhí)行點擊操作耗時相同，因此令CT等于一個常量β，CT=β。

根據(jù)BBCM模型，我們定義了兩個新指標(biāo)： 耗時RT(Required Time) 和耗時期望RTE(Required Time Expectation)。

定義6用戶訪問節(jié)點u的耗時RT(u)是指在BBCM模型中用戶從根節(jié)點開始執(zhí)行順序瀏覽和點擊展開操作，直到最終點擊訪問節(jié)點u所耗費的時間。

基于定義4和定義5，我們可以得到計算訪問節(jié)點u的耗時RT(u)的遞推式：

當(dāng)u非根節(jié)點時，

RT(u)= RT(parent(u))+α

×|childSet(parent(u))|+β;

當(dāng)u是根節(jié)點時，

RT(u)=0。

定義7用戶訪問收藏夾t的耗時期望RTE(t)表示在BBCM模型中用戶訪問t中一個網(wǎng)頁節(jié)點的耗時期望。

在沒有其他日志數(shù)據(jù)支持的情況下，我們認(rèn)為同一個收藏夾中的所有網(wǎng)頁節(jié)點的訪問概率相等，即先驗分布是均勻分布。于是，我們可以得到收藏夾(t)的耗時期望：

RTE將隨著收藏夾的規(guī)模增大而變大。僅從訪問效率而言，我們希望在收藏夾包含節(jié)點數(shù)量一定的情況下，RTE越小越好。

3.2.2 最小耗時期望

在BBCM模型中，給定收藏夾樹t包含的網(wǎng)頁節(jié)點數(shù)量|pageSet(t)|，我們能構(gòu)造出令PRE(t)最小的樹狀結(jié)構(gòu)。這樣的樹狀結(jié)構(gòu)通常不止一個。我們希望計算出最小耗時期望MRTE(Minimum Required Time Expectation)。

定義8最小耗時期望MRTE(n)是指包含n個網(wǎng)頁節(jié)點的所有可能形態(tài)樹狀結(jié)構(gòu)的耗時期望的最小值。

MRTE(n)的具體推導(dǎo)如下：

令g(m,n)表示包含n個葉子節(jié)點并且根節(jié)點有m個兒子節(jié)點的樹的最小總耗時。分三種情況討論：

(1) 當(dāng)m=n時，將n個葉子節(jié)點放在根節(jié)點下即可。g(n,n)=(α×n+β)×n

(2) 當(dāng)2≤m

g(m,n)= minm-1≤k

+αk+α(m-1)(n-k)}

(3) 當(dāng)1=m

g(1,n)=min2≤k

通過g(m,n)，我們可以得到MRTE(n)：

至此，我們完成了最小耗時期望MRTE(n)全部推導(dǎo)過程。

3.2.3 實驗與分析

定義9平均耗時期望ARTE(n)表示數(shù)據(jù)集中包含n個網(wǎng)頁節(jié)點的收藏夾的平均耗時期望。

根據(jù)BBCM模型，我們評估數(shù)據(jù)集T的整體使用效率。首先，對于數(shù)據(jù)集中的每個收藏夾t，計算其耗時期望RTE(t)。然后，給定網(wǎng)頁節(jié)點數(shù)量n，計算所有包含n個網(wǎng)頁的收藏夾的平均耗時期望ARTE(n)和最小耗時期望MRTE(n)，比較兩者的差值。

實驗中我們?nèi)ˇ?0.1s，β=0.2s。

圖2 使用效率分析

從圖2可以看出，當(dāng)網(wǎng)頁節(jié)點數(shù)較小時，ARTE和MRTE還比較接近；當(dāng)網(wǎng)頁節(jié)點數(shù)增加時，MRTE增長得十分緩慢，基本不變，而ARTE增長則較為迅速，與MRTE差距逐漸拉大。例如，當(dāng)n=1 時ARTE(1)=0.32，MRTE(1)=0.3；當(dāng)n=100時ARTE(100)=5.47，MRTE(100)=2；當(dāng)n=1 000 時ARTE(1 000)=13.4，MRTE(1 000)= 2.99。需要說明的是，網(wǎng)頁節(jié)點數(shù)越大ARTE震蕩越厲害是因為此時對應(yīng)的用戶數(shù)量在急劇減少(從圖1(b)k可以看出)，于是平均值缺乏穩(wěn)定。

上述實驗結(jié)果表明，從使用效率上看，許多用戶的收藏夾組織方式有很大改進空間。在網(wǎng)頁節(jié)點訪問概率均勻分布的先驗假設(shè)下，通過計算，我們發(fā)現(xiàn)過于“扁平型”和“縱深型”的樹狀結(jié)構(gòu)使用效率都不高，“平衡型”結(jié)構(gòu)則較好。當(dāng)然，用戶實際存儲網(wǎng)頁節(jié)點時需要考慮到內(nèi)容上的相關(guān)性，往往并不能達(dá)到理想的MRTE值。因此，用戶可以在內(nèi)容關(guān)聯(lián)的基礎(chǔ)上，盡量將樹狀結(jié)構(gòu)調(diào)整成“平衡型”，減少RTE值。

4 收藏夾網(wǎng)站質(zhì)量評估

從收藏夾數(shù)據(jù)的產(chǎn)生方式可知，收藏夾中的網(wǎng)絡(luò)資源可以看成是用戶精心挑選的結(jié)果。那么這部分網(wǎng)絡(luò)資源的質(zhì)量如何呢？本節(jié)試圖初步評估收藏夾中包含網(wǎng)站的質(zhì)量，為后續(xù)將收藏夾數(shù)據(jù)擴展到反垃圾和網(wǎng)頁質(zhì)量評估等工作打下基礎(chǔ)。

4.1 PR與CF

PageRank算法[10]是著名搜索引擎Google早期使用的用于評價網(wǎng)頁重要性的一種網(wǎng)頁級別排序算法。由于Google公司的成功，PageRank算法也被研究界和業(yè)界廣泛采用。

將用戶在Web上的瀏覽行為看成是一個Markov隨機沖浪模型，PR(PageRank)值代表了各個網(wǎng)頁極限狀態(tài)下的被訪問概率。具體公式如下：

圖3 收藏夾站點質(zhì)量評估

其中pi表示網(wǎng)頁，M(pi)表示pi的入鏈集合，L(pj)表示pj的出鏈集合，N是所有頁面的數(shù)量，q是衰減因子，一般取0.85。根據(jù)經(jīng)典PageRank算法，網(wǎng)頁的PR值越高，說明它被訪問的概率越大，代表質(zhì)量較高。

將同一個網(wǎng)站內(nèi)的所有頁面合并成一個點，原圖的邊對應(yīng)到合并后的點，這樣構(gòu)成的新圖稱為站點鏈接關(guān)系圖。類似的，在站點鏈接關(guān)系圖中執(zhí)行PageRank算法，我們得到站點級別的PR值。

為了衡量網(wǎng)絡(luò)資源在收藏夾數(shù)據(jù)集中的重要程度，我們提出了收藏頻度CF(Collection Frequency)指標(biāo)。網(wǎng)頁收藏頻度CF(p)是指網(wǎng)頁p被不同用戶收藏的次數(shù)。

為了避免數(shù)據(jù)稀疏問題，需要使用站點級別的收藏頻度。我們認(rèn)為用戶收藏了網(wǎng)頁p，則表示用戶同時收藏了網(wǎng)頁p對應(yīng)的站點s。網(wǎng)站收藏頻度CF(s)是指站點s被不同用戶收藏的次數(shù)。

4.2 實驗與分析

第一步，通過搜索引擎公司獲得站點級別的鏈接關(guān)系，使用PageRank算法計算得到了全網(wǎng)的站點級PR值。這部分?jǐn)?shù)據(jù)總共涉及148 269 803個網(wǎng)站。

第二步，我們在收藏夾數(shù)據(jù)集中計算站點收藏頻度CF，這部分?jǐn)?shù)據(jù)包含個不同905 723個站點。從第一步的結(jié)果中，我們還能得到這部分站點對應(yīng)的PR值。

圖3(a)顯示了將全網(wǎng)站點PR值從高到低的排列情況。縱軸表示PR值，取值在0到1之間，橫軸是排名。曲線基本成線性，大致滿足冪律形式。最大值是0.003，最小值是1.03e-10。

圖3(b)顯示的是PR值的比例分布。橫軸是PR值，縱軸是比例，取值在0到1之間。其中，點狀符號對象是全網(wǎng)站點，加號符號則只包含了收藏夾數(shù)據(jù)集T中涉及的站點。根據(jù)圖3(b)，我們可以看出PR值是離散的，左上角的點狀符號表示全網(wǎng)中有62%的站點PR值等于最小值1.03e-10，這也是圖3(a)曲線右邊出現(xiàn)斷層的原因。對比兩種符號，兩者整體趨勢都是斜向下，在PR值小于10-8.5的區(qū)間內(nèi)，點狀符號要高于加號符號，而當(dāng)PR值大于10-8.5時，加號符號則遠(yuǎn)在點狀符號之上。這說明比起全網(wǎng)站點，收藏夾站點明顯更多地集中在PR值高端的部分，這也意味著用戶傾向于收集PR值較高的站點。

以上我們比較了收藏夾中的站點和全網(wǎng)站點的PR值分布差異，下面我們再來分析被用戶收藏的站點集合中收藏頻度CF與PR的關(guān)系。

圖3(c)的橫軸是CF值，縱軸是PR均值。函數(shù)f表示CF值為x的網(wǎng)站對應(yīng)的PR均值，定義如下：

可以看出， 整體而言，CF增大，對應(yīng)的PR均值增大。這個趨勢在CF小于100時尤為明顯。當(dāng)CF大于102.1后，圖像開始發(fā)散。這是因為CF越高，對應(yīng)的站點數(shù)量越少，PR均值也就越不穩(wěn)定了。

為了更好地看清PR均值隨著CF增大而增大這一趨勢，我們在圖3(c)基礎(chǔ)上將橫軸分段統(tǒng)計。圖3(d)將橫軸按對數(shù)坐標(biāo)系分成離散的100個桶，桶區(qū)間為[10x,10x+0.06)。函數(shù)h表示CF值在區(qū)間[10x,10x+0.06)中的網(wǎng)站對應(yīng)的PR均值，定義如下：

圖3(d)結(jié)果進一步證明了PR值有隨著CF值增長而增長的趨勢。結(jié)果表明，CF可以作為衡量網(wǎng)站質(zhì)量的參考之一。

5 收藏夾用戶興趣分析

5.1 開放式分類目錄ODP

為了分析用戶的興趣，我們借助了開放式分類目錄。 開放式分類目錄ODP(Open Directory Project)是目前網(wǎng)絡(luò)上最大的人工編制站點分類目錄。ODP維護了多層的目錄結(jié)構(gòu)，支持多語言版本。

本文工作主要分析中文用戶，于是我們下載了ODP中文版本。其中包含43 047個標(biāo)注站點，與收藏夾網(wǎng)站的交集大小為24 973。

5.2 實驗與分析

ODP目錄第一層包含14個類別： 計算機、商業(yè)、地區(qū)、藝術(shù)、游戲、參考、新聞、社會、休閑 、科學(xué)、購物、體育、健康、家庭。我們將這14類看成是興趣類別，利用標(biāo)注數(shù)據(jù)，將網(wǎng)站對應(yīng)到這14類興趣中去。

收藏夾網(wǎng)站的興趣類別分布如圖4(a)所示，其中計算機類的網(wǎng)站被用戶收藏得最多。圖4(b)展示了用戶興趣的多樣性。只對一個類別感興趣的用戶最多，占到了20%以上。同時感興趣的類別越多，用戶比例越少，同時對8個類別感興趣的用戶不到5%。

我們使用信息熵指標(biāo)，考察了用戶對興趣的離散程度。熵的計算公式如下：

圖4(c)顯示了用戶興趣熵的累積分布情況。熵值從0到3.5變化，興趣熵為0的用戶占到了20%左右，與圖4(b)中單興趣用戶對應(yīng)。曲線往后緩慢上升，顯示出大部分用戶的興趣還是比較集中的。

圖4 收藏夾用戶興趣分析

6 總結(jié)與未來展望

本文通過對大規(guī)模真實數(shù)據(jù)的統(tǒng)計處理，詳細(xì)分析了網(wǎng)絡(luò)用戶收藏行為的特點，圍繞三個核心問題給出了相關(guān)結(jié)論。

(1) 用戶怎樣收藏網(wǎng)頁

對收藏夾的結(jié)構(gòu)進行分析，發(fā)現(xiàn)大部分用戶的收藏夾呈“扁平型”，少部分用戶屬于“縱深型”和“平衡性”。為了衡量不同樹狀結(jié)構(gòu)的收藏夾的使用效率， 我們提出了收藏夾瀏覽點擊模型BBCM。該模型指出“平衡型”收藏夾能獲得較好的使用效率。將真實用戶的平均耗時期望與最小耗時期望相比，我們發(fā)現(xiàn)大部分用戶的收藏夾組織方式有很大改進空間。

(2) 用戶傾向于收藏哪些網(wǎng)頁

根據(jù)經(jīng)典PageRank算法，我們計算了站點級的PR值。將全網(wǎng)站點PR值與收藏夾站點PR值做比較，實驗指出，用戶傾向于收藏高質(zhì)量網(wǎng)站。在收藏夾站點集合內(nèi)，比較收藏頻度CF和PR，發(fā)現(xiàn)CF與PR有同樣的增長趨勢，可以作為衡量網(wǎng)站質(zhì)量的參考之一。

(3) 收藏夾用戶有什么興趣特點

借助開放式分類目錄ODP，我們對收藏夾用戶的興趣進行了分析，發(fā)現(xiàn)用戶對計算機類的網(wǎng)站最感興趣，80%左右的用戶會對兩個以上類別感興趣。

從興趣熵的變化來看，大部分用戶的興趣還是比較集中的。

未來我們將進一步分析哪些用戶的收藏行為更為可靠，更能為其他用戶提供借鑒，同時嘗試把本文研究結(jié)果應(yīng)用到反垃圾、網(wǎng)頁質(zhì)量評估、大規(guī)模網(wǎng)頁目錄構(gòu)建、用戶個性化等研究方向上。

[1] Liu Y., Gao B., Liu T., Zhang Y. et al. 2008. BrowseRank: Letting Web Users Vote for Page Importance[C]//Proceedings of the 31st ACM SIGIR Conference. 451-458.

[2] Liu Y., Zhang M., Ma S., Ru L., User Browsing Graph: Structure, Evolution and Application[C]//The 2nd ACM International Conference on Web Search and Data Mining (WSDM 2009).

[3] Silverstein C., Marais H., Henzinger M., Moricz M. 1999. Analysis of a very large web search engine query log[C]//SIGIR Forum 33, 1 (Sep. 1999), 6-12.

[4] Gyongyi Z., Garcia-Molina H. Web spam taxonomy[C]//First International Workshop on Adversarial Information Retrieval on the Web, 2005.

[5] Yiqun Liu, Rongwei Cen, Min Zhang, Shaoping Ma, Liyun Ru. Identifying Web Spam with User Behavior Analysis[C]//The Fourth International Workshop on Adversarial Information Retrieval on the Web.2008.4.

[6] N. Eiron， K.S. McCurley. Analysis of anchor text for Web search[C]//Proceedings of ACM SIGIR ’03, 2003.

[7] B. Mobasher, R. Cooley, J. Srivastava. Automatic personalization based on Web usage mining[J]. Communications of the ACM, (43) 8, August 2000.

[8] J. Feng, H. K. Bhargava, D. M. Pennock. Implementing sponsored search in web search engines: Computational evaluation of alternative mechanisms[J]. INFORMS Journal on Computing, 2005. Forthcoming.

[9] Stamou S., Krikos V., Kokosis P., Ntoulas A. and Christodoulakis D. Web directory construction using lexical chains[C]//Proceedings of the 10th NLDB Conference 2005, 138-149.

[10] Page L., Brin S., Motwani R.， Winograd T. The PageRank citation ranking: Bringing order to the web[R]. Available at http://dbpubs.stanford.edu:8090/pub/1999-66.