tsk-shell:一種話題敏感的高影響力傳播者發(fā)現(xiàn)算法

笱程成 杜 攀 賀 敏,3 劉 悅 程學(xué)旗

1(中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)2(中國科學(xué)院大學(xué) 北京 100049)3 (國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心 北京 100029) (gouchengcheng@gmail.com)

tsk-shell:一種話題敏感的高影響力傳播者發(fā)現(xiàn)算法

笱程成1,2杜 攀1賀 敏1,2,3劉 悅1程學(xué)旗1

1(中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院計(jì)算技術(shù)研究所) 北京 100190)2(中國科學(xué)院大學(xué) 北京 100049)3(國家計(jì)算機(jī)網(wǎng)絡(luò)與信息安全管理中心 北京 100029) (gouchengcheng@gmail.com)

在社交網(wǎng)絡(luò)中，挖掘高影響力的信息傳播者，對(duì)微博服務(wù)中內(nèi)容的流行度分析和預(yù)測是非常有價(jià)值的任務(wù).與眾多相關(guān)方法相比，k-shell分解(k-core)方法因其簡潔高效、平均性能好的特點(diǎn)吸引了越來越多的研究人員的興趣.但是，目前k-shell方法著重考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置因素，而忽略了話題在信息傳播中的影響.因此，為了利用用戶歷史數(shù)據(jù)中蘊(yùn)含的話題對(duì)消息的傳播概率進(jìn)行細(xì)粒度的建模，提出了一種話題敏感的k-shell(topic-sensitivek-shell， tsk-shell)分解算法.在真實(shí)Twitter數(shù)據(jù)集上實(shí)驗(yàn)表明，在發(fā)現(xiàn)topk高影響力傳播者任務(wù)中，tsk-shell比k-shell的性能平均提高了約40%，證明了tsk-shell算法的有效性.

高影響力傳播者；k-shell分解；社交網(wǎng)絡(luò)；信息擴(kuò)散；傳播概率；微博

發(fā)現(xiàn)高影響力的傳播者在各種應(yīng)用場景中越來越重要，如社交推薦、病毒式營銷、流行度預(yù)測、品牌管理等.針對(duì)該任務(wù)，學(xué)術(shù)界目前提出了多種方法[1-3]，比如基于PageRank[4]的方法[1]和基于k-shell分解的方法[2]，其中，基于k-shell分解[2]的方法被證明是目前最有效的方法[3]. 從信息傳播的角度看，消息的爆發(fā)或流行主要是由2個(gè)因素造成的：一方面，網(wǎng)絡(luò)結(jié)構(gòu)對(duì)消息的傳播具有較大的影響，如果一個(gè)消息傳播過程中的轉(zhuǎn)發(fā)者有較多的朋友，則該消息就能有機(jī)會(huì)被更多的人看見，就越能獲得更大的傳播機(jī)會(huì)；另一方面，消息本身的內(nèi)容對(duì)消息的傳播有重要影響，如具有吸引力和爆炸性話題的消息具有較大的概率被廣泛地傳播.

一般來講，對(duì)于不同的話題或領(lǐng)域，各個(gè)用戶感興趣的程度不同，因而，同一用戶在不同話題或領(lǐng)域中的傳播影響力是隨著話題或領(lǐng)域的不同而改變的[5-8]，例如，Kevin Durant可能是NBA全明星賽中是最有影響力的傳播者，但肯定與Geoffrey Hinton在機(jī)器學(xué)習(xí)領(lǐng)域的影響力沒辦法相比.在眾多傳統(tǒng)的用戶影響力分析模型中，k-shell及其變種以網(wǎng)絡(luò)拓?fù)浞治鰹榛A(chǔ)，能夠有效地衡量網(wǎng)絡(luò)傳播過程中的用戶影響力，但基于k-shell分解的方法及其擴(kuò)展往往只關(guān)注拓?fù)浣Y(jié)構(gòu)對(duì)傳播能力的影響，而實(shí)際應(yīng)用場景往往更加復(fù)雜.首先，不同用戶之間交互的頻度明顯不同，有親疏之別；其次，用戶交互的強(qiáng)度也會(huì)隨著內(nèi)容或領(lǐng)域的變化而改變，如某些粉絲只評(píng)論和轉(zhuǎn)發(fā)某類感興趣的話題，而不理睬其他的話題.針對(duì)前者，文獻(xiàn)[9]提出了加權(quán)的k-shell分解算法，在金融、貿(mào)易等網(wǎng)絡(luò)中進(jìn)行的實(shí)驗(yàn)表明，考慮權(quán)重信息的k-shell分解要好于原始的k-shell分解，但是加權(quán)的k-shell分解算法仍然側(cè)重于拓?fù)浞治?，并沒有充分考慮信息在網(wǎng)絡(luò)上傳播的內(nèi)容因素，比如不同的話題在不同的邊上產(chǎn)生傳播的可能性也不盡相同，僅靠拓?fù)湫畔㈦y于捕捉話題變遷在網(wǎng)絡(luò)傳播過程中對(duì)于傳播者影響力的影響.

