基于在線社會(huì)網(wǎng)絡(luò)的用戶影響力研究

許丹青，劉奕群，張 敏，馬少平

(清華大學(xué) 計(jì)算機(jī)系,智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，清華大學(xué)信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌)，北京 100084)

基于在線社會(huì)網(wǎng)絡(luò)的用戶影響力研究

許丹青，劉奕群，張 敏，馬少平

(清華大學(xué) 計(jì)算機(jī)系,智能技術(shù)與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，清華大學(xué)信息科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室(籌)，北京 100084)

對(duì)大規(guī)模的在線社會(huì)網(wǎng)絡(luò)圖結(jié)構(gòu)進(jìn)行了較為系統(tǒng)的分析，結(jié)果表明社會(huì)網(wǎng)絡(luò)的入度、出度、發(fā)文數(shù)等基本符合冪律分布。社會(huì)網(wǎng)絡(luò)的小世界屬性也使得強(qiáng)連通關(guān)系呈現(xiàn)“紡錘體”形狀。該文從用戶的閱讀概率角度引入用戶的發(fā)文行為、瀏覽行為與標(biāo)簽社區(qū)小世界屬性等對(duì)用戶的社會(huì)影響力模型進(jìn)行建模。實(shí)驗(yàn)結(jié)果顯示PTIM模型融合了發(fā)文行為與小世界屬性等特性，在最具影響力用戶節(jié)點(diǎn)、用戶粉絲數(shù)、認(rèn)證用戶數(shù)與人工標(biāo)注的相對(duì)用戶影響力大小等指標(biāo)上均表現(xiàn)出穩(wěn)定的性能。

社會(huì)影響力;小世界屬性;信息擴(kuò)散;社會(huì)網(wǎng)絡(luò)

1 引言

社交網(wǎng)絡(luò)已經(jīng)逐漸成為用戶獲取信息的一個(gè)不可或缺的工具。與傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)不同，社交網(wǎng)絡(luò)中的信息發(fā)布權(quán)不再只是被媒體編輯等少數(shù)人掌握，社交網(wǎng)絡(luò)用戶掌握了信息發(fā)布的自主權(quán)。社會(huì)網(wǎng)絡(luò)逐步改變了用戶與互聯(lián)網(wǎng)的交互方式和互聯(lián)網(wǎng)用戶的行為習(xí)慣。新浪微博作為中國(guó)社交網(wǎng)絡(luò)的一個(gè)典型代表，其發(fā)展速度也遠(yuǎn)遠(yuǎn)超過(guò)了之前任何傳統(tǒng)媒體的普及速度。互聯(lián)網(wǎng)從發(fā)展初期到用戶量達(dá)到5 000萬(wàn)用了四年的時(shí)間，而微博僅僅用了14個(gè)月。截止2012年底，我國(guó)微博用戶規(guī)模達(dá)到了3.09 億，較2011年增長(zhǎng)了5 873萬(wàn)，網(wǎng)民中微博用戶比例達(dá)到了54.7%[1]。

在社會(huì)網(wǎng)絡(luò)中，用戶關(guān)注關(guān)系、發(fā)文轉(zhuǎn)發(fā)等行為都對(duì)信息傳播有著重要的影響[2-3]，不同影響力的用戶在信息傳播中也擔(dān)當(dāng)著不同的角色，社會(huì)影響力分析[4-5]也是社會(huì)態(tài)勢(shì)分析的重要組成部分，影響力的分析可以幫助市場(chǎng)營(yíng)銷(xiāo)領(lǐng)域更好地定位宣傳用戶和垃圾用戶[2-4]。本文中，我們搜集了約260萬(wàn)的社會(huì)網(wǎng)絡(luò)用戶數(shù)據(jù)，對(duì)社會(huì)網(wǎng)絡(luò)的圖結(jié)構(gòu)進(jìn)行詳盡的統(tǒng)計(jì)分析。我們從用戶閱讀概率的角度出發(fā)對(duì)用戶影響力進(jìn)行定義，并引入用戶的發(fā)文與瀏覽行為等假設(shè)構(gòu)建不同的社會(huì)影響力模型。我們選取不同模型的最具影響力用戶、粉絲數(shù)與認(rèn)證用戶的識(shí)別、基于人工標(biāo)注的用戶影響力相對(duì)大小等指標(biāo)對(duì)不同的影響力模型進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明不同的模型適用于不同的小世界群體的影響力識(shí)別。

