基于冪律分布的網(wǎng)絡(luò)用戶快速排序算法

張 玥，張宏莉，張偉哲

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

1 引言

隨著Web2.0的興起，計(jì)算機(jī)網(wǎng)絡(luò)將用戶從傳統(tǒng)的信息接收者轉(zhuǎn)變?yōu)樾畔⒅圃煺?，網(wǎng)絡(luò)論壇、博客、微博作為新興媒體對(duì)傳統(tǒng)媒體產(chǎn)生了極大沖擊，以前的社會(huì)影響主要由傳統(tǒng)媒體決定和控制，但新興媒體下用戶發(fā)布的一條信息就可能引發(fā)蝴蝶效應(yīng)，從天涯網(wǎng)絡(luò)論壇中大量長期的對(duì)“藥家鑫”事件的討論到“郭美美”的炫富微博，無不顯示出網(wǎng)絡(luò)用戶在新興媒體中“草根”階層對(duì)社會(huì)發(fā)展的積極影響。如何評(píng)價(jià)新興媒體中用戶的影響力是近年來社會(huì)網(wǎng)絡(luò)研究中的一個(gè)重要內(nèi)容，文獻(xiàn)[1]分析博客中用戶影響力，文獻(xiàn)[2-7]分析微博中用戶影響力，用戶影響力計(jì)算主要根據(jù)用戶的活躍性和受眾性以及發(fā)布的內(nèi)容，對(duì)社會(huì)網(wǎng)絡(luò)中的用戶進(jìn)行排序。文獻(xiàn)[8-10]量化了社會(huì)網(wǎng)絡(luò)中存在的影響力。文獻(xiàn)[11-12]對(duì)主題進(jìn)行區(qū)分量化了主題級(jí)用戶影響力。針對(duì)大規(guī)模數(shù)據(jù)下影響力計(jì)算困難性，文獻(xiàn)[11]采用分布式框架在Map-Reduce上量化影響力強(qiáng)度。

用戶影響力計(jì)算結(jié)果與對(duì)影響力的定義和分析有很大關(guān)系，文獻(xiàn)[4，7]中比較多種影響力計(jì)算方法，均認(rèn)為影響力值由計(jì)算方法決定。文獻(xiàn)[4]比較了twitter中利用粉絲數(shù)、依據(jù)粉線關(guān)系所形成的網(wǎng)絡(luò)拓?fù)洳捎肞agerank算法[13]、回復(fù)數(shù)三種方法的排序比較，前兩種方法都是反映了twitter用戶在twitter空間中的被認(rèn)識(shí)程度，該影響力是其綜合表現(xiàn)和社會(huì)傳播的結(jié)果，前兩種方法結(jié)果相似，但沒有明確反映出其內(nèi)容影響力，后者與前兩者結(jié)果不同，而依據(jù)回復(fù)數(shù)的排序結(jié)果僅部分反映了內(nèi)容影響力而未考慮到傳播的影響[1]。網(wǎng)絡(luò)用戶產(chǎn)生影響過程也是信息擴(kuò)散過程，從信息擴(kuò)散角度研究影響力包括文獻(xiàn)[14-15]等，文獻(xiàn)[14]分析博客空間中的鏈接模式，文獻(xiàn)[15]計(jì)算具有最在化影響力的少量用戶。博客、微博和網(wǎng)絡(luò)論壇信息傳播方式不同，博客、微博是根據(jù)用戶信息定制的定向推送式傳播；網(wǎng)絡(luò)論壇是公開的大眾用戶討論場所，基于服務(wù)器的集中式討論，網(wǎng)絡(luò)論壇中信息全部用戶可見。