本文提出了話題敏感的k-shell(topic-sensitivek-shell, tsk-shell)分解算法，在發(fā)揮k-shell基于拓?fù)涞膫鞑ビ绊懥Ψ治鰞?yōu)勢的同時(shí)引入基于內(nèi)容的傳播影響力分析，即分析用戶及其好友在不同話題上的轉(zhuǎn)發(fā)行為特征，更加真實(shí)地建模社交網(wǎng)絡(luò)上用戶之間的傳播影響機(jī)制，從而更加有效地發(fā)現(xiàn)社交網(wǎng)絡(luò)上的高影響力的傳播用戶，為社交推薦、病毒式營銷、流行度預(yù)測、品牌管理、甚至突發(fā)性預(yù)測等諸多應(yīng)用提供有效支持.tsk-shell算法與傳統(tǒng)加權(quán)的k-shell分解算法的區(qū)別在于，傳統(tǒng)加權(quán)k-shell算法在k-shell算法的基礎(chǔ)上，通過量化拓?fù)浣Y(jié)構(gòu)屬性賦予網(wǎng)絡(luò)邊權(quán)[9]，其權(quán)重的計(jì)算無法與傳播的內(nèi)容關(guān)聯(lián)，不會(huì)隨著傳播內(nèi)容的變化而變化；而tsk-shell則試圖將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)傳播內(nèi)容2種異質(zhì)關(guān)聯(lián)的信息有效地融合起來，從而將經(jīng)典k-shell算法擴(kuò)展出內(nèi)容分析的能力，使其能夠融合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)傳播內(nèi)容2種常用卻異質(zhì)的信息，進(jìn)一步提升其在社交網(wǎng)絡(luò)傳播者影響力分析上的優(yōu)勢.

1 相關(guān)工作

總的來講，社交網(wǎng)絡(luò)中發(fā)現(xiàn)高影響力傳播者的研究可以大致分成3類：1)基于網(wǎng)絡(luò)拓?fù)涞姆椒ǎ?)拓?fù)浜陀脩粜袨槁?lián)合建模的方法；3)拓?fù)浜托畔?nèi)容聯(lián)合建模的方法.

基于網(wǎng)絡(luò)拓?fù)涞姆椒兇庖跃W(wǎng)絡(luò)結(jié)構(gòu)為用戶傳播影響力的分析基礎(chǔ)，其代表性方法主要包括度中心性、介數(shù)中心性(betweenness centrality)、k-shell[2]分解方法等.度中心性是一種比較直接的方法，認(rèn)為網(wǎng)絡(luò)中用戶節(jié)點(diǎn)的度越大，則該用戶影響力越高；介數(shù)中心性是指網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該點(diǎn)的邊的比例，比例越高，節(jié)點(diǎn)影響力越大；k-shell分解方法描述了節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置信息，越靠近網(wǎng)絡(luò)核心的節(jié)點(diǎn)影響力越高.文獻(xiàn)[2]證明在復(fù)雜網(wǎng)絡(luò)中，在只有一個(gè)傳播源點(diǎn)的前提條件下，最有效的傳播者不是度中心性最大的節(jié)點(diǎn)，也不是介數(shù)中心性指示的位于網(wǎng)絡(luò)中心的節(jié)點(diǎn)，而是由k-shell分解算法得到的位于網(wǎng)絡(luò)核心的節(jié)點(diǎn).k-shell算法時(shí)間復(fù)雜度為O(N+E)[10]，N和E分別表示節(jié)點(diǎn)數(shù)和邊數(shù)，由于時(shí)間復(fù)雜度低，其經(jīng)常被應(yīng)用于大規(guī)模網(wǎng)絡(luò)的分析.但是，k-shell算法會(huì)造成多個(gè)節(jié)點(diǎn)被分配到同一個(gè)索引值ks，而屬于同一ks索引值的節(jié)點(diǎn)無法區(qū)分其傳播能力.為了克服上述弱點(diǎn)，Zeng等人[11]提出了基于混合度(mixed degree decomposition， MDD)的k-shell分解算法，MDD在計(jì)算節(jié)點(diǎn)權(quán)重時(shí)同時(shí)考慮了剩余邊和刪除邊，達(dá)到了更加細(xì)致的劃分效果.文獻(xiàn)[9]同時(shí)考慮了網(wǎng)絡(luò)中節(jié)點(diǎn)度和連邊權(quán)重的影響，提出了加權(quán)k-shell分解方法，該方法可以更準(zhǔn)確地估計(jì)一個(gè)節(jié)點(diǎn)的重要程度.上述基于網(wǎng)絡(luò)拓?fù)涞姆椒ǎ瑑?yōu)點(diǎn)是直觀、速度快，但缺少對(duì)網(wǎng)絡(luò)用戶行為或網(wǎng)絡(luò)信息內(nèi)容的建模能力，因而對(duì)網(wǎng)絡(luò)上信息傳播過程中用戶真實(shí)的傳播影響力的分析能力還有進(jìn)一步提升的空間.