2 已有工作概述

根據(jù)廣義的社會(huì)學(xué)理論[6]，一個(gè)用戶的社會(huì)影響力被定義為他的某一行為引起或促使另一用戶產(chǎn)生相應(yīng)的行為的能力?；诂F(xiàn)有的社交網(wǎng)絡(luò)平臺(tái)，很多的研究學(xué)者從不同角度對(duì)用戶的社會(huì)影響力進(jìn)行度量與評(píng)價(jià)[7-8]。初始的基于社交網(wǎng)絡(luò)上的社會(huì)影響力是由用戶的粉絲數(shù)來(lái)決定的，如果某用戶擁有的粉絲數(shù)越多，說(shuō)明其社會(huì)影響力越大[6]。然而，后續(xù)的分析結(jié)果發(fā)現(xiàn)單純的基于關(guān)注關(guān)系圖并不能對(duì)社會(huì)影響力進(jìn)行全面而準(zhǔn)確的描述。用戶的話題分布、專(zhuān)業(yè)領(lǐng)域、發(fā)文內(nèi)容與頻率等均可能對(duì)用戶的影響力評(píng)估產(chǎn)生一定的影響，而且同一用戶可能對(duì)不同領(lǐng)域發(fā)揮的影響力很不同[8-10]。

前人的一些研究工作基于傳統(tǒng)的Web中的PageRank[11]算法對(duì)社會(huì)網(wǎng)絡(luò)中的節(jié)點(diǎn)影響力進(jìn)行迭代度量；也有一些工作引入HITS[12]算法作為衡量社會(huì)影響力的方法之一。HITS算法假定每個(gè)節(jié)點(diǎn)的影響力都由自身的內(nèi)容影響力與鏈接影響力兩部分組成，而且好的鏈接影響力節(jié)點(diǎn)通常指向具有高內(nèi)容影響力的節(jié)點(diǎn)。在PageRank 算法中，一個(gè)節(jié)點(diǎn)的影響力是所有關(guān)注這一節(jié)點(diǎn)的節(jié)點(diǎn)集合(或稱(chēng)為粉絲集合)的影響力之和，一個(gè)節(jié)點(diǎn)的粉絲集合的影響力之和越大，則表明這一節(jié)點(diǎn)所具有的影響力越高。誠(chéng)然，這些傳統(tǒng)Web網(wǎng)絡(luò)中的著名算法假設(shè)[11-13]也同樣適合于社會(huì)網(wǎng)絡(luò)的影響力。在本文中，我們將用戶的閱讀概率引入到社會(huì)影響力的定義中，結(jié)合發(fā)文習(xí)慣、小世界屬性、瀏覽假設(shè)等完成用戶影響力模型的構(gòu)建。

3 社會(huì)網(wǎng)絡(luò)的圖結(jié)構(gòu)分析

3.1 入度、出度等圖屬性分析

我們將某一用戶的粉絲數(shù)目定義為入度，關(guān)注數(shù)目定義為出度?，F(xiàn)有的社會(huì)網(wǎng)絡(luò)的入度分布見(jiàn)圖1。與其他復(fù)雜網(wǎng)絡(luò)相似，社交網(wǎng)絡(luò)的入度頻度由兩段冪率分布組合而成。有相當(dāng)多的用戶被少于十個(gè)用戶關(guān)注，這些用戶主要由僵尸用戶、不活躍用戶與新用戶組成。他們?cè)谏缃痪W(wǎng)絡(luò)中很常見(jiàn)，但是在社交網(wǎng)絡(luò)中發(fā)揮的作用并不是很大，影響力相對(duì)都比較小，甚至有的會(huì)產(chǎn)生一些負(fù)影響力(如垃圾用戶或水軍)，經(jīng)常推送廣告或者發(fā)布一些垃圾信息等。另外的一部分用戶擁有著很多的粉絲，被稱(chēng)為影響力大的用戶，我們的統(tǒng)計(jì)結(jié)果表明，前30%的高入度用戶影響著了大約80%的用戶。

