陳毅恒,李雪婷,王 彪,劉 挺

(1. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院信息檢索研究中心,黑龍江 哈爾濱 150001;2. 哈爾濱工業(yè)大學(xué) 圖書館信息咨詢部,黑龍江 哈爾濱 150001)

基于網(wǎng)絡(luò)結(jié)構(gòu)的多種用戶影響力分析算法對(duì)比研究

陳毅恒1,李雪婷2,王 彪1,劉 挺1

(1. 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院信息檢索研究中心,黑龍江 哈爾濱 150001;2. 哈爾濱工業(yè)大學(xué) 圖書館信息咨詢部,黑龍江 哈爾濱 150001)

隨著社交網(wǎng)絡(luò)的發(fā)展，人們可以非常平等、快捷地發(fā)布和接受信息，這導(dǎo)致線上生活對(duì)線下生活的影響越來越大。社會(huì)化營銷應(yīng)運(yùn)而生，其非常重要的一個(gè)需求是要最大化營銷活動(dòng)在社交網(wǎng)絡(luò)中的影響力。因此，社交網(wǎng)絡(luò)中用戶影響力分析成為一個(gè)至關(guān)重要的研究點(diǎn)。該文重點(diǎn)考察了基于網(wǎng)絡(luò)結(jié)構(gòu)的影響力分析方法，主要包括最大度算法、距離中心點(diǎn)算法、類似PageRank算法的PeopleRank算法等，并給出了具體的分析結(jié)論。

用戶影響力分析; 網(wǎng)絡(luò)結(jié)構(gòu); 社交網(wǎng)絡(luò); 微博

Abstract: The analysis of the user influence in the social network is a key research issue in social marketing. This paper is focused on several network structure based algorithms for user influence analysis, and conducts a contrastive study on their performances.

Key words: user influence analysis; network structure; social network; chinese microblog

1 引言

在當(dāng)前的社交網(wǎng)絡(luò)大潮中，通過社交網(wǎng)絡(luò)來銷售自己的產(chǎn)品成為傳統(tǒng)行業(yè)所做的積極嘗試。人們發(fā)現(xiàn)，對(duì)于一些新的產(chǎn)品或者思想，總是由少數(shù)幾個(gè)人首先接受，然后將其傳播到整個(gè)社交網(wǎng)絡(luò)中去。于是，常用的一種營銷手段就是，在某個(gè)潛在客戶群體中找一些人，給予他們一定的優(yōu)惠或者試用機(jī)會(huì)，爭取得到他們的推薦，進(jìn)而將新產(chǎn)品或者思想傳播到整個(gè)潛在客戶群體中去。對(duì)于這種營銷手段來說，產(chǎn)品的質(zhì)量和創(chuàng)新或者價(jià)格的優(yōu)惠是影響最終效果的一個(gè)方面，另一個(gè)非常重要的方面就在于，應(yīng)該選擇社交網(wǎng)絡(luò)中的哪些人，才能最大 化 地 影 響 潛

在客戶群體。本文主要著眼于社會(huì)化營銷這一新興市場需求，通過研究社交網(wǎng)絡(luò)中用戶的影響力，著力解決如何選出合適的用戶以達(dá)到市場營銷的目的。挖掘社交網(wǎng)絡(luò)中有影響力的用戶，或者對(duì)用戶的影響力進(jìn)行量化和排序，對(duì)于信息檢索、信息推薦和社區(qū)挖掘等各方面的研究都是十分有利的。

在信息檢索領(lǐng)域，我們需要對(duì)網(wǎng)頁進(jìn)行排序，所用的排序算法利用了節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈接關(guān)系。事實(shí)上，網(wǎng)頁之間的相互鏈接關(guān)系與微博這種社交網(wǎng)絡(luò)中用戶與用戶之間關(guān)注或者粉絲的關(guān)系是非常相似的。研究者們很早便將這種用于網(wǎng)頁排序的算法應(yīng)用到社交網(wǎng)絡(luò)中來?；诖耍瑢⑦@些算法引入到微博網(wǎng)絡(luò)中并分析各種算法的結(jié)果表現(xiàn)，非常值得嘗試。