聯(lián)合用戶行為和拓?fù)浣５姆椒ㄖ?，代表性方法是IP[12](influence and passivity). IP提出了與HITS類似的算法來迭代計(jì)算用戶的影響力和被動(dòng)性(passivity)，其中一個(gè)用戶的影響力打分取決于他影響的用戶個(gè)數(shù)以及這些用戶的被動(dòng)性打分.一個(gè)用戶的被動(dòng)性打分，取決于他試圖影響他但被他拒絕的用戶個(gè)數(shù)及其影響力打分.容易看出IP算法中計(jì)算影響力和被動(dòng)性的方式，與HITS算法中迭代計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)hub值和authority值的方式類似.該類方法的先進(jìn)性在于它不但充分利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，而且能夠利用用戶的行為特征幫助提升傳播影響力建模的準(zhǔn)確性.但同樣地，該方法仍然沒有深入到傳播信息的內(nèi)容層面進(jìn)行分析，無法區(qū)分用戶在不同話題上的傳播影響力大小.此外，相較k-shell算法而言，該算法的時(shí)間復(fù)雜度也比較高.

信息內(nèi)容和網(wǎng)絡(luò)拓?fù)渎?lián)合建模的方法中，具有代表性的是TwitterRank[1]，TAP(topical affinity propagation)[13]等.TwitterRank在PageRank算法的轉(zhuǎn)移概率中加入了話題和用戶活躍程度來度量用戶的興趣.TAP提出了話題因子圖(topical factor graph， TFG)模型來建模網(wǎng)絡(luò)用戶在不同話題下的影響關(guān)系，在共同作者網(wǎng)絡(luò)、引文關(guān)系網(wǎng)絡(luò)和電影-導(dǎo)演-演員-編劇關(guān)系網(wǎng)絡(luò)定量和定性分析上都取得了不錯(cuò)的計(jì)算效果，其算法若采用傳統(tǒng)的子集和法求解，計(jì)算復(fù)雜度高，無法適應(yīng)大規(guī)模數(shù)據(jù)，針對(duì)該問題，作者又提出了一個(gè)并行的分布式求解算法.此外，作者實(shí)驗(yàn)的3個(gè)網(wǎng)絡(luò)都很容易獲得規(guī)范的元信息數(shù)據(jù)，比如論文話題類別、電影類別等，而在Twitter、微博等社交媒體網(wǎng)絡(luò)上常常無法直接獲得這類關(guān)鍵信息.

綜上所述，傳統(tǒng)的發(fā)現(xiàn)高影響力傳播者的算法，要么脫離話題建模用戶的社會(huì)影響力[2,9,11-12]；要么認(rèn)為話題影響力是固定的[1,13]，無法跟隨內(nèi)容的變化而改變，消弱了實(shí)踐應(yīng)用價(jià)值.而k-shell算法具有簡單、直觀、高效等特點(diǎn)，因此，本文在考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，向k-shell引入話題和用戶交互行為的作用，提出了tsk-shell算法，以期在保持其簡潔高效優(yōu)勢的同時(shí)，擴(kuò)展出其利用社交網(wǎng)絡(luò)中內(nèi)容話題的能力，提升其建模社交網(wǎng)絡(luò)用戶傳播影響力建模的有效性.

2 話題敏感的k-Shell分解

傳統(tǒng)k-shell分解方法，通過遞歸的方式依次刪除網(wǎng)絡(luò)中度最小的節(jié)點(diǎn)，將網(wǎng)絡(luò)劃分成不同的子結(jié)構(gòu).對(duì)屬于不同子結(jié)構(gòu)的節(jié)點(diǎn)賦予一個(gè)k-shell索引值，ks反映了節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，ks越大，節(jié)點(diǎn)越靠近網(wǎng)絡(luò)中心，其傳播影響力被認(rèn)為越大，反之，ks越小，節(jié)點(diǎn)離網(wǎng)絡(luò)中心越遠(yuǎn)，其傳播影響力被認(rèn)為越小.社交網(wǎng)絡(luò)中傳播者的影響力不但與拓?fù)浣Y(jié)構(gòu)有關(guān)，而且是隨著不同的話題發(fā)生變化的，為了區(qū)分不同話題下的用戶傳播行為，我們需要在考慮拓?fù)溆绊懙耐瑫r(shí)，建模話題對(duì)傳播行為的影響.直觀的想法，是將用戶之間基于話題的轉(zhuǎn)發(fā)關(guān)系，同k-shell框架下節(jié)點(diǎn)“度”的概念關(guān)聯(lián)起來.借鑒Garas等人[9]提出的方法，融合拓?fù)浣Y(jié)構(gòu)和話題影響力權(quán)重的節(jié)點(diǎn)度計(jì)算方式，如式(1)所示：

