基于Peoplerank的微博用戶可信度排序算法

李文政， 張云飛， 周思琪， 李鑫

(河海大學 計算機與信息學院，南京 211100)

基于Peoplerank的微博用戶可信度排序算法

李文政， 張云飛， 周思琪， 李鑫

(河海大學 計算機與信息學院，南京 211100)

為了提升微博用戶可信度排序的穩定性與合理性，結合Peoplerank的基本思想，提出了一種基于用戶關注圈特征的微博用戶可信度評估的算法。引入用戶關注圈平衡特征作為rank值傳遞的影響因子，優化了用戶rank值的傳遞過程，對每次迭代過程中的rank值的進行加權和修正。實驗結果表明，該算法對不同規模的社交用戶數據集具有良好的適應性，對用戶可信度的排序和評估更加合理。

微博； 用戶可信度； Peoplerank； 排序； 關注圈

0 引言

自互聯網誕生以來，微博作為一種新興的社交網絡形式，其規模和應用領域日益發展壯大，成為一種重要的日常溝通工具。在方便人們交流的同時，微博用戶量和信息量的不斷增加也帶來了一系列的挑戰，例如垃圾信息泛濫、謠言擴散、群體性事件產生與傳播，“僵尸粉”，“偽專家”等，因此研究微博用戶的可信度具有重要的價值。現有微博信息可信度的研究方法多以分析微博用戶的特征為主，運用分類或排序方法對其可信度進行評估[1]。

從社交網絡理論的角度看，一個用戶對另外一個用戶的可信度能通過他們之間的關注產生變化和影響。新浪微博的網絡結構類似于 Web頁面的網絡結構。評估 Web頁面的權威性排序的算法有 PageRank 算法、HITS 算法等。因此有學者提出把pagerank模型應用于社交網絡。Mtibaa等基于此思路提出了peoplerank模型，以用于以人為本的社交網絡用戶影響力的評估[2]。Gupta等提出基于事件圖和pagerank 算法計算Twitter 事件可信度[3]。

國內對于基于鏈接分析微博用戶可信度的研究雖然比較晚，但也取得了不少成果。唐飛龍等提出的基于用戶質量的微博社區博主影響力排序算法就是以pagerank算法為基礎的[4]。劉耀庭根據指出了用戶影響力評價中的一個重要指標是用戶的好友數量[5]。王峰等提出的用于評估用戶可信度的userrank模型中，用戶粉絲對其影響力的貢獻值是模型中重要的參數[6]。用戶可信度是用戶影響力的基礎，通常情況下，兩者處于正相關的關系，這是userrank實現的前提。然而用戶可信度不僅僅體現在用戶的粉絲這一個方面，此外還應該考慮用戶關注社區的質量上。

綜上所述，已有的用戶可信度評價方法的研究成果存在其合理性的一面，但在實踐中還存在著兩個問題，一是基于用戶的關注群很大程度上并非是等效信用值的傳遞過程，按照傳統peoplerank算法計算會導致基于用戶同一社區的排名缺乏區分度，二是在實際應用過程中所獲得的數據往往存在大量的缺失數據，這些大量的缺失數據無法對可信度進行有效的運算但作為權值分配的分母時會大大稀釋全局的權值，導致最后的排名結果會出現偏差，這種偏差在數據集規模越小時越突出。

通過研究發現在計算可信度排名時以社區化的關注圈的概率特征作為用戶信用度的影響因子可以對排序的結果進行偏差修正，從而解決上述的問題。

1 相關知識

1.1 用戶可信度和用戶影響力

用戶影響力表示用戶在社交網絡中進行信息傳播的能力大小，一個高影響力用戶通常是由于其社區活躍度高，擁有數量龐大的粉絲，使其成為信息傳播的關鍵節點。微博名人就是高影響力的用戶的代表，一些微博信息經過他們轉發之后會快速地進行傳播。

用戶可信度表示用戶在社交網絡中的真實性和可信任性的大小，一個高可信度的用戶通常是因為擁有真實的信息資料，高質量的微博內容和高質量的粉絲。