本文將著眼于影響力的排序算法，基于微博的網(wǎng)絡(luò)結(jié)構(gòu)，在不考慮任何文本特征的情況下，對(duì)比使用最大度算法[1]、距離中心點(diǎn)算法[2]、平均轉(zhuǎn)發(fā)率和改進(jìn)的PageRank算法——PeopleRank算法的排序結(jié)果。并對(duì)幾種算法的結(jié)果進(jìn)行分析，說明不同場合下算法的表現(xiàn)。

2 相關(guān)研究

2.1 面向信息檢索領(lǐng)域的網(wǎng)絡(luò)節(jié)點(diǎn)重要度計(jì)算方法 與用戶影響力比較近似的是面向信息檢索領(lǐng)域的節(jié)點(diǎn)重要度的計(jì)算方法。信息檢索領(lǐng)域在對(duì)檢索結(jié)果進(jìn)行排序的過程中，產(chǎn)生了對(duì)于網(wǎng)頁權(quán)威度或者說重要度進(jìn)行評(píng)價(jià)的需求。實(shí)際上，這就是一個(gè)有向圖中計(jì)算節(jié)點(diǎn)重要度的需求。

Kleinberg等人提出了一種網(wǎng)頁重要性的分析的算法[3]，算法對(duì)每個(gè)頁面計(jì)算兩種值,一個(gè)是樞紐值(hub scores)，另一個(gè)是權(quán)威值(authority scores)。這兩個(gè)值是相互依存、相互影響的。這個(gè)算法就是著名的HITS算法。Page等人在1999年提出一種基于網(wǎng)頁間相互鏈接關(guān)系的網(wǎng)頁重要度計(jì)算方法，稱為PageRank[4]。PageRank 并不計(jì)算直接鏈接的數(shù)量，而是將從網(wǎng)頁 A 指向網(wǎng)頁B的鏈接解釋為由網(wǎng)頁A對(duì)網(wǎng)頁B所投的一票。這樣，PageRank會(huì)根據(jù)網(wǎng)頁B所收到的投票數(shù)量來評(píng)估該頁的重要性。Haveliwala等人又對(duì)通用性的PageRank算法做了進(jìn)一步的變形[5]，使得網(wǎng)頁排序算法不僅要考慮網(wǎng)頁之間的鏈接，還加進(jìn)了對(duì)正文上下文和主題的考慮。

HITS和PageRank及其衍生算法出現(xiàn)之后，人們發(fā)現(xiàn)其不僅可以用來評(píng)價(jià)網(wǎng)頁的重要度，也可以用于評(píng)價(jià)社交網(wǎng)絡(luò)中的成員的重要性。Zhang等人在一個(gè)Java主題的社區(qū)網(wǎng)站中，嘗試使用HITS等多種方法來評(píng)價(jià)用戶權(quán)威度[6]。Qin等人[7]和Xu等人[8]基于PageRank算法的核心思想，在犯罪網(wǎng)絡(luò)中做了評(píng)價(jià)網(wǎng)絡(luò)成員重要性的嘗試。

2.2 針對(duì)社交網(wǎng)絡(luò)中用戶影響力的研究