除了入度分布之外，我們也對(duì)社會(huì)網(wǎng)絡(luò)的出度分布進(jìn)行了分析,結(jié)果見(jiàn)圖2。前人研究顯示在小范圍的社會(huì)關(guān)系圖中出度頻度也符合冪律分布。然而，我們的分析并不能與這一結(jié)果相吻合。我們實(shí)驗(yàn)中所引用的新浪微博服務(wù)有2 000 個(gè)關(guān)注的上限限制，導(dǎo)致了出度圖中的數(shù)量截止現(xiàn)象的產(chǎn)生，這也導(dǎo)致了我們的頻度分布與之前研究的差異產(chǎn)生。

圖 1 入度分布

圖2 出度分布

我們也對(duì)用戶的粉絲數(shù)與關(guān)注數(shù)之間的關(guān)系進(jìn)行了分析，如圖3所示。 圖中顯示了一個(gè)很有趣的現(xiàn)象：對(duì)于那些擁有中等數(shù)目粉絲(粉絲數(shù)<=1 000)的用戶，關(guān)注數(shù)與粉絲數(shù)呈現(xiàn)一個(gè)線性關(guān)系；然而，當(dāng)粉絲數(shù)大于1 000之后(具有一定影響力的節(jié)點(diǎn))，關(guān)注數(shù)與粉絲數(shù)之間的關(guān)系則不再是之前的線性關(guān)系，而變得相對(duì)復(fù)雜分散。影響力節(jié)點(diǎn)的關(guān)注行為相對(duì)分散，一部分用戶僅僅關(guān)注他們感興趣的用戶；另一部分用戶出于相互關(guān)注的禮貌性行為而關(guān)注更多的人,禮貌性互相關(guān)注行為被文獻(xiàn)[8]所驗(yàn)證。圖4展示的發(fā)文情況也大致符合冪率分布。

圖3 入度與出度關(guān)系

圖4 發(fā)文分布

3.2 強(qiáng)連通關(guān)系

基于已有社會(huì)網(wǎng)絡(luò)，我們隨機(jī)選取用戶節(jié)點(diǎn)作為種子節(jié)點(diǎn)并使用廣度優(yōu)先策略進(jìn)行強(qiáng)連通分析。關(guān)系網(wǎng)絡(luò)中的節(jié)點(diǎn)可分為：IN、OUT、SCC與ISOLATE 四類(lèi)。其中，SCC是關(guān)系網(wǎng)絡(luò)中的一個(gè)最大強(qiáng)連通分支，分支中的任一節(jié)點(diǎn)到另一節(jié)點(diǎn)均存在至少一條可抵達(dá)的有向路徑；IN集合中的任一節(jié)點(diǎn)都存在至少一條前向可抵達(dá)路徑可以到達(dá)SCC中的任一節(jié)點(diǎn)，而不存在后向可抵達(dá)路徑；OUT集合中的任一節(jié)點(diǎn)都存在至少一條后向可抵達(dá)路徑可以由SCC某一節(jié)點(diǎn)抵達(dá)，并且不存在前向可抵達(dá)路徑；ISOLATE集合也稱(chēng)為可分離集合，其與IN、OUT與SCC集合均不可以互相抵達(dá)，是相對(duì)獨(dú)立的集合。

