張 玥，張宏莉，張偉哲

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

1 引言

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

用戶影響力計算結(jié)果與對影響力的定義和分析有很大關(guān)系，文獻[4，7]中比較多種影響力計算方法，均認為影響力值由計算方法決定。文獻[4]比較了twitter中利用粉絲數(shù)、依據(jù)粉線關(guān)系所形成的網(wǎng)絡(luò)拓撲采用Pagerank算法[13]、回復(fù)數(shù)三種方法的排序比較，前兩種方法都是反映了twitter用戶在twitter空間中的被認識程度，該影響力是其綜合表現(xiàn)和社會傳播的結(jié)果，前兩種方法結(jié)果相似，但沒有明確反映出其內(nèi)容影響力，后者與前兩者結(jié)果不同，而依據(jù)回復(fù)數(shù)的排序結(jié)果僅部分反映了內(nèi)容影響力而未考慮到傳播的影響[1]。網(wǎng)絡(luò)用戶產(chǎn)生影響過程也是信息擴散過程，從信息擴散角度研究影響力包括文獻[14-15]等，文獻[14]分析博客空間中的鏈接模式，文獻[15]計算具有最在化影響力的少量用戶。博客、微博和網(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ù)隨機游走和關(guān)聯(lián)圖的排序算法，網(wǎng)頁間的指向關(guān)系是網(wǎng)頁分值的主要依據(jù)。Pagerank算法設(shè)計思想也適用于網(wǎng)絡(luò)論壇中： 論壇中用戶A回復(fù)了用戶B是基于人主觀判斷后對B的一種認同表現(xiàn)，因此我們認為B對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é)點度分布，該算法運行效率有提高空間。本文的研究問題。主要針對大規(guī)模的社會網(wǎng)絡(luò)數(shù)據(jù)，在對用戶復(fù)雜排序應(yīng)用中如何提高數(shù)據(jù)的存儲和運行效率。本文在網(wǎng)絡(luò)論壇中用戶度分布符合冪律特性，對Pagerank算法依據(jù)度分布進行數(shù)據(jù)結(jié)構(gòu)優(yōu)化，按入度和出度進行集合劃分，采用鏈表數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)基于集合劃分的快速排序算法SD-Rank。在天涯論壇上的用戶排序?qū)嶒炛?，算法時空復(fù)雜性大大降低。

2 相關(guān)工作

1) Pagerank算法

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

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

2) Pagerank改進快速算法

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

3) 本文思想

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

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

3.1 矩陣與圖的稀疏性

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

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

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

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

3.3 基于鄰接表的Pagerank計算

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

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

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

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

Rank計算過程見算法1。

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

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

A1:迭代過程保存rank值向量，初始全0，,n節(jié)點數(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 計算b0桶中rank值的分配

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

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

3 { i=out[v];

4 Insert List v into B0[i];

//插入排序，排序時計算節(jié)點出現(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é)點j and weight[j];

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

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

3.4 基于集合劃分的SD-rank改進算法

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

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

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

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

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

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

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

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

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

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

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

令c=count_b1

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

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

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

4 實驗結(jié)果

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

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

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

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

統(tǒng)計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)計及相對比例

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

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

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

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

為考察SD-Rank算法和Pagerank算法排序結(jié)果的相似性，采用Kendall’s tau排序相關(guā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明細，兩種算法top5結(jié)果相同。

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

4.4 SD-Rank算法運行效率

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

圖7 算法運行時間和SD-Rank提高效率

5 結(jié)論

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

[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.