Cha等人[9]提出了三個(gè)影響力評(píng)價(jià)指標(biāo),并對(duì)三者進(jìn)行了對(duì)比研究: indegree(入度，即粉絲數(shù))，retweets(轉(zhuǎn)發(fā))和 mentions(提及)。作者用三個(gè)指標(biāo)分別對(duì)5 400萬用戶排序，分析各個(gè)指標(biāo)之間的情況得出結(jié)論: 被提及多的人，被轉(zhuǎn)發(fā)也多。但是粉絲數(shù)卻和其他兩個(gè)指標(biāo)沒有什么關(guān)系。由此可以看出,粉絲數(shù)多的人不一定影響力大。作者同時(shí)研究了影響力隨話題的變化規(guī)律。結(jié)論是最有影響力的人可以在各種話題中發(fā)揮影響力。Romero等人[10]的著眼點(diǎn)還是影響力的指標(biāo)，其他人的工作大多考慮的是影響者的influence，而沒能考慮被影響者的passivity (忠誠度)。作者提出綜合influence和passivity來判斷一個(gè)用戶的影響力。Weng等人[11]首先對(duì)Twitter用戶分析: 72.4%的用戶關(guān)注了其80%以上的粉絲，80.5%的用戶獲得了其關(guān)注者80%的回粉率?；谶@個(gè)發(fā)現(xiàn)，作者提出一個(gè)算法TwitterRank——基于PageRank，考慮話題相似性及網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。Huang等人[12]研究了口碑推薦與用戶后續(xù)的評(píng)價(jià)之間的關(guān)系，并發(fā)現(xiàn)了反直覺的現(xiàn)象，這二者之間是有著關(guān)聯(lián)關(guān)系的。作者建立了一個(gè)框架來衡量個(gè)人的社會(huì)影響力，即衡量這個(gè)人的粉絲數(shù)及對(duì)新鮮事物的敏感度，且研究出一套方法來識(shí)別個(gè)人能夠影響的好友數(shù)。Singer等人[13]試圖在社交網(wǎng)絡(luò)中識(shí)別出一個(gè)個(gè)人的小集合，這些集合中的人可以作為新產(chǎn)品或新技術(shù)最早的接受者，并且在社交網(wǎng)絡(luò)中能夠觸發(fā)出一個(gè)爆發(fā)式的傳播。Bhagat等人[14]在社交網(wǎng)絡(luò)中度量產(chǎn)品能被最大程度接受的量，提出了新穎的方法研究產(chǎn)品最大接受率，接近病毒式傳銷的應(yīng)用，并且在電影社交網(wǎng)站和音樂社交網(wǎng)站上都取得了不錯(cuò)的效果。還有研究者將用戶行為融入模型中，來分析用戶影響力,如Wang等人[15]將用戶行為融入隨機(jī)游走算法中，Huang等人[16]將用戶行為融入PageRank算法中,Bi等人[17]不僅只考慮用戶之間的鏈接關(guān)系，還考慮用戶發(fā)布的具體內(nèi)容，來分析微博中的用戶影響力。

3 基于用戶本身特性的用戶影響力分析

3.1 用戶節(jié)點(diǎn)特性的選擇 在評(píng)價(jià)用戶影響力的算法中[9]，最直接的便是通過統(tǒng)計(jì)節(jié)點(diǎn)本身的某些特性來推斷其影響力。從社交網(wǎng)絡(luò)中用戶影響力分析的需求來看，我們最需要選擇的是那些可以引起其他人反應(yīng)的用戶，比如轉(zhuǎn)發(fā)和評(píng)論。這就決定了那些越是可以把自己的消息送到最多的人面前的用戶，影響力越大。我們可以使用社會(huì)學(xué)研究者們經(jīng)常使用的影響力評(píng)價(jià)算法: 最大度算法[1]和距離中心點(diǎn)算法[2]。

最大度算法的一個(gè)最基本的假設(shè)是，越是擁有更多跟其他節(jié)點(diǎn)鏈接的節(jié)點(diǎn)，越是可能讓更多人看到自己所發(fā)布的信息。因此，一個(gè)樸素的想法是，社交網(wǎng)絡(luò)中度數(shù)越大的節(jié)點(diǎn)，其影響力也越大。即:

inf(v)=d(v),v∈N

(1)

距離中心點(diǎn)算法的一個(gè)基礎(chǔ)假設(shè)為: 社交網(wǎng)絡(luò)中的節(jié)點(diǎn)，如果可以以更短的路徑到達(dá)其他節(jié)點(diǎn)，那它應(yīng)該有更高的機(jī)會(huì)來影響其他節(jié)點(diǎn)。考察網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)所需的路徑長度，也可以是衡量其影響力的一個(gè)方法。即:

(2)

其中dist(v,w)是指網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的最短距離。

除了以上兩種方法之外，我們還可以根據(jù)微博用戶中微博被轉(zhuǎn)發(fā)的歷史記錄計(jì)算其每條微博的平均被轉(zhuǎn)發(fā)率，以每條微博引起的轉(zhuǎn)發(fā)行為作為其影響力的一種體現(xiàn)。即:

(3)