(1)

(2)

用戶的話題影響力被轉(zhuǎn)化為社交網(wǎng)絡(luò)中關(guān)系的權(quán)重，然后，加權(quán)的k-shell分解算法被用來尋找消息集合D所代表話題中最有影響力的傳播者.tsk-shell首次將話題影響力和k-shell分解方法結(jié)合起來尋找社交網(wǎng)絡(luò)中話題相關(guān)的高影響力傳播者.

2.1 話題加權(quán)的社交網(wǎng)絡(luò)結(jié)構(gòu)

tsk-shell算法的關(guān)鍵在于如何根據(jù)Twitter網(wǎng)絡(luò)中的歷史數(shù)據(jù)和網(wǎng)絡(luò)結(jié)構(gòu)生成一個(gè)話題敏感的加權(quán)網(wǎng)絡(luò).算法考慮了以下3種因素：1)用戶產(chǎn)生內(nèi)容，用戶的興趣反映了其對(duì)話題的偏好程度，而用戶的歷史消息(包括原創(chuàng)和轉(zhuǎn)發(fā))可以用來推斷用戶在不同話題上的興趣分布；2)用戶的關(guān)注關(guān)系，由于Twitter網(wǎng)絡(luò)中的同質(zhì)性[1]的現(xiàn)象，關(guān)注關(guān)系表示了用戶之間興趣的相似性，可以在一定程度上反映用戶之間的話題影響力，但是這種影響力是一般意義上的、定性的，不能夠精確度量用戶在某個(gè)話題上的影響力；3)用戶的轉(zhuǎn)發(fā)行為，轉(zhuǎn)發(fā)行為是用戶對(duì)某個(gè)話題感興趣的重要特征，也是網(wǎng)絡(luò)中信息傳播的動(dòng)力.

基于上述觀察，Twitter網(wǎng)絡(luò)中的用戶產(chǎn)生內(nèi)容、關(guān)注網(wǎng)絡(luò)和用戶轉(zhuǎn)發(fā)行為，被聯(lián)合用來建模兩兩用戶之間的話題傳播影響力.對(duì)于社交網(wǎng)絡(luò)中存在連接關(guān)系的任意2個(gè)用戶，用戶之間的影響力被定義為某個(gè)話題分布下的條件概率.在Twitter網(wǎng)絡(luò)中，由于關(guān)注關(guān)系是有向的，影響力也是有方向的，即影響力的方向是從被關(guān)注的用戶指向關(guān)注他的用戶.為了描述方便，預(yù)先定義一組符號(hào)，如表1所示：

Table 1 The Symbol Table表1 符號(hào)表

在考慮話題的情況下，轉(zhuǎn)發(fā)的消息被映射到一個(gè)主題向量空間中，t，Ru v，V三個(gè)變量的關(guān)系表示如圖1所示：

Fig. 1 Graphical representation of topical influence圖1 話題影響力的概率圖表示

用戶v對(duì)u在話題t下的影響力可以定義為條件概率P(Ru v|Vt)，即對(duì)于主題t，在事件V已經(jīng)發(fā)生的條件下事件發(fā)生的概率.由于P(Ru v|Vt)不便于直接求解，通過貝葉斯公式得到式(3)：

(3)

P(t|V) 表示用戶v發(fā)布的消息中主題t出現(xiàn)的概率，可以用式(4)表示：

(4)

其中，I(m,t)為指示函數(shù)，若消息m的主題為t，則I(m,t)=1，否則I(m,t)=0.P(Ru vt|V)表示在Dv中被用戶u轉(zhuǎn)發(fā)且主題為t的概率，可以通過式(5)計(jì)算：

(5)

綜合式(3)～(5)，可得出式(6)：

(6)

事實(shí)上，一條消息可能包含不止一個(gè)主題，為了更加細(xì)粒度地劃分話題，我們以詞為單位進(jìn)行統(tǒng)計(jì)，設(shè)P(t|m)表示消息m中主題為t的詞出現(xiàn)的概率，則式(6)可以進(jìn)一步表示為式(7)：

在實(shí)際應(yīng)用中，話題常常由多條描述相關(guān)內(nèi)容的消息集合組成，對(duì)于某個(gè)給定的待預(yù)測的消息集合D，按照式(2)，在消息集合D上，用戶v對(duì)u的話題影響力可以由式(8)計(jì)算：