與Web網(wǎng)絡(luò)的“蝴蝶結(jié)”形狀不同[14]，社會(huì)網(wǎng)絡(luò)圖的連通關(guān)系更像一個(gè)紡錘體結(jié)構(gòu)(圖5)。基于我們收集到的2 631 342個(gè)用戶節(jié)點(diǎn)的社會(huì)關(guān)系圖，最大的強(qiáng)連通分支包含了2 161 844 個(gè)用戶，占總用戶數(shù)的82.15%。在社會(huì)關(guān)系圖中，絕大多數(shù)的用戶都處在最大強(qiáng)連通子圖中，而且處于可分離集合的用戶占了很小的比例，這可能與社會(huì)網(wǎng)絡(luò)的社會(huì)屬性有很大的關(guān)系。社會(huì)網(wǎng)絡(luò)中用戶的趨同性使得用戶之間的連通關(guān)系加強(qiáng)。

圖5 連通關(guān)系圖

4 社會(huì)網(wǎng)絡(luò)的影響力模型

基于在線社會(huì)網(wǎng)絡(luò)的特點(diǎn)，我們將社會(huì)網(wǎng)絡(luò)用戶的影響力定義為：在某個(gè)特定的時(shí)間段內(nèi)這一用戶的發(fā)文被整個(gè)社會(huì)網(wǎng)絡(luò)其他用戶閱讀到的概率。令整個(gè)社會(huì)網(wǎng)絡(luò)為S，用戶u的影響力定義為式(1)。

(1)

其中Read(u,v)表示用戶u的發(fā)文被用戶v瀏覽到的概率，其主要與用戶u的發(fā)文生成函數(shù)G(u)、用戶v的信息接收函數(shù)O(v)、用戶u到用戶D(u,v)的信息傳播函數(shù)等因素相關(guān)。在接下來(lái)的工作中，我們分別基于不同的假設(shè)提出不同的影響力模型。

FLM(Follower Limited Model)模型：用戶u的社會(huì)影響力由他的粉絲集合的瀏覽概率Read(u,v)累加形成。對(duì)于任一粉絲v，不妨假設(shè)v的關(guān)注集合Att(v)={a1,a2,...,an},同時(shí)u屬于Att(v)，即v關(guān)注了u。那么用戶u對(duì)用戶v的影響力Inf(u,v)可以量化表示為用戶u的發(fā)文被用戶v瀏覽到的概率。FLM模型中用戶u的影響力可以形式化定義為式(2)。

(2)

用戶u的影響力由其所有的粉絲到用戶u的閱讀概率累加而成。FLM模型從用戶的發(fā)文角度對(duì)用戶的影響力進(jìn)行刻畫(huà)。

SWDM(Small World Diffusion Model)模型：對(duì)于用戶u的任一粉絲v而言，如果u與v同屬于一個(gè)小世界群體，我們認(rèn)為他們之間的信息傳播呈雙向傳遞趨勢(shì)，u到v的影響力擴(kuò)散大小與這兩個(gè)用戶現(xiàn)有的影響力差值成正比；如果不存在同一群體，則信息傳播更加偏向于單向傳遞，其影響力的擴(kuò)散差值取決于用戶u的影響力。SWDM模型的形式化定義如下：

? 如果u與v同屬于某個(gè)小世界群體(同時(shí)編輯了某個(gè)標(biāo)簽)且v關(guān)注了u，則用戶u到v的影響力擴(kuò)散值見(jiàn)式(3)：

(3)

? 如果他們不屬于小世界群體，僅僅存在著關(guān)注關(guān)系(v關(guān)注u)，則用戶u到v的影響力擴(kuò)散值為式(4)：

(4)

接著，我們對(duì)FLM與SWDM進(jìn)行線性迭代，形成了PTIM (Posting and Tagging Incorporated Model)模型，它將用戶的發(fā)文行為和標(biāo)簽信息引入到影響力模型中。

5 模型評(píng)估分析

