結合時間因子的校園論壇用戶影響力分析方法研究

謝國豪+羅浩+吳志剛+張樹壯

摘要：針對如何在高校論壇中識別出高影響力用戶的問題，提出了一種結合時間因子的論壇用戶影響力計算方法。在PageRank算法的基礎上，通過分析論壇用戶回帖行為隨時間變化的規律引入用戶影響力的衰減系數，并根據用戶間的交互情況，通過用戶間的交互次數和用戶主題參與度來優化用戶影響力的分配形式。實驗結果表明：在相同時間段內，改進后的算法相對于PageRank算法能夠識別出具有更強中心性特性和更高用戶覆蓋率的高影響力用戶。在連續時間段上，通過引入衰減系數能夠發掘當前真正具有影響力的用戶并保持穩定的用戶覆蓋率。

關鍵詞： 影響力； 時間因子； 衰減系數； 主題參與度； 中心性特性； 覆蓋率

中圖分類號：TP393

文獻標碼：A

文章編號：2095-2163（2017）05-0013-04

XIE Guohao， LUO Hao， WU Zhigang， ZHANG Shuzhuang

（Institute of Network Technology， Beijing University of Posts and Telecommunications， Beijing 100876， China）

Abstract：

In order to identify high-impact users in the campus forums， an algorithm combined with time factor is proposed. Based on PageRank algorithm， the attenuation coefficient of user′s influence is introduced by analyzing the change law of user′s reply behavior， and the propotion of user′s influence assigned to others is determined by the number of interactions between users and user′s subject participation. Experimental results indicate that the improved algorithm can identify the influential users with higher centrality and user coverage ratio than PageRank algorithm in the same time period. In the continuous period of time， by introducing the attenuation coefficient， the real high-impact users can be identified and stable user coverage ratio can be maintained.

Keywords： influence； time factor； attenuation coefficient； subject participation； centrality； coverage ratio

基金項目： 家重點研發計劃資助項目（2016YFB0801200）。

收稿日期： 2017-08-27

0引言

隨著移動互聯網的發展和普及，在線社交網絡已經深刻地影響了人們的生活方式。高校網絡論壇作為在線社交網絡的重要組成部分，憑借其以高校為背景的區域性特征以及當今大學生思想交流活動頻繁的特性，吸引了大量師生參與到論壇交流中。考慮到高校論壇的參與對象以及自由開放的討論空間，識別出高校網絡論壇中具有高影響力的用戶對于信息的傳播和引導具有重要的意義。

PageRank作為經典的頁面排名算法是基于網頁及其鏈接構成的全局拓撲結構，依據網頁間的鏈接關系和隨機游走思想對網頁進行重要度計算和排序[1]。社交網絡與網頁鏈接網絡具有相似的拓撲結構，用戶在社交網絡中活動產生交互關系，這種關系會隨著用戶活動而不斷累積，若直接利用PageRank算法對用戶影響力進行計算，顯然在社交網絡中存在時間較長的用戶有更大的可能擁有較多的鏈入關系從而獲得更高的影響力值，即使用戶之后不再產生任何行為，這種全局關系仍然會使用戶在影響力計算中取得較大的值而非呈現減弱的趨勢。同時在PageRank算法中，網絡拓撲中的節點平等對待其它所有節點，以平均分配的方式分配其權值從而導致忽略了節點之間的差異性對最后計算結果的影響。

針對以上問題，本文提出了一種結合時間因子的用戶影響力計算方法，通過收集到的高校論壇數據對算法進行了實驗和對比，驗證了改進后的算法能夠更加準確識別出具有高影響力的用戶群。

1相關工作