(8)

最后將P(Ru v|VD)作為社交網(wǎng)絡(luò)中關(guān)系的權(quán)重，執(zhí)行帶權(quán)重的k-shell的分解得到消息集合D代表的話題下的高影響力傳播者.式(7)中的P(t|m)，通過LDA[14]( latent Dirichlet allocation)主題模型對(duì)用戶歷史消息進(jìn)行估計(jì)得到，式(8)中的P(t|D)通過訓(xùn)練好的LDA模型推斷得到.

2.2 tsk-shell算法

按照2.1節(jié)描述，tsk-shell算法的完整過程如算法1所示：

算法1.tsk-shell算法.

訓(xùn)練階段：

1) 由LDA模型得到每個(gè)消息的主題分布P(t|m);

2) 由式(7)計(jì)算社交網(wǎng)絡(luò)中相連用戶之間主題相關(guān)的轉(zhuǎn)發(fā)概率P(Ru v|Vt).

預(yù)測階段：

1) 由LDA推斷出待預(yù)測消息集合的主題分布，即話題;

2) 利用式(8)計(jì)算該話題下，網(wǎng)絡(luò)中相連用戶之間的轉(zhuǎn)發(fā)概率P(Ru v|VD);

3) 結(jié)合式(1)的權(quán)重計(jì)算，迭代計(jì)算加權(quán)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的k-shell索引值;

4) 按照k-shell索引值估計(jì)該話題下用戶傳播影響力的大小.

算法1的過程分為訓(xùn)練和預(yù)測2個(gè)階段，在訓(xùn)練階段，將社交網(wǎng)絡(luò)中的連接關(guān)系轉(zhuǎn)化為主題相關(guān)的轉(zhuǎn)發(fā)概率圖；在預(yù)測階段，首先推斷出待預(yù)測的消息集合話題的主題分布，接著計(jì)算出話題加權(quán)的社交網(wǎng)絡(luò)，最后采用加權(quán)的k-shell分解方法計(jì)算出每個(gè)用戶的k-shell索引值，作為用戶話題相關(guān)的傳播影響力的估計(jì).

3 實(shí)驗(yàn)評(píng)估

在本節(jié)中，我們通過真實(shí)的Twitter網(wǎng)絡(luò)中傳播實(shí)例對(duì)算法的效果進(jìn)行了驗(yàn)證，我們首先給出了tsk-shell關(guān)于幾個(gè)基準(zhǔn)方法，如PageRank、度、k-shell在效果上的定量對(duì)比；然后為了給出一個(gè)直觀認(rèn)識(shí)，我們又給出了tsk-shell和傳統(tǒng)k-shell方法在醫(yī)改話題上的定性對(duì)比結(jié)果.

3.1 數(shù)據(jù)集

原始數(shù)據(jù)集為2009-06-01—2009-12-31采集的Twitter數(shù)據(jù)集，其中包括4.76億條tweets消息[15].

實(shí)驗(yàn)抽取2009年6月和7月的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，在經(jīng)過分詞去除高頻和低頻詞，得到歷史tweets數(shù)(包括發(fā)布和轉(zhuǎn)發(fā))大于等于3的有效用戶數(shù)3 200 521個(gè).在有效用戶的tweets中，從包含轉(zhuǎn)發(fā)關(guān)系，即含有RT @name和via @name字符串模式的tweets中，進(jìn)一步提取用戶間的轉(zhuǎn)發(fā)關(guān)系，共發(fā)現(xiàn)存在有效轉(zhuǎn)發(fā)消息的用戶對(duì)3 352 337個(gè).將有效用戶的歷史數(shù)據(jù)用LDA模型進(jìn)行訓(xùn)練，設(shè)主題個(gè)數(shù)k=100，得到每個(gè)消息的主題分布，然后，通過式(7)計(jì)算每個(gè)有效用戶對(duì)在各個(gè)主題下的影響力權(quán)重.

實(shí)驗(yàn)抽取2009年8月的數(shù)據(jù)作為預(yù)測數(shù)據(jù).利用主題模型選取其中流行的3個(gè)話題預(yù)測，即甲型H1N1流感疫情、奧巴馬醫(yī)保改革和邁克爾·杰克遜逝世作為預(yù)測數(shù)據(jù).利用每個(gè)話題的高頻關(guān)鍵詞抽取相應(yīng)的轉(zhuǎn)發(fā)tweets和參與的用戶，利用文獻(xiàn)[16]采集的社交關(guān)系構(gòu)建用戶的關(guān)注關(guān)系網(wǎng)絡(luò)，利用式(8)計(jì)算每個(gè)特定話題下的關(guān)系權(quán)重.在執(zhí)行加權(quán)的k-shell分解算法時(shí)，式(1)中的參數(shù)取α=1，β=1.