早期應(yīng)用于Google搜索引擎的網(wǎng)頁排序算法Pagerank[1]利用網(wǎng)頁間鏈接關(guān)系構(gòu)造有向關(guān)聯(lián)圖，依據(jù)隨機(jī)游走和關(guān)聯(lián)圖的排序算法，網(wǎng)頁間的指向關(guān)系是網(wǎng)頁分值的主要依據(jù)。Pagerank算法設(shè)計(jì)思想也適用于網(wǎng)絡(luò)論壇中： 論壇中用戶A回復(fù)了用戶B是基于人主觀判斷后對(duì)B的一種認(rèn)同表現(xiàn)，因此我們認(rèn)為B對(duì)A產(chǎn)生了影響，而且論壇中主題內(nèi)用戶自然形成基于話題的社區(qū)。由此可根據(jù)主題內(nèi)用戶間回復(fù)關(guān)系，構(gòu)造用戶關(guān)聯(lián)圖，應(yīng)用Pagerank算法排序網(wǎng)絡(luò)用戶。但Pagerank算法沒有深入分析節(jié)點(diǎn)度分布，該算法運(yùn)行效率有提高空間。本文的研究問題。主要針對(duì)大規(guī)模的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)，在對(duì)用戶復(fù)雜排序應(yīng)用中如何提高數(shù)據(jù)的存儲(chǔ)和運(yùn)行效率。本文在網(wǎng)絡(luò)論壇中用戶度分布符合冪律特性，對(duì)Pagerank算法依據(jù)度分布進(jìn)行數(shù)據(jù)結(jié)構(gòu)優(yōu)化，按入度和出度進(jìn)行集合劃分，采用鏈表數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)基于集合劃分的快速排序算法SD-Rank。在天涯論壇上的用戶排序?qū)嶒?yàn)中，算法時(shí)空復(fù)雜性大大降低。

2 相關(guān)工作

1) Pagerank算法

經(jīng)典的網(wǎng)頁排序算法包括Pagerank算法[16]和HITS算法[17]。Pagerank算法根據(jù)頁面間指向關(guān)系迭代計(jì)算頁面的排序值，被大量指向的頁面其排序值高，排序值高的網(wǎng)頁所指向的頁面排序值也高，具有互增強(qiáng)特性；Pagerank算法還引入了隨機(jī)游走機(jī)制，即每次以一定的概率隨機(jī)選擇節(jié)點(diǎn)以防止進(jìn)入連通子圖中。Pagerank算法可表示為式(1)：

A是網(wǎng)頁間關(guān)聯(lián)矩陣，X是Pagerank迭代向量，X(0)是初始隨機(jī)游走向量，s是阻尼系數(shù)，1-s為隨機(jī)游走參數(shù)。歸一化后，網(wǎng)頁排序值最后收斂于特征值為1對(duì)應(yīng)的主特征向量，與X(0)無關(guān)，但X(0)影響算法迭代速度。

2) Pagerank改進(jìn)快速算法

提高Pagerank算法運(yùn)算速度主要從算法和數(shù)據(jù)兩個(gè)角度，文獻(xiàn)[18]總結(jié)了Pagerank算法的本質(zhì)： 節(jié)點(diǎn)rank值主要取決于連接該節(jié)點(diǎn)的邊，且在邊上僅傳遞rank值。文獻(xiàn)[18]加速計(jì)算方法： a)減少迭代次數(shù)法[19]。在計(jì)算排序值的收斂向量時(shí)，Pagerank的Power算法迭代次數(shù)取決于所選取的初始值X(0)。改進(jìn)算法： 迭代過程中修改迭代向量，令X(i+1)=X(i)+Z(i)使其快速逼近主特征向量，且迭代過程中利用啟發(fā)式修正Z向量；b)劃分?jǐn)?shù)據(jù)。按節(jié)點(diǎn)間連通性劃分為多個(gè)連通區(qū)域[9]，單遍迭代過程中，在節(jié)點(diǎn)間連接稠密區(qū)域可連續(xù)計(jì)算幾次再進(jìn)入下一連通區(qū)域繼續(xù)；c)減少計(jì)算量。當(dāng)節(jié)點(diǎn)間關(guān)聯(lián)圖隨時(shí)間變化時(shí)，若關(guān)聯(lián)圖變化不大可采用前一次rank結(jié)果作為啟發(fā)式來快速排序，當(dāng)節(jié)點(diǎn)rank值穩(wěn)定時(shí)不必進(jìn)行下輪迭代，僅對(duì)未收斂于穩(wěn)定概率分布的節(jié)點(diǎn)進(jìn)行迭代以減少計(jì)算量。

3) 本文思想