其中S為v的所有微博的集合。

3.2 基于節(jié)點(diǎn)特性的用戶影響力算法

對(duì)于最大度算法，我們采用最簡單的方式。統(tǒng)計(jì)某位用戶有多少領(lǐng)域內(nèi)的粉絲(入度)。具體算法如算法1所示。

算法1 最大度影響力算法

對(duì)于距離中心點(diǎn)算法，要計(jì)算每個(gè)節(jié)點(diǎn)的影響力,需要計(jì)算到達(dá)某個(gè)節(jié)點(diǎn)的平均路徑長度。也即每個(gè)節(jié)點(diǎn)通過關(guān)注到此節(jié)點(diǎn)的評(píng)價(jià)路徑長度，如算法2所示。

算法2 距離中心點(diǎn)算法

對(duì)于用戶平均轉(zhuǎn)發(fā)率的計(jì)算，如算法3所示。

算法3 計(jì)算用戶平均轉(zhuǎn)發(fā)率的算法

續(xù)表

3.3 基于PeopleRank算法的用戶影響力分析

前文已經(jīng)探討了距離中心點(diǎn)算法，主要考慮影響其他節(jié)點(diǎn)的距離。事實(shí)上，在信息檢索領(lǐng)域的網(wǎng)頁權(quán)威度算法PageRank算法能夠更好地描述一個(gè)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的重要程度。本節(jié)將借鑒PageRank算法的主要思想，計(jì)算微博網(wǎng)絡(luò)中用戶的影響力?；谝陨舷敕?，我們?cè)O(shè)計(jì)了PeopleRank的公式，如式(4)所示。

(4)

但是仔細(xì)分析就會(huì)發(fā)現(xiàn)，式(4)中有一個(gè)缺陷: 無論j關(guān)注了多少用戶，只要j關(guān)注了i，i都將得到與j一樣的影響力。當(dāng)j關(guān)注了多個(gè)用戶時(shí)，這個(gè)思想就會(huì)造成不合理的情況。例如，一個(gè)新加入的用戶x獲得了兩個(gè)人的關(guān)注，一個(gè)是行業(yè)里早已存在的意見領(lǐng)袖f，另一個(gè)是很不知名的用戶u。根據(jù)上面的公式，就會(huì)得到這個(gè)新加入的用戶x比意見領(lǐng)袖f影響力更大的結(jié)論。這個(gè)結(jié)論顯然不符合人們的常識(shí)。

彌補(bǔ)這個(gè)缺陷的一個(gè)簡單方法是當(dāng)j關(guān)注了多個(gè)用戶時(shí)(假設(shè)個(gè)數(shù)為N)，其每個(gè)關(guān)注用戶得到其影響力R(j)/N(j)。如式(5)所示。

(5)

F(i)為i的粉絲用戶集，N(j)為用戶j的關(guān)注數(shù)目。

為了得到更加貼近現(xiàn)實(shí)情況的結(jié)果，我們?cè)谏厦婀降幕A(chǔ)上增加一個(gè)常數(shù)c，得到最終的公式，如式(6)所示。

(6)

其中的c為阻尼系數(shù)，代表一條消息從用戶A到用戶B(即B轉(zhuǎn)發(fā)A)的概率。

PeopleRank算法如算法4所示。

算法4 PeopleRank算法

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù) 本文中所進(jìn)行的實(shí)驗(yàn)全部基于新浪微博數(shù)據(jù)。考慮到獲取包含三億用戶的微博網(wǎng)絡(luò)的難度過大，而且在如此巨大的網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)的計(jì)算速度必然十分緩慢。于是我們只選取了“IT互聯(lián)網(wǎng)”領(lǐng)域進(jìn)行本文的所有實(shí)驗(yàn)。對(duì)于“IT互聯(lián)網(wǎng)領(lǐng)域”的人員名單，我們使用了新浪微博“名人堂”中的“IT互聯(lián)網(wǎng)”領(lǐng)域人員名單。最終獲取了2 381名用戶的信息，6 589 451條微博?？紤]到本文所研究的算法為通用的影響力分析算法，限制在某些領(lǐng)域內(nèi)只是為了方便方法的驗(yàn)證，所以，我們對(duì)已經(jīng)獲得的數(shù)據(jù)進(jìn)行了進(jìn)一步的加工和整理。整理之后的數(shù)據(jù)增加了用戶在本領(lǐng)域內(nèi)followesIds、friendsIds的信息，也即用戶在本領(lǐng)域內(nèi)的關(guān)注和粉絲列表。