3.2 評(píng)估標(biāo)準(zhǔn)

在社交網(wǎng)絡(luò)的信息傳播中，信息傳播過程可能從少數(shù)的幾個(gè)點(diǎn)開始，沿著網(wǎng)絡(luò)的社交結(jié)構(gòu)進(jìn)行傳播；此外，用戶也可能會(huì)通過搜索引擎或外部的環(huán)境獲取并發(fā)布信息，這造成了影響信息傳播因素的多樣性和分析的困難.在本實(shí)驗(yàn)中，為了簡化問題，便于分析，采用了文獻(xiàn)[3]中的方法，即假設(shè)信息的傳播只發(fā)生在封閉的社交網(wǎng)絡(luò)中，并沿著可見的社交網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行，任一用戶在某一話題傳播過程中的影響力定義為，在該話題傳播結(jié)束后經(jīng)過N跳影響的用戶總數(shù)，實(shí)驗(yàn)中取N=2.該方法的優(yōu)點(diǎn)是，既考慮了用戶對(duì)直接鄰居的影響，又考慮了用戶對(duì)間接鄰居的影響，即用戶的直接影響力和間接影響力[17].圖2表示在Twitter網(wǎng)絡(luò)上的信息傳播示意圖，節(jié)點(diǎn)表示用戶，邊表示關(guān)注關(guān)系，如節(jié)點(diǎn)A和節(jié)點(diǎn)C之間的有向邊表示C關(guān)注了A.信息傳播的過程如下：最開始用戶A發(fā)表了一條消息，A的粉絲E，C，F(xiàn)轉(zhuǎn)發(fā)了這則消息，接著C的粉絲B、F的粉絲、H和J轉(zhuǎn)發(fā)這條消息，在H的粉絲I轉(zhuǎn)發(fā)了該消息后傳播結(jié)束.最終，節(jié)點(diǎn)A影響的范圍為集合SA={B，C，E，F(xiàn)，H，J}，節(jié)點(diǎn)F最終影響的范圍為集合SB={H，I，J}.用戶節(jié)點(diǎn)的影響力可以定義為最終影響范圍的集合大小，即A的影響力為|SA|，B的影響力為|SB|.通過該方法，可以在話題傳播結(jié)束后，計(jì)算出每個(gè)參與傳播用戶的真實(shí)影響力大小.在實(shí)驗(yàn)中，待預(yù)測的話題中涉及用戶的真實(shí)傳播影響力由此計(jì)算得出.

Fig. 2 Schematic diagram of the information propagation圖2 信息傳播示意圖

3.3 tsk-shell算法效果

1) 定量比較

本節(jié)將文中提出的算法tsk-shell與常用的尋找高影響力傳播者的度中心性，k-shell和PageRank等算法進(jìn)行對(duì)比，比較各種算法在預(yù)測傳播者影響力的正確性.其中，k-shell是目前證實(shí)的最好的發(fā)現(xiàn)有影響力傳播者的算法.上述4種算法的結(jié)果預(yù)測了用戶傳播影響力的相對(duì)大小，為用戶的一個(gè)排序，該結(jié)果將和3.2節(jié)中的評(píng)估標(biāo)準(zhǔn)進(jìn)行比較.本文采用Kendall’sτ和Spearman’sρ這2種相關(guān)系數(shù)進(jìn)行序的相似性比較，他們用來計(jì)算預(yù)測的用戶影響力排序和標(biāo)準(zhǔn)的用戶影響力排序之間的統(tǒng)計(jì)依賴關(guān)系，定義如下：

對(duì)于長度為n的樣本向量X和Y，分別將其轉(zhuǎn)化為每個(gè)樣本對(duì)應(yīng)的排序向量x和y，對(duì)于任意的2個(gè)觀測值(xi,yi)和(xj,yj)，如果xi>xj且yi>yj，或者xi

(9)

其中，cc表示一致觀測對(duì)的數(shù)量，dc表示不一致觀測對(duì)的數(shù)量.Spearman’sρ的定義為式(10)：

(10)

其中，di=xi-yi，表示2個(gè)排序值之差.

Fig. 3 Comparison of algorithms’ prediction performance (Kendall’s τ)圖3 算法預(yù)測性能比較(Kendall’s τ)

由于每個(gè)話題在傳播過程中的影響因素的復(fù)雜多樣性，每個(gè)話題傳播的過程不盡相同，因此，文中取算法對(duì)所有話題預(yù)測性能的平均值作為最后的結(jié)果.圖3和圖4分別比較了4種算法分別運(yùn)用Kendall’sτ和Spearman’sρ這2種相關(guān)系數(shù)的比較結(jié)果.可以得出，本文提出的tsk-shell算法在發(fā)現(xiàn)最有影響力的topk個(gè)傳播者方面超過了傳統(tǒng)的算法，其中比最好的k-shell算法性能平均提高了40%.