用戶可信度是用戶影響力的基礎，通常情況下，兩者處于正相關的關系。但有的時候一個影響力不高的用戶，可信度未必也低，例如一個普通用戶的影響力可能遠遠低于微博名人，但是他的可信度未必會低于微博名人；同樣一個可信度不高的用戶，影響力也不一定會低，例如有人可以通過社交網絡來廣泛傳遞謠言等不實信息。從社交網絡結構上看，用戶影響力更多的是單考慮了粉絲數這一個因素，而用戶可信度卻一種新的概念，不僅僅是考慮粉絲的數量，粉絲的質量對其可信度的影響更為突出。

1.2 社交網絡社區理論

社交網絡用戶之間的信任產生和傳遞是屬于社會學和心理學的研究范疇[7]。社交網絡是一種知識共享、興趣交流的平臺，所謂物以類聚，人以群分，人們總是傾向于跟自己在態度、興趣、價值觀、背景和人格上和自己相似的人進行在線社交[8]，形成了一個個“圈子”，這些“圈子”便是根據用戶的興趣傾向和所屬知識領域而劃分的社區[9]，盡管學術界沒有給社區一個明確的定義，但普遍認為社區具有以下特點：社區是網絡的一個子圖，在同一個社區內的用戶節點，交流更加頻繁和緊密，而相對來說，社區之間的交互卻稀疏的多[10]。

圖1為一個簡易社區結構示意圖。

圖1 簡易的社區結構示意圖

左邊和右邊分別是一個是某知識領域或者共同興趣形成的社區結構，雖然它們的規模不同，但是社區內部之間存在大量的連接，而社區之間的關系則相對比較稀疏，這些連接不僅僅是簡單的關注關系，更是一種用戶間認可和信任的表現形式，因此可以通過用戶所在的社區整體的特點，來判斷用戶信用高低。

2 算法模型

2.1 Peoplerank算法思想

Pagerank算法將Web看成一個圖，圖的節點是網頁，圖中的邊是網頁之間的鏈接。PageRank算法對圖進行自由遍歷通過rank值的傳遞多次迭代到收斂時得出最終排名得分。基本公式如式(1)。

(1)