Pagerank算法本質(zhì)思想為在關(guān)聯(lián)網(wǎng)絡(luò)中以一定概率隨機(jī)選擇節(jié)點(diǎn)，然后在該節(jié)點(diǎn)沿出邊向外游走，節(jié)點(diǎn)rank值主要取決于連接該節(jié)點(diǎn)的邊，且在邊上僅傳遞rank值，該思想也適用于網(wǎng)絡(luò)用戶的影響力計(jì)算，但本文不同于文獻(xiàn)[18-19]，基于大量節(jié)點(diǎn)入度為0特點(diǎn)，對(duì)入度為0集合進(jìn)行優(yōu)化處理以減少存儲(chǔ)和運(yùn)輸復(fù)雜度。本文與上述Pagerank加速算法不同之處在于，基于網(wǎng)絡(luò)論壇中80%以上用戶入度為0的數(shù)據(jù)特征，提出基于入度是否為0進(jìn)行集合劃分來加速pagerank算法，而該數(shù)據(jù)特征和文獻(xiàn)[9]基于集合劃分思想一致。入度為0節(jié)點(diǎn)為論壇中僅發(fā)表評(píng)論，沒有引發(fā)別人評(píng)論的用戶，這類用戶對(duì)論壇的影響僅增加了帖子數(shù)量而沒有產(chǎn)生交互性影響，用戶實(shí)質(zhì)性影響表現(xiàn)為發(fā)表主題以及在主題中發(fā)表見解并引發(fā)正負(fù)面爭論。

3 網(wǎng)絡(luò)用戶快速排序算法

3.1 矩陣與圖的稀疏性

對(duì)于一個(gè)n×n矩陣，其存儲(chǔ)空間為n2。一個(gè)n階方陣與一個(gè)n維列向量相乘，運(yùn)算復(fù)雜度為O(n2)(需要n*(n個(gè)乘法+(n-1)個(gè)加法))。當(dāng)n數(shù)量級(jí)較大時(shí)存儲(chǔ)運(yùn)算開銷都較大。當(dāng)n×n矩陣中多數(shù)值為0時(shí)，為稀疏矩陣[20]。

3.2 關(guān)聯(lián)圖的鄰接表表示

稀疏圖可用鄰接表表示，如圖1所示。用鄰接表形式表示存儲(chǔ)空間小且計(jì)算復(fù)雜度低[21]。有向圖G=(V,E)可表示為一個(gè)包含|V|個(gè)鏈表的數(shù)組Adj。?u,v∈V，(u,v)∈E，則v在u的鄰接表中。圖G的鄰接表所需存儲(chǔ)空間為Θ(V+E)。

圖1 用戶關(guān)聯(lián)圖所對(duì)應(yīng)的鄰接表表示

3.3 基于鄰接表的Pagerank計(jì)算

根據(jù)Pagerank算法(式1)，圖G=(V,E)中節(jié)點(diǎn)v的rank值由兩部分而來。

1) 當(dāng)邊(u,v)∈E時(shí)，u的rank值rank[u]沿關(guān)聯(lián)矩陣游走，乘以因子s后按其出度均分到u所指向的節(jié)點(diǎn)，故v的rank值從指向其的節(jié)點(diǎn)u處傳播而來。當(dāng)多個(gè)點(diǎn)u1,u2,…，uk都指向v時(shí)，(u1,v)∈E，(u2,v)∈E，(u3,v)∈E,…(uk,v)∈E，Rank[v]=∑rank[ui]*s/out[ui]

2) 每個(gè)節(jié)點(diǎn)隨機(jī)游走所分的rank值，每個(gè)節(jié)點(diǎn)都乘以系數(shù)(1-s)后均分到所有節(jié)點(diǎn):

Rank[v]=(1-s)*∑(u∈G)rank[u]/n

Rank計(jì)算過程見算法1。

算法1基于鏈表方式的排序算法

Input (鏈表B，初始rank向量A0，出度向量out，阻尼系數(shù)s)

A1:迭代過程保存rank值向量，初始全0，,n節(jié)點(diǎn)數(shù)

A2： 上一次迭代rank向量，初始全0，e：rank向量收斂誤差，k迭代次數(shù)

function pagerank-iterate-computation(L,A0)