4.2 實(shí)驗(yàn)結(jié)果與分析

使用前三種方法，即最大度算法、距離中心算法和用戶平均轉(zhuǎn)發(fā)率得到的實(shí)驗(yàn)結(jié)果如表1所示。

為了對(duì)比各個(gè)方法得出的結(jié)果，我們將三個(gè)排序結(jié)果做了比較。

第一種比較方法是，將三個(gè)結(jié)果作為三個(gè)向量，對(duì)比三個(gè)向量的差別。

首先，我們對(duì)三個(gè)算法的結(jié)果進(jìn)行數(shù)值標(biāo)準(zhǔn)化，如式(7) 所示。

(7)

計(jì)算余弦相似度如式(8)。

Sim(A,B)=cosθ= (8)

其中A，B為兩個(gè)向量，每個(gè)用戶即為一個(gè)維度，每個(gè)用戶的標(biāo)準(zhǔn)化數(shù)值即為該維度的值。

對(duì)數(shù)值化之后的向量計(jì)算兩兩之間的余弦相似度，結(jié)果如表2所示。

表2 三種算法得出的IT互聯(lián)網(wǎng)領(lǐng)域結(jié)果的相似度對(duì)比

通過對(duì)比，我們發(fā)現(xiàn)，距離中心點(diǎn)算法與平均轉(zhuǎn)發(fā)率算法的結(jié)果最為接近，而兩者與最大度算法的結(jié)果都相差較大。

另一種方法是看某個(gè)用戶在三個(gè)結(jié)果中的排名相差多少，即計(jì)算兩個(gè)排序結(jié)果相關(guān)度，具體公式如式(9)。

(9)

其中xi，yi為第i個(gè)用戶在兩個(gè)排序中不同的名次。對(duì)數(shù)值化之后的向量兩兩計(jì)算相關(guān)度，結(jié)果如表3所示。

表3 三種算法得出的IT互聯(lián)網(wǎng)領(lǐng)域排名的相關(guān)度對(duì)比

與余弦相似度的計(jì)算類似，當(dāng)考慮所有節(jié)點(diǎn)時(shí)，不同方法的排序結(jié)果之間差異大體相同。如果考慮影響力比較大的用戶，距離中心點(diǎn)和轉(zhuǎn)發(fā)率算法的結(jié)果比較接近，而兩者與最大度算法的差異都比較大。綜上所述，距離中心點(diǎn)算法的結(jié)果與平均轉(zhuǎn)發(fā)率算法的結(jié)果是比較接近的，而最大度算法的結(jié)果與以上兩種算法結(jié)果不是太接近。

基于此，我們要探究一種可代表某個(gè)用戶將某個(gè)消息擴(kuò)散出去的能力的方法。所以，從概念上考慮，將某個(gè)節(jié)點(diǎn)的度數(shù)作為其擴(kuò)散能力的代表，可能是不適合的，從實(shí)際效果來看，其與其他算法的差別也是非常大的。但是，探索某個(gè)用戶可以通過幾個(gè)用戶就可以到達(dá)另一個(gè)用戶，通過統(tǒng)計(jì)該用戶之前的擴(kuò)散能力以推測其實(shí)際的擴(kuò)散能力，或許是一種符合我們目的的算法。從實(shí)際結(jié)果來看，這兩種算法的結(jié)果也是比較接近的。

為了對(duì)PeopleRank的算法結(jié)果與前文的三個(gè)算法進(jìn)行對(duì)比，先將PeopleRank的結(jié)果進(jìn)行標(biāo)準(zhǔn)化，然后計(jì)算它們的余弦相似度，結(jié)果如表4所示。

表4 PeopleRank算法與三種統(tǒng)計(jì)算法的余弦相似度