Fig. 4 Comparison of algorithms’ prediction performance (Spearman’s ρ)圖4 算法預(yù)測性能比較(Spearman’s ρ)

2) 定性比較

為了給出一個(gè)更為直觀的認(rèn)識(shí)，表2給出了在奧巴馬醫(yī)改計(jì)劃話題中分別利用k-shell和tsk-shell算法得出的排名top 10的高影響力傳播用戶.

Table 2 Top 10 Users in the Obama Health Care Topic表2 在奧巴馬醫(yī)改話題中排名top 10的用戶

可以看出，2種結(jié)果中相同的用戶只有Barack-Obama和TheOnion，表示考慮了話題因素后結(jié)果有了顯著的變化.直觀上看，tsk-shell算法更加合理，如BarackObama是當(dāng)時(shí)奧巴馬發(fā)布Twitter的賬號(hào)，在奧巴馬醫(yī)改計(jì)劃這個(gè)話題中，奧巴馬無疑是最有影響力傳播者，要高于用戶reimagin；另外，tsk-shell算法發(fā)現(xiàn)的top 10高影響力傳播者中還有曾擔(dān)任小布什總統(tǒng)高級(jí)顧問的著名政治評(píng)論家Karl Rove.

4 結(jié) 論

k-shell算法是目前發(fā)現(xiàn)社交網(wǎng)絡(luò)中高影響力傳播者的效果較好的算法之一，但主要依賴拓?fù)浣Y(jié)構(gòu)分析用戶的傳播影響力，而缺少考量話題在信息傳播中的影響.本文基于不同用戶對(duì)不同話題感興趣的程度不同、同一用戶在不同話題下的影響力存在差異這一假設(shè)，將用戶間的話題影響關(guān)系建模進(jìn)社交網(wǎng)絡(luò)中用戶的度的概念，從而使傳統(tǒng)k-shell算法在保留拓?fù)浣Y(jié)構(gòu)分析能力、簡潔高效特性的同時(shí)，擴(kuò)展出利用網(wǎng)絡(luò)傳播內(nèi)容的話題信息的能力，提出了話題敏感的tsk-shell算法.該算法建模了話題對(duì)信息傳播的影響，并結(jié)合用戶交互行為和社交網(wǎng)絡(luò)結(jié)構(gòu)一起來發(fā)現(xiàn)特定話題下的高影響力傳播者.本文在Twitter數(shù)據(jù)集上利用真實(shí)的傳播實(shí)例對(duì)算法進(jìn)行了驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了話題對(duì)信息傳播具有重要影響，以及tsk-shell算法在發(fā)現(xiàn)話題相關(guān)的高影響力傳播者應(yīng)用中的有效性.

[1]Weng Jianshu, Lim E, Jiang Jing, et al. TwitterRank: Finding topic-sensitive influential twitterers[C] //Proc of the 3rd ACM Int Conf on Web Search and Data Mining. New York: ACM, 2010: 261-270

[2]Kitsak K, Gallos K L, Havlin S, et al. Identifying influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893

[3]Pei Sen, Muchnik L, Andrade J S, et al. Searching for superspreaders of information in real-world social media[J]. Scientific Reports, 2014, 4: 5547-5547

[4] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the Web, SIDL-WP-1999-0120[R]. Palo Alto: the Stanford InfoLab, 1999: 1-14

[5] Barbieri N, Bonchi F, Manco G. Topic-aware social influence propagation models[J]. Knowledge and Information Systems, 2013, 37(3): 555-584

[6] Bi B, Tian Y, Sismanis Y, et al. Scalable topic-specific influence analysis on microblogs[C] //Proc of the 7th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2014: 513-522