1 while (||A0-A2||2

2 { rank=0; A2=A1；

3 For (i=1 , i++, i<=n) rank=rank+

A0[i];

4 For (i=1 , i++, i<=n) A1[i]=rank*(1-s)/n;

5 For (count=0;count++;count

6 { While (當(dāng)B[count]鏈表未考察結(jié)束) //邊數(shù)

7 { read j //(i,j)?E

8 A1[j]= A1[j]+A1[count]′s/out[count];

9 }

10 }

11 A0=A1；

12 } Output A0

算法2基于SD-Rank的集合部分排序算法

Compute-rank-b0 計(jì)算b0桶中rank值的分配

{ 1 max-out=1; //出度最大值

2 For (A[v]=w) //對(duì)B0中節(jié)點(diǎn)v的鄰接表按出度放入相應(yīng)的桶中

3 { i=out[v];

4 Insert List v into B0[i];

//插入排序，排序時(shí)計(jì)算節(jié)點(diǎn)出現(xiàn)次數(shù)

5 If (i>max-out ) max-out=i;

6 }

7 For(i=1 to max-out)

8 { while list B0[i] is not null

9 { read 節(jié)點(diǎn)j and weight[j];

10 A1[j]= A1[j]+A0[k]′s′weight[j]/i;

//節(jié)點(diǎn)k入度=0 } }

3.4 基于集合劃分的SD-rank改進(jìn)算法

定義1： 入度為0的點(diǎn)所構(gòu)成的集合稱為set0；入度大于0的點(diǎn)所構(gòu)成的集合稱為set1。

定義2： 由入度為0的點(diǎn)所引發(fā)的邊的集合為edges0。其他邊的集合為edges1。edges0集合即由set0中節(jié)點(diǎn)指向set1中節(jié)點(diǎn)所構(gòu)成的邊。edges1集合即由set1集合內(nèi)部節(jié)點(diǎn)間關(guān)聯(lián)所構(gòu)成的邊。

性質(zhì)1點(diǎn)集合set0和set1不相交，且點(diǎn)的總集由set0和set1構(gòu)成，setV=set0∪set1。

性質(zhì)2邊集合edges0和edges1不相交，且edgesE=edges0∪edges1。

關(guān)聯(lián)圖的點(diǎn)集合和邊集合劃分后如圖2所示。set1集合中節(jié)點(diǎn)影響力值： 1)由隨機(jī)游走；2)由集合內(nèi)部相互指向得到；3)由集合0節(jié)點(diǎn)指向得到。

圖2 關(guān)聯(lián)圖基于入度的集合劃分

3.4.1 集合劃分后進(jìn)行優(yōu)化

Set0中節(jié)點(diǎn)入度為0，若其初始rank值相同，出度相同時(shí)其向外傳播的rank值也相同，按出度值重新劃分桶，那么鏈接表中數(shù)組B的元素?cái)?shù)降低到set0的出度數(shù)。Set0中出度相同的節(jié)點(diǎn)指向相同節(jié)點(diǎn)時(shí)，累計(jì)指向節(jié)點(diǎn)出現(xiàn)次數(shù)，鄰接表采用加權(quán)表示，如圖3所示。集合劃分可采用對(duì)節(jié)點(diǎn)著色法表示，set0集合用w表示；set1點(diǎn)顏色為用b表示。對(duì)set0集合引發(fā)的edges0邊集合，應(yīng)用加權(quán)鄰接表表示后的rank計(jì)算過程見算法2。

圖3 入度為0的節(jié)點(diǎn)加權(quán)鄰接表表示

3.4.2 運(yùn)算復(fù)雜性分析

對(duì)B0鏈表的運(yùn)算復(fù)雜度分析：Compute-rank-b0的第二行對(duì)B0中節(jié)點(diǎn)進(jìn)行處理，循環(huán)了count_b0次；第四行采用插入排序法鏈接到第i個(gè)桶，最少插入i次，最多插入count_b1次；第7行循環(huán)了max-out次；第八行同第四行。運(yùn)算復(fù)雜度

令c=count_b1

對(duì)T(n)等式兩邊取數(shù)學(xué)期望，有

令Xij=I{A[j]落入桶i中},i∈[1,max-out]，j∈[1,c]。

對(duì)B0桶進(jìn)行改進(jìn)后，運(yùn)算復(fù)雜度下降到Θ(count_b1)。count_b1為入度不為0用戶數(shù)量。即： 對(duì)入度為0節(jié)點(diǎn)按其出度值劃分桶后其運(yùn)行復(fù)雜度為Θ(|set1|)。

4 實(shí)驗(yàn)結(jié)果

4.1 數(shù)據(jù)描述