在本文中，我們將選取前人類(lèi)似的評(píng)價(jià)方法對(duì)影響力模型的性能進(jìn)行評(píng)價(jià)。首先，我們對(duì)比不同模型得到的最有影響力的前N個(gè)用戶，并進(jìn)行影響力對(duì)比分析；接下來(lái)，我們將分析不同模型的影響力排名下用戶粉絲數(shù)、獲得認(rèn)證的人數(shù)等特征的召回情況；最后，我們?nèi)斯みx取并標(biāo)注了一部分用戶的影響力相對(duì)關(guān)系，并對(duì)不同模型的相對(duì)影響力識(shí)別性能進(jìn)行評(píng)估。

5.1 最具影響力節(jié)點(diǎn)的方法評(píng)估

最具影響力用戶的定位研究，如何挑選最少的(符合一定規(guī)模的)用戶，可以影響覆蓋到最多的用戶，是在線社會(huì)網(wǎng)絡(luò)的一項(xiàng)重要工作，在廣告推廣、市場(chǎng)營(yíng)銷(xiāo)等領(lǐng)域有著廣泛的應(yīng)用前景。我們將最具影響力節(jié)點(diǎn)識(shí)別作為我們的評(píng)估方法之一。表1列出了不同的社會(huì)影響力模型下計(jì)算出來(lái)的前五個(gè)最具影響力用戶。

表1 不同模型下前五個(gè)最具影響力的用戶

FLM模型的最具影響力節(jié)點(diǎn)與其他四個(gè)模型結(jié)果相差最大。FLM模型的影響力主要由兩部分決定：用戶發(fā)文數(shù)以及用戶的粉絲數(shù)，越高的發(fā)文數(shù)與粉絲數(shù)形成了用戶越大的影響力。用戶的發(fā)文行為是衡量社會(huì)影響力的一個(gè)重要方面，F(xiàn)LM 模型將用戶的發(fā)文行為量化地引入到了社會(huì)影響力的模型中。SWDM模型與TrustRank 模型的前五 位影響力最高的用戶均為娛樂(lè)或者行業(yè)的名人，PageRank與PTIM模型的結(jié)果相對(duì)比較多元化。“冷笑話精選”與“頭條新聞”在PageRank模型中分列影響力第四與第五位，他們分別以發(fā)笑話或者熱門(mén)事件相關(guān)內(nèi)容為主，經(jīng)常有著很大的轉(zhuǎn)發(fā)量，對(duì)于公眾而言有著廣泛的影響力。

PTIM模型的結(jié)果最具多樣化，前五個(gè)最具影響力的用戶分散在不同的領(lǐng)域，覆蓋更廣泛的人群。PTIM模型將用戶的發(fā)文行為、用戶鏈接關(guān)系與標(biāo)簽的社區(qū)行為等因素均考慮入內(nèi)，因此，它在識(shí)別最具影響力用戶上表現(xiàn)出了很好的性能。

5.2 粉絲數(shù)目與認(rèn)證用戶特征的交叉評(píng)估

用戶粉絲數(shù)一直被認(rèn)為是在線社會(huì)網(wǎng)絡(luò)的影響力評(píng)估的一個(gè)重要特征。我們以多粉絲用戶與少粉絲用戶的識(shí)別作為評(píng)估指標(biāo)之一。在我們的實(shí)驗(yàn)中，如果一個(gè)用戶的粉絲數(shù)大于5 000，則我們稱(chēng)之為多粉絲用戶；如果粉絲數(shù)少于100，則我們稱(chēng)為少粉絲用戶。我們將對(duì)我們的模型對(duì)于多粉絲用戶與少粉絲用戶的甄別情況進(jìn)行對(duì)比分析。