計(jì)算PeopleRank算法結(jié)果與三種統(tǒng)計(jì)方法的排名相關(guān)度，結(jié)果如表5所示。

表5 PeopleRank算法與三種統(tǒng)計(jì)算法的排名相關(guān)度

從前面兩個(gè)結(jié)果可以看出，PeopleRank算法與轉(zhuǎn)發(fā)率算法比較接近，而與最大度算法差別最大。

4.2 基于用戶本身特性的算法與PeopleRank算法的對(duì)比和分析 從前面幾種算法的結(jié)果可以發(fā)現(xiàn)，使用PeopleRank算法的排序結(jié)果與用戶的平均轉(zhuǎn)發(fā)率排序差別最小。如前文所述，平均轉(zhuǎn)發(fā)率可以比較真實(shí)地表示某個(gè)用戶發(fā)布一條微博之后所獲得的傳播效果，所以，大體上可以說，PeopleRank的算法要比最大度算法和距離中心點(diǎn)算法效果要好。

事實(shí)上，從理論上講，最大度算法、距離中心點(diǎn)算法和PeopleRank算法都是利用了網(wǎng)絡(luò)本身的特性。其中，對(duì)于節(jié)點(diǎn)A，最大度算法只考察了其粉絲數(shù)目，意圖使用粉絲的數(shù)目來推斷其影響力大小，實(shí)際試驗(yàn)證明，這一方法的表現(xiàn)是最差的。而距離中心點(diǎn)算法，考察節(jié)點(diǎn)A距離網(wǎng)絡(luò)中其他節(jié)點(diǎn)的平均距離，事實(shí)上，是對(duì)最大度算法的一個(gè)擴(kuò)展，直觀上講，如果A的粉絲越多，則其距離所有節(jié)點(diǎn)平均距離也可能越小。但是距離中心點(diǎn)算法考察的網(wǎng)絡(luò)屬性要比最大度算法更多。

對(duì)于PeopleRank算法，其不僅考察了整個(gè)網(wǎng)絡(luò)的關(guān)系屬性，而且嘗試著模擬消息的傳遞過程。算法公式中的阻尼系數(shù)c事實(shí)上就是代表某個(gè)消息被下一個(gè)節(jié)點(diǎn)轉(zhuǎn)播的概率。多次的迭代過程，也是在模擬整個(gè)網(wǎng)絡(luò)中一遍又一遍進(jìn)行的消息傳播的過程。所以，PeopleRank算法不僅考察了網(wǎng)絡(luò)的整體屬性,而且考慮進(jìn)了信息傳播的過程，實(shí)際試驗(yàn)表明其比其他兩個(gè)算法更加接近實(shí)際的轉(zhuǎn)發(fā)效果。

但是，我們應(yīng)該看到，PeopleRank算法中對(duì)于信息傳播過程的描述是非常粗略的，其傳播概率值c的取值也是非常不精確的。不考慮當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的關(guān)系，粗糙而簡單地將傳播概率設(shè)為一個(gè)統(tǒng)一的常量，并不是最好的做法。

5 結(jié)論與未來工作

用戶影響力分析是社會(huì)計(jì)算領(lǐng)域一個(gè)重要的研究方向。本文首先從用戶特性的統(tǒng)計(jì)算法著手，分析了最大度算法、距離中心點(diǎn)算法和平均轉(zhuǎn)發(fā)率算法之間的區(qū)別，發(fā)現(xiàn)最大度算法與后兩者的區(qū)別較大，得出的結(jié)論為粉絲數(shù)越大，不一定影響力越大。繼而，本文又將經(jīng)典的PageRank算法遷移到微博網(wǎng)絡(luò)中，即PeopleRank算法。通過對(duì)比PeopleRank算法與之前三個(gè)算法，得出的結(jié)論是PeopleRank算法的結(jié)果與真實(shí)轉(zhuǎn)發(fā)率更加接近。

本文的PeopleRank算法中我們簡單地采用一個(gè)統(tǒng)一的常數(shù)c來表示下一個(gè)節(jié)點(diǎn)被影響的概率，是不精確的。事實(shí)上，這個(gè)概率應(yīng)該是根據(jù)用戶與用戶之間的關(guān)系不同、交互歷史不同而變化的。因此，在未來工作中，我們將建立一個(gè)更合理的模型，對(duì)影響力傳播過程做進(jìn)一步的細(xì)化。