天涯網(wǎng)絡(luò)論壇是中國門戶網(wǎng)絡(luò)論壇，用戶活躍，內(nèi)容廣泛，部分主題討論深入交互性好。實(shí)驗(yàn)數(shù)據(jù)集采集自天涯網(wǎng)絡(luò)論壇天涯雜談版塊，采用工具為實(shí)驗(yàn)室開發(fā)的爬蟲軟件，于2010年12月21日按主題進(jìn)行廣度爬行。過濾掉回復(fù)數(shù)少于50的主題。抽取了11月26日到12月7日共12天的數(shù)據(jù)進(jìn)行了測試。數(shù)據(jù)按天劃分，提取出用戶間回復(fù)關(guān)系，默認(rèn)情況下回復(fù)給主題創(chuàng)建者。統(tǒng)計(jì)結(jié)果如表1所示。

表1 數(shù)據(jù)集統(tǒng)計(jì)

4.2 入度和出度統(tǒng)計(jì)結(jié)果

統(tǒng)計(jì)11月26日到12月7日的入度為0用戶數(shù)及所占比例，如圖4所示。圖4左為日入度為0和出度為1用戶數(shù)量，圖4右為日入度為0和出度為1用戶占總數(shù)比例。平均日入度為0用戶數(shù)5 566。入度為0用戶占總?cè)藬?shù)日平均比例為86.16%。出度為1用戶數(shù)日平均4 430人。出度為1用戶占總?cè)藬?shù)日平均比例為64.98%。

圖4 入度為0和出度為1日用戶數(shù)統(tǒng)計(jì)及相對(duì)比例