圖6(a)列出了五種模型在不同的影響力排名下對(duì)于多粉絲用戶的甄別情況。在同等影響力排名情況下，多粉絲用戶占到的比例越多，則可以認(rèn)定其對(duì)影響力較大的用戶識(shí)別效果越好。結(jié)果顯示FLM 模型識(shí)別的多粉絲用戶要明顯少于其他四種模型，其他四個(gè)模型在多粉絲用戶的識(shí)別上有著相似的性能，PageRank模型在少粉絲用戶的識(shí)別上性能最差。少粉絲用戶的識(shí)別性能對(duì)比見(jiàn)圖6(b)圖。通常意義上，少粉絲用戶中有相當(dāng)大的比例是屬于不活躍用戶、新用戶或者僵尸用戶，這些用戶通常的在線社會(huì)影響力較小，其排名越靠后，則模型的識(shí)別效果越好。圖6(b)顯示PageRank 模型對(duì)于這類(lèi)少粉絲用戶的識(shí)別效果較差。與Web中網(wǎng)頁(yè)重要性一樣，TrustRank模型仍舊在識(shí)別小粉絲用戶上體現(xiàn)除了很好的性能。PTIM模型在這類(lèi)用戶的識(shí)別上體現(xiàn)出了卓越的性能。結(jié)果表明發(fā)文行為、標(biāo)簽與鏈接關(guān)系等特征的結(jié)合對(duì)于衡量用戶影響力起著至關(guān)重要的作用。

圖6 不同模型對(duì)多粉絲用戶、少粉絲用戶與認(rèn)證用戶的識(shí)別情況

名人身份認(rèn)證策略是微博服務(wù)的獨(dú)特的特征之一，新浪微博中現(xiàn)有超過(guò)三億的注冊(cè)用戶，其中認(rèn)證用戶約30萬(wàn)。通常意義上來(lái)講，認(rèn)證名人都具有較高的影響力。本文也對(duì)不同模型的認(rèn)證用戶識(shí)別情況進(jìn)行了對(duì)比，結(jié)果見(jiàn)圖6(c)。PTIM模型與FLM模型中都將發(fā)文行為作為重要的特征之一引入到影響力的構(gòu)建中，這樣很容易給予那些發(fā)文很多的營(yíng)銷(xiāo)或者廣告用戶一個(gè)很好的影響力得分。在同等情況下，TrustRank模型與SWDM模型對(duì)于認(rèn)證用戶的識(shí)別效果最佳，F(xiàn)LM模型與PTIM效果較差。SWDM模型是基于在線社會(huì)網(wǎng)絡(luò)的小世界屬性而提出假設(shè)建立的。認(rèn)證用戶之間的互相關(guān)注強(qiáng)，存在著明顯的小世界屬性，這與我們的實(shí)驗(yàn)結(jié)果剛好吻合。

5.3 基于人工標(biāo)注的用戶影響力相對(duì)關(guān)系評(píng)估

粉絲數(shù)目、認(rèn)證用戶識(shí)別等都是社會(huì)網(wǎng)絡(luò)評(píng)估用戶影響力重要的特征，另外，我們也基于人工標(biāo)注的用戶影響力對(duì)的方法進(jìn)行進(jìn)一步的評(píng)估。首先，我們選擇十個(gè)具有代表性的標(biāo)簽(代表著不同的用戶群)，它們分別是“音樂(lè)”、“攝影”、“清華大學(xué)”、“數(shù)據(jù)挖掘”、“法律”、“電影”、“互聯(lián)網(wǎng)”、“中醫(yī)”、“心理學(xué)”等。這些標(biāo)簽覆蓋了傳統(tǒng)意義上的自然科學(xué)、社會(huì)科學(xué)、人文藝術(shù)和其他熱門(mén)領(lǐng)域，因此其有一定的代表意義。在這十類(lèi)的標(biāo)簽用戶集合中，我們隨機(jī)抽取部分認(rèn)證用戶并進(jìn)行隨機(jī)不重復(fù)進(jìn)行配對(duì)組合作為我們的實(shí)驗(yàn)評(píng)估集合。我們總計(jì)收集到1 345對(duì)認(rèn)證用戶并將其進(jìn)行人工標(biāo)注。兩個(gè)經(jīng)過(guò)專(zhuān)業(yè)訓(xùn)練的標(biāo)注人員完全獨(dú)立地對(duì)這些抽取出來(lái)的用戶對(duì)的相對(duì)影響力大小進(jìn)行標(biāo)注。對(duì)用戶的相對(duì)影響力定義如下：如果前者的影響力明顯大于后者，則標(biāo)記為1；如果明顯小于后者，則標(biāo)記為-1，如果不能區(qū)分或者無(wú)明顯差異，則標(biāo)記為0。這兩個(gè)標(biāo)注人員的Kappa 系數(shù)為0.84。