社會網絡作為一門交叉性學科，已經被SIGKDD、WWW等多個重要的國際會議列為研究議題[2-3]，且形成了一個專門的研究方向——社會網絡分析（Social Network Analysis，SNA）。社會影響力排序作為社會網絡研究的子領域吸引了大量學者參與研究，不同學者從不同的角度對用戶影響力進行研究。如Zhang等人通過對網絡BBS構建回復網絡，分析節點中心性來發現處于網絡中心位置的用戶[4]。Meeyoung Cha等人從粉絲數、轉發數、引用數這3個指標來評定Twitter上的用戶影響力[5]。Weng等人利用社交網絡中用戶之間的關注關系來構建轉發網絡，提出了TwitterRank算法[6]。Zhai等人通過對論壇中用戶發表內容進行所屬興趣域的劃分來識別用戶的影響力[7]，Matsumura等人提出了IDM模型，考慮論壇帖子中關鍵詞在對話鏈中的傳遞來反映影響力[8]，Hu等人針對Twitter提出了TAP算法，根據轉發內容與給定主題間的相似度計算用戶在給定主題下的影響力權重[9]。endprint

本文從時間維度對社交網絡中的用戶影響力衰減規律進行分析，并在影響力計算公式中引入衰減系數，同時通過改進PageRank算法中節點權值的分配方式來對PageRank進行優化，以此分析用戶的影響力。

2結合時間因子的影響力計算

2.1數據集說明

本文以北郵人論壇的數據作為算法改進和實驗的基礎。數據主要由用戶信息和主題帖信息構成，其中用戶信息包括參與過發帖或者回帖的用戶數目。主題帖信息包括正文和后續的跟帖內容，以及正文和跟帖的發布時間和作者信息，同時整理出了用戶之間的交互關系。

本文收集到的數據集包含了自2004年11月份至2017年3月份的全部相關數據。具體的數據集描述如表1所示。

3實驗結果與分析

3.1評價指標

社會網絡分析中普遍認為全局網絡中具有高影響力的節點具有高中心性，并提出以中心性測度（Centrality measures）作為判斷網絡中節點重要性的指標來對節點重要性進行量化 [13]。緊密中心性（Closeness Centrality）[14]作為中心性的度量方法之一，當節點具有更高的緊密中心性時表示該節點處于中心位置[4]并且具有更高傳遞影響的能力，刻畫了節點的全局重要性[15]。

本文以節點緊密度的大小排序作為基準排序，通過計算不同算法識別的影響力Top N用戶集合相對于基準排序的召回率來對算法進行評價。同時鑒于高影響力人物往往能夠影響更多的用戶，參考文獻[7，16]引入覆蓋率指標（Coverage Ratio）。

3.2實驗結果分析

3.2.1單個時間段內的結果對比

以節點緊密度為指標，對相同時間段內的用戶進行排序并作為基準，考察不同算法在相同時間段內識別出的用戶集合相對基準排序的召回率，召回率越高則說明結果越接近基準排序。得到2種算法的召回率結果如圖2所示，從圖2中可知，在取相同比例Top N的用戶進行對比的前提下，TUR算法相對基準算法具有較高召回率，說明其識別的用戶群體相對于PageRank算法所識別的用戶群體具有更高的中心性。

同時，考察2種算法識別出的Top N前50%的用戶的覆蓋率。結果如圖3所示，在相同比例的Top N用戶群體中，TUR算法識別的高影響力用戶相對于PageRank算法識別的高影響力用戶具有更高的覆蓋率，表明利用TUR算法識別的用戶群所具有的影響力能夠覆蓋更多用戶，影響范圍更廣。

3.2.2連續時間段上影響力變化

本文選取了2016年1月1日到12月31日為期一年的所有數據進行研究，在該時間段上分析了排名前5%的高影響力用戶的覆蓋率變化情況。結果如圖4所示。從圖4中可以看出，利用TUR算法識別的排名前5%的用戶覆蓋率，隨著時間的發展變化波動較小，趨勢線趨于平穩，總體保持較穩定的覆蓋率。而利用PageRank算法所識別的排名前5%的用戶覆蓋率，隨著時間的發展整體呈下降趨勢。究其原因，TUR算法在計算公式中引入了衰減系數，通過篩選當前時間段內活躍用戶并淘汰長期無作為的用戶，來保持高影響力用戶群的影響覆蓋率。而在PageRank算法計算中，一些不再參與論壇活動但曾經活躍的用戶因為之前積累了大量的交互關系仍然獲得了較大的影響力值并占據較高的排名，這些用戶不再產生新的交互，其影響的用戶數量始終保持不變，隨著論壇中新用戶的不斷增多從而導致了覆蓋率下降。說明了衰減系數的引入有助于更好地識別活躍的高影響力用戶。