[1] Reka Albert, Hawoong Jeong, Albert-Laszlo Barabasi. Error and attack tolerance of complex networks[J]. Nature, 2000, 406 (6794): 378-382.

[2] S Wasserman, K Faust, D Iacobucci, et al. Social Network Analysis: Methods and Applications[M]. Cambridge University Press, 1994.

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

[4] Lawrence Page, Sergey Brin, Rajeev Motwani, et al. The PageRank citation ranking: Bringing order to the web[J]. World Wide Web Internet and Web Information Systems, 1998, 54(2): 1-17.

[5] T H Haveliwala. Topic-sensitive PageRank: a context-sensitive ranking algorithm for Web search[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(4): 784-796.

[6] Jun Zhang, Mark S Ackerman, Lada Adamic. Community Net Simulator: Using Simulations to Study Online Community Networks[J]. Forum American Bar Association, 2007, 2005(3): 221-230.

[7] Jialun Qin, Jennifer J Xu, Daning Hu, et al. Analyzing Terrorist Networks: A Case Study of the Global Salafi Jihad Network[J]. Network, 2005, 3495(196): 287-304.

[8] Jennifer J Xu, Hsinchun Chen. Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks[J]. Decision Support Systems, 2004, 38(3): 473-487.

[9] Meeyoung Cha, Krishna P Gummadi. Measuring User Influence in Twitter: The Million Follower Fallacy[J]. Artificial Intelligence, 2010, 146(1): 10-17.

[10] Daniel M Romero, Wojciech Galuba, Sitaram Asur, et al. Influence and Passivity in Social Media[J]. Information Systems Journal, 2010, 1(4): 1-9.

[11] Jianshu Weng, Ee-Peng Lim, Jing Jiang, et al. TwitterRank: Finding Topic-Sensitive Influential Twitters[C]// Proceedings of WSDM, 2010: 261-270.

[12] Junming Huang, Xue-qi Cheng, Hua-wei Shen, et al. Exploring Social Influence via Posterior Effect of Word-of-Mouth Recommendations[C]//Proceedings of the 5th ACM international conference on Web search and data mining,2012: 573-582.

[13] Yaron Singer. How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks[C]// Proceedings of WSDM, 2012: 733-742.

[14] Smriti Bhagat, Amit Goyal, Laks V S Lakshmanan. Maximizing Product Adoption in Social Networks[C]// Proceedings of the 15th ACM international conference on Web search and data mining WSDM, 2012: 603-612.

[15] Meng Wang, Gang Zhou, Jun Yu Chen. Analysis of User Influence Using User Behavior and Random Walk[J]. Applied Mechanics and Materials, 2014, 571: 1163-1167.

[16] Yulan Huang. Analysis of user influence in social network based on behavior and relationship[J]. Measurement, Information and Control, 2013: 682-686.

[17] Bin Bi, Yuanyuan Tian et al. Scalable Topic-Specific Influence Analysis on Microblogs[C]//Proceedings of WSDM, 2014: 513-522.

陳毅恒(1979—)， 博士，主要研究領(lǐng)域?yàn)樽匀徽Z言處理。

E-mail: yhchen@ir.hit.edu.cn

李雪婷(1982—)，碩士，主要研究領(lǐng)域?yàn)榍閳?bào)學(xué)。

E-mail: lixueting@hit.edu.cn

王彪(1987—)，碩士，主要研究領(lǐng)域?yàn)樽匀徽Z言處理。

E-mail: bwang@ir.hit.edu.cn

Comparison of User Influence Analysis Algorithms Based on Network Structure

CHEN Yiheng1, LI Xueting2, WANG Biao1, LIU Ting1

(1. Research Center for Social Computing and Information Retrieval of Computer Science and Technology School, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China;2. Information Counseling of Library, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China)

1003-0077(2017)04-0216-07

TP391

A

2015-10-20 定稿日期: 2016-04-16

國家自然科學(xué)基金(61202277, 61133012)