[7] Wu Xindong, Li Yi, Li Lei. Influence analysis of online social network[J]. Chinese Journal of Computers, 2014, 37(4): 735-752 (in Chinese)(吳信東, 李毅, 李磊. 在線社交網(wǎng)絡(luò)影響力分析[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 735-752)

[8]Ding Zhaoyun, Zhou Bin, Jia Yan, et al. Topical influence analysis based on the multi-relational network in microblogs[J]. Journal of Computer Research and Development, 2013, 50(10): 2155-2175) (in Chinese)(丁兆云, 周斌, 賈焰, 等. 微博中基于多關(guān)系網(wǎng)絡(luò)的話題層次影響力分析[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(10): 2155-2175)

[9]Garas A, Schweitzer F, Havlin S. Ak-shell decomposition method for weighted networks[J]. New Journal of Physics, 2012, 14(8): 1-17

[10] Batagelj V, Zaversnik M. AnO(m) algorithm for cores decomposition of networks[J]. Advances in Data Analysis and Classification, 2011, 5(2): 129-145

[11]Zeng An, Zhang Chengjun. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013, 377(14): 1031-1035

[12]Romero M D, Galuba W, Asur S, et al. Influence and passivity in social media[C] //Proc of the 20th Int Conf Companion on World Wide Web. New York: ACM, 2011: 18-33

[13]Tang Jie, Sun Jimeng, Wang Chi, et al. Social influence analysis in large-scale networks[C] //Proc of the 15th ACM Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2009: 807-816

[14]Blei D, Ng A, Jordan M. Latent Dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3(1): 993-1022

[15]Yang J, Leskovec J. Patterns of temporal variation in online media[C] //Proc of the 4th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2011: 177-186

[16]Kwak H, Lee C, Park H, et al. What is Twitter, a social network or a news media?[C] //Proc of the 19th Int Conf on World Wide Web. New York: ACM, 2010: 591-600

[17]Liu Lu, Tang Jie, Han Jiawei, et al. Mining topic-level influence in heterogeneous networks[C] //Proc of the 19th ACM Int Conf on Information and Knowledge Management. New York: ACM, 2010: 199-208

Gou Chengcheng, born in 1985. PhD candidate. His main research interests include Web search and mining, machine learning and social network.

Du Pan, born in 1981. PhD. His main research interests include Web search and mining, machine learning and social network (dupan@software.ict.ac.cn).

He Min, born in 1982. PhD. Her main research interests include natural language process, Web mining and information security(heminsmile@163.com).

Liu Yue, born in 1971. PhD. Associate professor. Her main research interests include information retrieval and Web mining(liuyue@ict.ac.cn).

Cheng Xueqi, born in 1971. PhD. Currently professor and PhD supervisor in the Institute of Computing Technology, Chinese Academy of Sciences. His main research interests include network information security, large-scale information retrieval and knowledge mining (cxq@ict.ac.cn).

tsk-shell: An Algorithm for Finding Topic-Sensitive Influential Spreaders

Gou Chengcheng1,2, Du Pan1, He Min1,2,3, Liu Yue1, and Cheng Xueqi1

1(CASKeyLaboratoryofNetworkDataScienceandTechnology(InstituteofComputingTechnology,ChineseAcademyofSciences),Beijing100190)2(UniversityofChineseAcademyofSciences,Beijing100049)3(NationalComputerNetworkandInformationSecurityManagementCenter,Beijing100029)

Discovering influential spreaders is a valuable task in social networks, especially for the popularity prediction and analysis of online contents on microblogs, such as Twitter and Weibo. Thek-shell decomposition (k-core), which identifies influential spreaders located in the core of a network, attracts more attention due to its simpleness and effectiveness compared with various related methods, such as indegree, betweenness centrality and PageRank. However,k-shell method only considers the factor of the network position of nodes and ignores the impacts of the content itself in information diffusion. The content itself plays an important role in the process of diffusion. For example, ones just retweet their interested tweets in microblogs. The spread ability of users depends not only on topology structures but also on the published contents, and therefore a unified model considering the two aspects simultaneously is proposed to model users’ influence. Specifically, the topics hidden in user generated contents (UGC) are exploited to model the users’ propagation probability and a topic-sensitivek-shell (tsk-shell) decomposition algorithm is proposed. Experimental studies on a real Twitter dataset show that the tsk-shell outperforms traditionalk-shell by 40% on average in the task of finding topkinfluential users, which proves the effectiveness of the tsk-shell algorithm.

influential spreader;k-shell decomposition; social network; information diffusion; propagation probability；microblogs

2015-09-15；

2015-12-25

國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2012CB316303, 2014CB340401)；國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2015AA015803,2014AA015204)；中國科學(xué)院重點(diǎn)部署項(xiàng)目(KGZD-EW-T03-2)；國家自然科學(xué)基金項(xiàng)目(61232010,61572473,61303156,61502447)；國家242信息安全計(jì)劃基金項(xiàng)目(2015F028)；山東省自主創(chuàng)新及成果轉(zhuǎn)化專項(xiàng)(2014CGZH1103)；歐盟第七科技框架計(jì)劃項(xiàng)目(FP7)(PIRSES-GA-2012-318939) This work was supported by the National Basic Research Program of China (973 Program) (2012CB316303, 2014CB340401), the National High Technology Research and Development Program of China (863 Program) (2015AA015803, 2014AA015204), the Key Research Program of the Chinese Academy of Sciences (KGZD-EW-T03-2), the National Natural Science Foundation of China (61232010, 61572473, 61303156, 61502447), the National 242 Information Security Program (2015F028), the Shandong Province Independent Innovation and Achievements Transformation Special Program (2014CGZH1103), and the 7th Framework Programme of Europe Union (FP7) (PIRSES-GA-2012-318939).

TP391