我們基于人工標(biāo)注之后的用戶相對(duì)影響力情況對(duì)不同模型的性能進(jìn)行評(píng)估，實(shí)驗(yàn)對(duì)比結(jié)果見(jiàn)圖7。對(duì)于“法律”標(biāo)簽，F(xiàn)LM模型體現(xiàn)了最好的性能，發(fā)文行為在法律領(lǐng)域?qū)τ谟脩粲绊懥Φ淖R(shí)別起到了更加至關(guān)重要的作用。這可能與“法律”這一小世界高度專(zhuān)業(yè)集中且專(zhuān)家易識(shí)別有關(guān)，結(jié)果顯示發(fā)文情況在社會(huì)影響力的評(píng)估中顯得尤為重要。"音樂(lè)"是最大的用戶社區(qū)，有195 542個(gè)用戶將其作為他們的標(biāo)簽之一,用戶分布分散復(fù)雜。實(shí)驗(yàn)結(jié)果顯示FLM模型在音樂(lè)領(lǐng)域的性能很差，標(biāo)簽關(guān)系、關(guān)注鏈接信息對(duì)于衡量用戶影響力是非常重要的。PTIM模型將以上的這些特征有效地結(jié)合起來(lái)，在“音樂(lè)”群體中性能最好。

圖7 基于人工標(biāo)注的用戶相對(duì)影響力在不同模型的性能情況

總體而言，PTIM模型在大多數(shù)標(biāo)簽集合上均表現(xiàn)出了較好的性能，PageRank與TrustRank模型在各個(gè)用戶集合中有相似的性能。實(shí)驗(yàn)結(jié)果對(duì)比顯示不同的影響力模型在不同的用戶群體中所表現(xiàn)的性能也截然不同，這與不同的標(biāo)簽集合中用戶影響力與不同的因素影響有很大的關(guān)系。PageRank與TrustRank模型主要將用戶鏈接關(guān)系信息以不同的形式引入；FLM模型與SWDM模型分別僅僅側(cè)重用戶的發(fā)文行為、小世界屬性，性能相對(duì)不穩(wěn)定。PTIM模型將發(fā)文行為、鏈接關(guān)系、小世界屬性等有效地結(jié)合起來(lái)，在各種評(píng)估指標(biāo)均表現(xiàn)出了相對(duì)穩(wěn)定的性能。

6 總結(jié)與展望

本文中，我們首先分析了大規(guī)模在線社會(huì)網(wǎng)絡(luò)的圖結(jié)構(gòu)關(guān)系，社會(huì)網(wǎng)絡(luò)的強(qiáng)連通關(guān)系呈現(xiàn)“紡錘體”形狀。我們引入了用戶的閱讀概率從用戶的發(fā)文、瀏覽等行為對(duì)社會(huì)影響力進(jìn)行建模。我們使用用戶粉絲數(shù)、認(rèn)證用戶數(shù)等常見(jiàn)的傳統(tǒng)特征對(duì)模型的實(shí)驗(yàn)結(jié)果進(jìn)行交叉評(píng)估，并基于人工標(biāo)注的用戶相對(duì)影響力關(guān)系對(duì)進(jìn)一步對(duì)比不同影響力在不同領(lǐng)域的變化情況。PTIM模型將用戶的發(fā)文行為、小世界屬性與用戶關(guān)注關(guān)系進(jìn)行有效融合，性能表現(xiàn)穩(wěn)定。