4結束語

本文提出一種結合時間因子的論壇用戶影響力計算算法Time-User Rank。在PageRank算法基礎上結合時間因子引入影響力的衰減系數，以及通過用戶間的交互權重和用戶的主題參與度，針對PageRank算法中對節點影響力均分分配的問題做出了相關優化。通過實驗表明，在同一個時間段內改進后的算法相對于PageRank算法能夠識別得到具有更高的中心性特性和用戶覆蓋率的高影響力用戶群體，并且在連續時間段上能夠通過影響力衰減系數有效地挖掘出活躍且具有高影響力的用戶，使整個高影響力用戶群始終保持穩定的用戶覆蓋率。

參考文獻：

PAGE L， BRIN S， MOTWANI R，et al. The PageRank citation ranking： Bringing order to the web[J]. World Wide Web Internet And Web Information Systems， 1998， 54（1999）： 1-17.

[LL]

[2] TANG Jie， SUN Jimeng， WANG Chi， et al. Social influence analysis in large-scale networks[C]Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. Paris， France：ACM， 2009： 807-816.

[3] KWAK H， LEE C， PARK H， et al. What is Twitter， a social network or a news media？[C]The 19th international conference on World Wide Web. Raleigh， North Carolina， USA ：ACM， 2010： 591-600.

[4] ZHANG Ke， LI Hui， QIN Lijuan， et al. Closeness centrality on BBS reply network[C] International Conference on Information Technology， Computer Engineering and Management Sciences. Nanjing， Jiangsu， China：IEEE， 2011： 80-82.endprint

[5] CHA M， HADDADI H， BENEVENUTO F， et al. Measuring user influence in twitter： The million follower fallacy[C]Proceedings of the Fourth International Conference on Weblogs and Social Media， ICWSM 2010. Washington， DC， USA：DBLP， 2010： 10-17.

[6] WENG Jianshu， LIM E P， JIANG Jing， et al. TwitterRank： Finding topic-sensitive influential twitterers[J]. Proceedings of the third ACM international conference on Web search and data mining. New York， USA：ACM， 2010： 261-270.

[7] ZHAI Zhongwu， XU Hua， JIA Peifa. Identifying opinion leaders in BBS[C]WI-IAT '08 Proceedings of the 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology . Washington， DC， USA ：IEEE， 2008： 398-401.

[8] MATSUMURA N. Topic diffusion in a community[M]OHSAWA Y， MCBURNEY P. Chance Discovery . Advanced Information Processing. Berlin/Heidelberg：Springer， 2003： 84-97.

[9] [JP3]HU Jian， FANG Yi， GODAVARTHY A. Topical authority propagation on microblogs[C][JP] Proceedings of the 22nd ACM international conference on Information & Knowledge Management. San Francisco， California， USA：ACM， 2013： 1901-1904.

[10]AGARWAL N， LIU Huan， TANG Lei， et al. Identifying the influential bloggers in a community[C] WSDM '08 Proceedings of the 2008 International Conference on Web Search and Data Mining. Palo Alto， California， USA：ACM， 2008： 207-218.

[11]GOTZ M， LESKOVEC J， MCGLOHON M， et al. Modeling blog dynamics[C] AAAI Conference on Weblogs and Social Media （ICWSM）. San Jose， California：AAAI， 2009： 26-33.

[12]BOLDI P， SANTINI M， VIGNA S. PageRank as a function of the damping factor[C]WWW '05 Proceedings of the 14th international conference on World Wide Web. Chiba， Japan：ACM， 2005： 557-566.

[13]NEWMAN M E J. Networks： An introduction[M]. Oxford： Oxford University Press， 2010.

[14]FREEMAN L C. Centrality in social networks conceptual clarification[J]. Social Networks， 1978， 1（3）： 215-239.

[15]TRAVERS J， MILGRAM S. The small world problem[J]. Phychology Today， 1967， 1：61-67.

[16]SONG Xiaodan， CHI Yun， HINO K， et al. Identifying opinion leaders in the blogosphere[C]Proceedings of the sixteenth ACM Conference on information and knowledge management.Lisbon， Portugal ：ACM， 2007：971-974endprint