上述公式中，p1,p2,p3,…,pn代表個不同的網頁，M(i)是鏈接到pi的所有網頁的集合，L(j)是網頁上的外鏈數。d(0

根據Pagerank的思想，同樣將社交網絡看作一個圖,圖的節點是社交網絡用戶，圖的邊代表兩個社交網絡用戶之間的社交關系。這樣就得到了Peoplerank的計算公式，如式(2)。

(2)

上述公式中，N1,N2,N3,…,Nn代表的是社交網絡用戶，F(Ni) 表示與Nj具有社交關系的用戶集合。d是阻尼因子，表示節點間的社交關系有可能改善節點等級的概率，它是決定社交關系所能發揮作用的一個權值。其中對于d的取值，userrank模型中對其進行了優化，將其看作是針對每個用戶每次迭代中一個由用戶粉絲群決定的相對隨機的阻尼因子以解決懸掛節點的問題。

2.2 用戶信用度影響因素的假設

影響用戶可信度有很多因素，這里只考慮用戶所處的靜態的社交網絡結構，對用戶行為特征不做考慮。社交網絡社區理論指出用戶并非是孤立存在的個體，直接將Peoplerank算法移植到用戶信用度的計算上無法體現出用戶所處關注圈的定位，在同一關注圈里的排名失去了區分度。因此在算法中有必要研究以社區視角的rank值傳遞過程。

以下是影響用戶信用度rank值因素的假設：

假設一 用戶的信用度與被關注的數量(即粉絲數)相關，如果一個用戶節點接收到的其他用戶關注越多，那么這個用戶的rank值會提升。

假設二 用戶的信用度與粉絲的信用值相關，信用高的粉絲會通過關注向其他用戶傳遞更多的rank值。

假設三 用戶的信用度與用戶關注社群的整體穩定度有關，用戶關注圈的其他用戶的平均相似度高低反映出該用戶的選擇關注者的謹慎態度，關注群越均衡則獲得rank值越高。

假設四 相似用戶彼此的信用關系程度越高，用戶之間的信用值可以通過關注用戶的相似度大小進行影響。反映到關注圈上的特征即為用戶關注圈越相似則用戶所獲的rank值越高。

上述4個假設分別表示了衡量用戶可信度的四個層面：粉絲的數量和質量、關注圈的穩定度和相似度。

2.3 改進算法

基于四個假設對Peoplerank算法進行改進，設計出新的計算,如式(3)～(5)。

(3)

(4)

(5)

上述公式中，N1,N2,N3,…,Nn代表的是社交網絡用戶，F(Ni) 表示與Nj具有社交關系的用戶集合。f是阻尼因子，表示節點間的社交關系有可能改善節點等級的概率，它是決定社交關系所能發揮作用的一個權值,同時在此算法中與di的修正程度關系高度敏感。wij表示的是j對i的權重分配，在以j為中心的關注圈中i的rank值越高，則傳遞所獲的權重越大。di表示的是以i為中心形成的關注圈的穩定度，是由i關注用戶的rank方差計算得到的。可以看出其關注圈用戶的方差越小，則di越大，同時也表示i關注圈用戶的相似度越大，根據相似傳遞更多信用值的假設，此時i的可信度也越高。

如圖2所示。

圖2 描述示意圖

以節點用戶X為例，X越穩定，則X的rank值在每次迭代中向他所關注的人傳遞權值被算法稀釋的作用就越小，反之，A本身穩定度越差則表示A本身信用度較低，那么他向他所關注的人而言就是屬于低質量粉絲(在某一興趣領域專一度不夠)，因此自身的權值會被稀釋更多。同時對于接受用戶Z1獲得的權值也不是從X用戶平均分配的，例如Z1在A所在的關注圈中信用值越靠前，則表示其他關注社區(如用戶Y)對Z1的認可度相對較高，因此A在分配權值時傳遞給用戶Z1的權值也較高，反之Z1在全局中的信用越靠后，則從A獲得的分配也會受到抑制而更低。

3 實驗及其結果分析

本實驗原始數據來源于新浪微博爬蟲所獲的用戶關注數據。實驗在配置為Linux操作系統上進行。其中對其進行去重等預處理，可以得到相對全局的連通社交網絡，共包含491 088用戶。

將這些數導入到MATLAB制成所需的仿真數據集。利用文中提到的模型和算法在編程實現，為保護用戶的賬戶隱私，得到的結果用戶昵稱均由uid表示。兩種算法運行后得到前20排序結果,如表1所示。

表1 兩種算法排序結果

其中，粗體為AI用戶(微博小秘書、微博客服、微博管理員、新手指南、微相冊等等)，這類非人注冊的用戶在粉絲的基數上因為某些原因會被放大(如注冊初期誘導關注等)，原來的算法只考慮了用戶的粉絲數量這一個因素，導致這類用戶的排名會相對靠前。而改進后的算法能識別出關注群體的相關性和穩定性，抑制掉此類用戶的rank值爆炸增長，將使此類用戶的信用排名結合關注群的特征得到更客觀的可信評估數據。同時，在去掉這類粉絲基數龐大的AI用戶后，可以看出剩下的前12用戶的排名具有很強的一致性。

為驗證新算法在缺失數據集上的表現，需要設計出不同規模的數據集對比實驗。實驗以在此數據集的排序前12名的數據作為實驗排序準確性的權威參考。然后隨機取其網絡中的子集數據進行排序運算，其規模分別取原用戶數據集的2%，4%，6%，8%，10%，20%，50%，80%，以8組不同規模的數據分別使用peoplerank算法和改進后的算法(其中為了描述方便，將改進前的算法結果稱為對照組，將改進后的算法結果稱為實驗組)。為減少誤差，每組規模進行5次隨機采樣計算其前12名用戶的平均得分，同時對其rank值作歸一化處理。

通過實驗結果，發現在總用戶數據集為十萬量級時，取樣規模為其10%以上時的對照組和實驗組所得到的前12用戶排序結果基本保持一致。但在數據規模小于10%時，對照組排序結果出現了排序波動，而實驗組依舊保持著排序結果的一致性。

以下是數據集規模在原數據集的2%，4%，6%，8%，10%時得到的前12名rank值歸一化后結果，圖3為對照組，圖4為實驗組(條形圖為100%數據時top12的排序結果)。

圖3 對照組top12實驗結果

圖4 實驗組top12實驗結果

最后，驗證本文提出的用戶可信度模型在小社區評估結果區分中的有效性，選取出不同類型的社區結構的數據集排序結果，得到如圖 5所示的結果。

圖5 不同測試集的用戶可信度分布情況

從上圖中可以看出，不同用戶類型的用戶可信度分布差異很明顯，可以看出本文提出的用戶可信度計算模型可以有效的篩選出正常用戶和低可信度的垃圾用戶。

4 總結

本文參考了peoplerank的算法思想并將其運用到微博用戶可信度評估的模型中，將傳統排序算法的節點從單個用戶傳遞權值的視角擴大到以用戶關注圈形成的社區化的視角，通過社區特征將算法模型進行改進，嘗試從社區化的角度減少數據集因缺失數據太多引起的結果偏差。文中提出了用戶可信度在靜態網絡中不僅僅與粉絲的數量和質量有關，而且與用戶所在社區的穩定度和相似度有關。實驗結果證明，基于社區化的排序算法不僅在篩選非AI用戶的作用上有效，并且能對針對不同的數據規模進行客觀的可信度分析。雖然國內對用戶可信度研究起步較晚，相信本文的研究能對此領域提出一定的參考。

[1] 蔣盛益，陳東沂，龐觀松，等． 微博信息可信度分析研究綜述[J]．圖書情報工作，2013，57(12): 136-142．

[2] A Mtibaa, M May, C Diot, et al. Peoplerank: Social Opportunistic Forwarding[C]∥INFOCOM, 2010 Proceedings IEEE. IEEE,2010: 1-5.

[3] Gupta M，Zhao Pengxiang，Han Jiawei． Evaluating Event Credibility on Twitter [C]∥Proc of the 12th SIAM International Conference on Data Mining． 2012: 153-164.

[4] 唐飛龍,葉施仁,肖春. 基于用戶質量的微博社區博主影響力排序算法[J]. 計算機工程與應用, 2015(4):128-132.

[5] 劉耀庭．社交網絡結構研究[D]．杭州:浙江大學，2008.

[6] 王峰，余偉，李石君． 新浪微博平臺上的用戶可信度評估[J]． 計算機科學與探索，2013，7(12): 1125-1130.

[7] 佐斌,高倩.熟悉性和相似性對人際吸引的影響[J]．中國臨床心理學雜志,2008,16(6): 634-636.

[8] 喬秀全, 楊春, 李曉峰, 等. 社交網絡服務中一種基于用戶上下文的 信任度計算方法[J]. 計算機學報, 2011, 34(12): 2404-2411.

[9] Yang Changchun,Ding Hong,Yang Jing,et al.Research of Microblog Community Detection Based on Clustering Analysis[J].AISS,2013: 1-2.

[10] Yan B,Gregory S.Detecting Community Structure in Networks Using Edge Prediction Methods[J]. Journal of Statistical Mechanics:Theory and Experiment, 2012(9): P09008.

User Credibility Evaluation Algorithm Based on Peoplerank

Li Wenzheng, Zhang Yunfei, Zhou Siqi, Li Xin

(College of Computer and Information, Hohai University, Nanjing 211100, China)

In order to enhance the stability and rationality in ranking the credibility of micro-blog users, an attention circle feature-based user credibility evaluation algorithm is proposed with the use of the idea of Peoplerank. The algorithm introduces the characteristics of the user’s attention circle as the key factor to weight and modify the process of iteration, then the rank value is optimized. Experimental result shows that the proposed algorithm is suitable for the social data sets in different sizes, and it is more rational to sort and evaluate the credibility of user.

Micro-blog; User credibility; Peoplerank; rank; Attention circle

水利部公益性行業科研專項重點項目(201501007);NSFC-廣東聯合基金重點項目(U1301252);國家科技支撐計劃項目(2013BAB06B04;HNKJ13-H17-04);國家自然科學基金面上項目(61272543)

李文政(1991-)，男，重慶，碩士研究生，研究方向：云計算與領域工程、數據挖掘、社交網絡。 張云飛(1980-),男，河南林縣，工程師，碩士研究生，CCf會員，研究方向：云計算、數據挖掘。 周思琪(1992-)，女，河南，碩士研究生，研究方向：云信息安全。 李 鑫(1992-)，男，河南鄭州，碩士研究生，研究方向：云信息安全。

1007-757X(2017)05-0004-04

TP311

A

2017.02.13)