盡管我們的模型取得了一定的成效，仍舊存在一些問(wèn)題亟需改進(jìn)。我們?cè)谝胄∈澜鐚傩詴r(shí)擴(kuò)散方式單一，然而實(shí)際情況下不同社區(qū)的信息擴(kuò)散很復(fù)雜，未來(lái)我們將引入不同的擴(kuò)散函數(shù)；另外，不同的用戶的影響力因素也不盡相同，區(qū)分不同用戶適用不同的影響力模型也是我們未來(lái)的主要研究工作之一。

[1] 中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心. 第31次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[R], 2013.

[2] A Anagnosopoulos, R Kumar, M. Mahdian. Influence and correlation in social networks[C]//Proceedings of the 14th ACM International Conference on Knowledge Discovery and Data Mining, 2008: 7-15.

[3] D Kempe, J M Kleinberg, E Tardos. Maximizing the spread of influence through social network[C]//Proceedings of the 9th ACM International Conference on Knowledge Discovery and Data Mining, 2003, 137-146.

[4] P F Lazarsfeld, B Berelson, H Gaudet. The people’s choice: How the voter makes up his mind in a presidential campaign[M]. Columbia University Press, 1944.

[5] W Chen, Y Wang, S Yang. Efficient influence maximization in social network[C]//Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, 2009.

[6] J R P French, B Raven. The bases of social power[J]. Studies in Social Power, 1959： 150-217.

[7] J Tang, J Sun, C Wang， et al. Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, 2009.

[8] J Weng, E Lim, J Jiang, et al. TwitterRank: finding topic-sensitive influential Twitters[C]//Proceedings of the 3th ACM International Conference on Web Search and Data Mining, 2010: 1-10.

[9] G R Manuel, L Jure, L Andreas. Inferring networks of diffusion and influence[C]//Proceedings of the 16th ACM International conference on Knowledge Discovery and Data Mining, 2010: 141-150.

[10] N Friedkin. A structural theory of social influence[M]. Cambrige University Press, 1998.

[11] L Pages, S Brin, R Motwani, et al. Wingorad. The page rank of citation ranking? Bringing order to the Web. Technical report, SIDL-WP-1999-0120, Standford University, 1999.

[12] L Li, Y Shang, W Zhang. Improvement of HITS-based Algorithms on Web documents[C]//Proceedings of the 11th International World Wide Web Conference.2002: 35-44.

[13] Z Gyongyi, H Garcia-Molina, J Pedersen. Combating Web spam with TrustRank[C]//Proceedings of the 30th VLDB Conference, 2004: 576-587.

[14] A Broder, R Kumar, F Maghoul, Graph structure in the Web[C]//Proceedings of WWW2009, 2009.

Study on User Influence in Online Social Networks

XU Danqing, LIU Yiqun, ZHAMG Min, MA Shaoping

(State Key Lab of Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

Based on the large-scale social network dataset, this paper conducts a multi-feature statistical analysis on graph structure and finds that the indegree, outdegree and posts of social networks generally fit power law distribution. The “small-world” property makes the strongly connected structure of social network show the “spindle” shape. Furthermore, this paper incorporates users’ posting behaviors, browsing behaviors and social communities’ properties into social influence modelings. Experimental results show that the PTIM model combining users’ behaviors and link relationships has a stable performance on identifying the numbers of fans, authenticated users, the relative influence of users’ pairs and other indices.

social influence, small world, information diffusion, social network

許丹青(1987—)，碩士。E?mail：xudanqing06@gmail．com劉奕群(1981—)，博士，副教授，主要研究領(lǐng)域?yàn)樾畔z索與用戶行為分析。E?mail：yinqunliu@tsinghua．edu．cn張敏(1977—)，博士，副教授，主要研究領(lǐng)域?yàn)樾畔z索與推薦系統(tǒng)。E?mail：z?m@tsinghua@edu．cn

1003-0077(2016)02-0083-07

2013-10-15 定稿日期： 2014-04-15

國(guó)家863高科技項(xiàng)目(2011AA01A205)；國(guó)家自然科學(xué)基金(60903107，61073071)

TP391

A