選取11月23日作為樣本點(diǎn)，統(tǒng)計(jì)入度和入度的頻數(shù)、出度和出度的頻數(shù)。圖5為用戶入度頻數(shù)、出度頻數(shù)對(duì)數(shù)坐標(biāo)圖，由圖可看出入度、出度符合冪律分布。文獻(xiàn)[22-23]分析了web入度符合冪律分布，web入度為k的概率與1/ka(2

圖5 11月23日度對(duì)數(shù)對(duì)數(shù)分布圖

4.3 SD-Rank算法和Pagerank算法運(yùn)行結(jié)果比較

圖6 比較兩種算法排序結(jié)果相似性

為考察SD-Rank算法和Pagerank算法排序結(jié)果的相似性，采用Kendall’s tau排序相關(guān)性比較的改進(jìn)公式[4，25-26]比較排序結(jié)果差異，Kendall’s tau公式為：

0≤K≤1，K=0表示R1和R2排序結(jié)果完全不同，K=1表示R1和R2排序結(jié)果完全相同。

圖6所示為Kendall’s tau排序相似性比較結(jié)果，K值在0.7以上，說明SD-Rank與Pagerank排序結(jié)果相似性大。表2為用戶排序結(jié)果top5明細(xì)，兩種算法top5結(jié)果相同。

表2 11月23-24日排序top5用戶結(jié)果

4.4 SD-Rank算法運(yùn)行效率

比較運(yùn)行Pagerank和SD-Rank算法的運(yùn)行時(shí)間。運(yùn)行時(shí)間對(duì)比如圖7左所示提高4-30s。運(yùn)行效率提高比例如圖7右所示。SD-Rank算法運(yùn)行效率平均提高了39%。

圖7 算法運(yùn)行時(shí)間和SD-Rank提高效率

5 結(jié)論

本文以網(wǎng)絡(luò)論壇為用戶排序應(yīng)用背景，提取用戶關(guān)聯(lián)圖。基于用戶度符合冪律分布，改進(jìn)Page-rank 算法，將用戶劃分為入度是否為0的兩個(gè)集合。對(duì)入度為0的用戶集合，再按出度構(gòu)造鏈接表，采用加權(quán)鏈接數(shù)據(jù)結(jié)構(gòu)?；诙确植歼M(jìn)行集合劃分，加權(quán)鏈接結(jié)構(gòu)的SD-Rank算法，時(shí)空復(fù)雜度降低為O(V′)，V′為入度不為0節(jié)點(diǎn)集合，大大降低了排序的存儲(chǔ)空間和運(yùn)行效率。

[1] Agarwal N., Liu H., Tang L.， et al. Identifying the influential bloggers in a community[C]//Proceedings of the international conference on Web search and web datamining(ICWSM ’08),New York, US, ACM, 2008:207-218.

[2] Paul N. Bennett, Krysta Svore, Susan T. Dumais.Classification-enhanced Ranking[C]//Proceedings of the 19th international conference on World Wide Web, Raleigh, NC, USA, 2010:111-120.

[3] T. L. Fond, J. Neville. Randomization Tests for Distinguishing Social Influence and Homophily Effects[C]//Proceedings of the 19th international conference on World Wide Web, Raleigh, NC,USA, 2010:601-610.

[4] H. Kwak, C. Lee, H. Park, et al. What is Twitter, a Social Network or a News Media[C]//Proceedings of the 19th international conference on World Wide Web, Raleigh, NC, USA, 2010:591-600.

[5] S. Wu, J. M. Hofman, W. A. Mason, et al. Who says What to Whom on Twitter[C]//Proceedings of the 20th international conference on World Wide Web, Madrid, India, 2011:705-714.

[6] M. Cha, H. Haddadi, F. Benevenuto, e al. Measuring user influence on wtitter: The million follower fallacy[C]//Proceedings of the 4th International AAAI Conference on Weblogs and Social Media, Washington DC, 2010.

[7] J. Weng, E. P. Lim, J. Jiang, et al. Twitterrank: finding topic-sensitive influential twitterers[C]//Proceedings of the 4th ACM international conference on Web search and data mining(WSDM), 2010:261-270.

[8] Dan Cosley, D. Huttenlocher,Jon Kleinberg,et al. Sequential Influence Models in Social Networks[C]//Proceedings of the International Conference on Weblogs and Social Media(ICWSM), 2010.

[9] A. Anagnostopoulos, R.Kumar, M. Mahdian. Influence and correlation in social networks[C]//Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining,2008:7-15.

[10] P. Singla, M. Richardson. Yes, there is a correlation: from social networks to personal behavior on the web[C]//Proceedings of the 17th international conference on World Wide Web, 2008:655-664.

[11] Jie Tang, Jimeng Sun, Chi Wang, et al. Social Influence Analysis in Large-scale Networks[C]//Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, 2009:721-730.

[12] Aditya Pai, Scott Counts. Identifying Topical Authorities in Microblogs[C]//Proceedings of the fourth ACM international conference on Web search and data mining(WSDM ), 2011:45-54.

[13] J. Leskovec, E. Horvitz. Planetary-scale views on a large instant-mssaging network[C]//Proceedings of the 17th international conference on World Wide Web. Beijing, China, 2008:915-924.

[14] D. Kemp, J.Kleinberg, E. Tardos. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, 2003:137-146.

[15] S Brin. L Page, R Motwani, T Winograd. The pagerank citation ranking: Bringing order to the web[R]. Technical report, Stanford University, 1999.

[16] J Kleinberg. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM, 1999,46(5):604-632

[17] Frank Mcsherry. A uniform Approach to Accelerated Pagerank Computation[C]//Proceedings of the 14th international conference on WWW, 2005:575-582.

[18] Sepandar D. Kamvar, T H. Haveliwala, C D. Manning, et al. Extrapolation Methods for Accelerating Pagerank[C]//Proceedings of the 12th international conference on WWW, 2003:261-270.

[19] Stoer Josef, R. Bulirsch. Introduction to Numerical Analysis[M]. Berlin, Dover Publications. 2002: 619

[20] Thomas A. Smith. The web of law[J]. San Diego Law Review,2007，44(309).

[21] A. Broder, R. Kumar, F. Maghoul, et al. Graph structure in the Web[C]//Proceedings of the 9th International World Wide Web Conference, 2000:309-320.

[22] David Easley, Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World[M]. Cambridge University Press, 2010. P546

[23] R. Fagin, R.Kumar, D. Sivakumar. Comparing top k lists[C]//Proceedings of the 14th annual ACM-SIAM symposium on discrete algorithms,2003:28-36.

[24] F. McCown, M. L. Nelson. Agreeing to disagree: search engines and their public interfaces[C]//Proceedings of the 7th ACM/IEEE-CS joint conference on digital libraries. ACM,2007:309-318.

[25] Thomas H. Cormen, Charles E.Leiserson, Ronald L. Rivest, et al. Introduction to Algorithms[M]. The MIT Press.2001. P527

[26] N. Agrawal, H. Liu, L. Tang, et al. Identifying the Influential Bloggers in a Community[C]//Proceedings of the international conference on Web search and web data mining(WSDM’08), 2008:207-218.