黃俊銘， 沈華偉， 程學(xué)旗

(中國科學(xué)院 計算技術(shù)研究所，中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室，北京 100190)

利用社交網(wǎng)絡(luò)的影響力骨架探索信息傳播

黃俊銘， 沈華偉， 程學(xué)旗

(中國科學(xué)院 計算技術(shù)研究所，中國科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點實驗室，北京 100190)

理解社交網(wǎng)絡(luò)上的信息傳播機制，通常包括對拓撲結(jié)構(gòu)的分析和對用戶行為的分析。由于社交網(wǎng)絡(luò)上連邊的強度具有異質(zhì)性，只有一部分連邊對于信息傳播有實質(zhì)作用，構(gòu)成隱藏在社交網(wǎng)絡(luò)中的影響力骨架。對影響力骨架的拓撲研究可幫助我們獲得比直接研究社交網(wǎng)絡(luò)拓撲結(jié)構(gòu)更深入的認識。我們從連邊正負性和個體節(jié)點角色分化入手，探討了微觀層面連邊和節(jié)點在信息傳播中的作用，進而從宏觀層面分析信息傳播所依賴的影響力骨架的連通性和擴散效率，發(fā)現(xiàn)信息傳播具有一定程度的脆弱性，且其傳播效率低于對社交網(wǎng)絡(luò)本身研究的預(yù)期。

信息傳播；社交網(wǎng)絡(luò)；影響力骨架

1 引言

近年來社交網(wǎng)絡(luò)的飛速發(fā)展，海量的信息通過社交網(wǎng)絡(luò)分發(fā)、共享和傳播，對大規(guī)模人群的線上和線下生活產(chǎn)生不可忽視的影響。例如，人們在Twitter和新浪微博上傳播身邊的新聞，或是在Facebook和豆瓣上交換對于音樂的看法。隨著社交網(wǎng)絡(luò)上的信息傳播逐漸衍生為蘊含豐富價值的大數(shù)據(jù)來源，利用信息傳播數(shù)據(jù)預(yù)測政治[1]、分析金融[2]、指導(dǎo)市場營銷[3]、預(yù)警疾病傳播[4]等數(shù)據(jù)挖掘應(yīng)用逐漸興起，使得理解信息傳播的機制成為具有兼具研究價值和現(xiàn)實意義的重要問題[5]。

對信息傳播的分析通常包括基于拓撲結(jié)構(gòu)的分析和基于行為歷史的分析。一些研究者分析社交網(wǎng)絡(luò)的拓撲結(jié)構(gòu)對于信息傳播的速度、范圍、廣度等指標的影響，希望尋找對信息傳播具有指導(dǎo)性意義的網(wǎng)絡(luò)拓撲機制，例如，探討復(fù)雜網(wǎng)絡(luò)的小世界性質(zhì)對信息傳播速度的影響[6]，利用信息傳播隨機跳轉(zhuǎn)的平穩(wěn)分布尋找關(guān)鍵節(jié)點[7]，討論結(jié)構(gòu)洞節(jié)點對于信息傳播的影響[8]，揭示局部拓撲結(jié)構(gòu)的多樣性對于個體信息傳播的決定性作用[9]，分析信息傳播早期人群局部拓撲性質(zhì)[10]等。另一些研究者對社交網(wǎng)絡(luò)中信息傳播參與者的行為歷史進行大規(guī)模分析以尋找信息傳播的統(tǒng)計規(guī)律，例如，通過信息傳播歷史估計信息傳播概率[11-14]，討論用戶評價對于信息傳播的影響[15]，分析不同性別、年齡等人口學(xué)因素對信息傳播的差異化作用[16]，擬合新信息隨時間衰減的趨勢[17]，評估信息傳播中蘊含的信任程度[18]等。對拓撲結(jié)構(gòu)和行為歷史的分析，從不同側(cè)面豐富了對信息傳播機制的定性認識，能夠更準確地指導(dǎo)針對信息傳播的定量應(yīng)用。

然而，作為兩種主流分析方法之一的拓撲結(jié)構(gòu)分析，目前幾乎所有的工作都集中于分析社交網(wǎng)絡(luò)本身的拓撲結(jié)構(gòu)。事實上，社交網(wǎng)絡(luò)中連接人與人的連邊并不是全同的，而是具有非常顯著的異質(zhì)性，不同的連邊有不同程度的信任和影響力[19]。事實上，只有一小部分邊表達了顯著的信任和影響(稱為影響力邊)，能夠在實質(zhì)上推動信息傳播。我們相信，由影響力邊所構(gòu)成的社交網(wǎng)絡(luò)的子圖(稱為影響力骨架)的拓撲結(jié)構(gòu)提供了更精確了解信息傳播機制的拓撲途徑。相比于對社交網(wǎng)絡(luò)所有連邊不加區(qū)分地合并分析，集中討論影響力骨架或許能夠提供更深入的認識。因此，本文我們試圖從真實的社交網(wǎng)絡(luò)中提取影響力骨架，以之作為實證分析信息傳播的拓撲結(jié)構(gòu)的載體。

我們首先從微觀角度入手，利用社會平衡理論與度分化現(xiàn)象分析連邊和節(jié)點在信息傳播中的角色，探討了影響力邊的正負性和個體節(jié)點的主導(dǎo)者/追隨者兩種角色的分化現(xiàn)象。在微觀討論的基礎(chǔ)上，我們從宏觀層面分析影響力骨架的連通能力與擴散效率，發(fā)現(xiàn)信息傳播對于關(guān)鍵節(jié)點的依賴程度與信息傳播的擴散效率都與此前對社交網(wǎng)絡(luò)研究的結(jié)果存在顯著差異，被低估的脆弱性和被高估的傳播效率使得我們意識到需要重新審視基于信息傳播的各種量化應(yīng)用。

2 提取影響力骨架

2．1 數(shù)據(jù)準備

我們采集了結(jié)合在線社交網(wǎng)絡(luò)和在線分享的網(wǎng)站豆瓣網(wǎng)(www.Douban.com) 和Goodreads(www.Goodreads.com)的數(shù)據(jù)作為觀測對象。在這兩個網(wǎng)站上，用戶可以對電影、音樂和書籍評分，并關(guān)注其他用戶的行為。用戶之間的關(guān)注關(guān)系構(gòu)成了社交網(wǎng)絡(luò)，而對電影、音樂和書籍(統(tǒng)稱為對象)的評分意見作為信息在這一社交網(wǎng)絡(luò)上傳播(數(shù)據(jù)抓取于2010年8月)。我們從網(wǎng)站上若干個熱門討論組開始，抓取討論組成員的行為數(shù)據(jù)，并擴展到關(guān)注這些成員以及被他們關(guān)注的用戶，迭代直到不再能擴展到新的未抓取用戶。我們一共抓取了1 014 890位豆瓣用戶和912 973位Goodreads用戶，并移除了關(guān)注者少于五個或評分少于五次的不活躍用戶，因為這些用戶的可用數(shù)據(jù)太少，無法提供穩(wěn)定的統(tǒng)計結(jié)果。清洗整理后的數(shù)據(jù)如表1所示。

表1 采集數(shù)據(jù)說明

2．2 影響力骨架提取算法

(1)

表2 影響力骨架的統(tǒng)計

3 利用影響力骨架分析信息傳播

3．1 影響力邊的正負性

我們首先從符號網(wǎng)絡(luò)的角度分析影響力邊的正負性。符號網(wǎng)絡(luò)理論將網(wǎng)絡(luò)中的連邊分為表達積極關(guān)系的正邊和表達消極關(guān)系的負邊，許多復(fù)雜網(wǎng)絡(luò)中都存在正負邊對立的現(xiàn)象。理解影響力邊的正負性對于預(yù)測信息傳播有重要的理論意義。若影響力是正關(guān)系，則信息傳播的效果是讓群體意見趨向一致。若影響力是負關(guān)系，則信息傳播的效果是讓群體分裂成多個意見集團。

我們計算了影響力骨架的連邊互惠系數(shù)，較高的互惠系數(shù)是正邊的標識之一。雖然兩個數(shù)據(jù)集上的影響力骨架的互惠系數(shù)相比于原網(wǎng)絡(luò)有大幅度降低，但仍然高于隨機抽取相同大小的隨機子圖的互惠系數(shù)，如表2所示。進一步地，我們利用社會平衡理論[22]檢驗影響力骨架中的三角形統(tǒng)計。社會平衡理論認為，如果三個個體之間的三條連邊全為正關(guān)系，則這個三角形處于平衡態(tài)，可以穩(wěn)定存在；反之若全為負關(guān)系則難以穩(wěn)定存在。在影響力骨架中，任意三個用戶之間的影響力若能構(gòu)成三角形，無外乎傳遞(a->b,b->c,a->c)和循環(huán)(a->b,b->c,c->a)兩種情況(若存在雙向邊，視為構(gòu)成兩個不同的三角形)。我們將影響力邊全部隨機重連，計算100次隨機實驗中這兩種三角形在隨機狀態(tài)下的期望個數(shù)，與實際影響力骨架中兩種三角形的個數(shù)相比。若一種三角形的實際個數(shù)遠大于期望個數(shù)，表明這種三角形能穩(wěn)定存在，反之則表明不能穩(wěn)定存在。

如表3所示，兩種三角的實際個數(shù)都遠遠大于期望個數(shù)。以z-score度量的顯著水平表明這一現(xiàn)象并非由于隨機誤差導(dǎo)致，而是由于影響力骨架中的三角形處于平衡態(tài)，從而能大量穩(wěn)定存在。這表明影響力邊表征了用戶之間的正關(guān)系，信息傳播的結(jié)果是使得相鄰個體的態(tài)度趨向一致。

表3 社會平衡理論檢驗影響力邊的正負性

3．2 個體角色分化

信息傳播中的個體作為社交網(wǎng)絡(luò)上的節(jié)點，度中心度對于理解個體在信息傳播中的地位有較好的指示作用。在原社交網(wǎng)絡(luò)中，由于互惠系數(shù)較高，大部分節(jié)點的出度入度幾乎相等。而在互惠系數(shù)大幅降低的影響力骨架中，節(jié)點的出度和入度產(chǎn)生了明顯的分化，這種分化表明了個體在信息傳播中處于不同的地位。

圖1為每個節(jié)點的出度-入度分布圖。在豆瓣和Goodreads兩個社交網(wǎng)絡(luò)中可以看到一個明顯的趨勢，大部分樣本點集中在y=x直線附近，其出度與入度表現(xiàn)出強烈的相關(guān)性，表明大部分節(jié)點傾向于保持相等的出度和入度。在影響力骨架中幾乎不存在這一趨勢，很多樣本點分布在遠離y=x直線的位置，表明影響力骨架中相當一部分節(jié)點的出度入度是嚴重不平衡的。為了更清晰地展示這一趨勢，我們對每個節(jié)點計算其出度入度之比的對數(shù)。如圖2所示，在兩個社交網(wǎng)絡(luò)中大部分節(jié)點集中在對數(shù)為0的位置，表明其出度入度基本一致。而在兩個影響力骨架中，雖然仍有不少節(jié)點集中在對數(shù)為0的位置，但兩側(cè)有明顯的多個分布峰，表明有相當一部分節(jié)點的出度遠大于入度，亦有相當一部分節(jié)點的入度遠大于出度。這一普遍的不平衡性現(xiàn)象背后是節(jié)點角色的分化。出度遠大于入度的節(jié)點，對應(yīng)的用戶能夠?qū)σ欢〝?shù)量的人群產(chǎn)生實質(zhì)影響，同時自己受到他人的影響較小，在社交網(wǎng)絡(luò)上的信息傳播中常常扮演主導(dǎo)者的角色。與之對稱的，入度遠大于出度的節(jié)點，對應(yīng)的用戶會受到較多人的影響，而自己影響他人的能力有限，在信息傳播中常常扮演追隨者的角色。這兩類人群的分化，使得信息能夠有效地從主導(dǎo)者傳播到追隨者，構(gòu)成了信息擴散的微觀機制。

圖1 原社交網(wǎng)絡(luò)和影響力骨架的出度-入度分布圖

圖2 節(jié)點出度入度之比的對數(shù)分布

圖 2(續(xù))

為了進一步分析這種不平衡性，我們選擇出度為某一特定值的節(jié)點計算其平均入度，畫出平均入度關(guān)于出度分布的散點圖，以分析給定影響力能力的人群受到影響的程度。毫無意外地，兩個社交網(wǎng)絡(luò)的分布圖集中在y=x一線，即平均入度嚴格隨出度遞增，不再贅述。圖3左側(cè)兩圖給出了兩個影響力骨架上的分布情況。可以看到，隨著出度的增加，平均入度并沒有表現(xiàn)出相應(yīng)地增加，而是始終穩(wěn)定在一定水平線以下。豆瓣數(shù)據(jù)中，任何出度的節(jié)點的平均入度都在10以下。Goodreads數(shù)據(jù)中，任何出度的節(jié)點的平均入度穩(wěn)定在10左右(雖然較大出度的節(jié)點由于樣本數(shù)量少產(chǎn)生波動)。這表明，對具有任何程度影響力的人來說，能影響他的人數(shù)始終是有限的。對于影響力較大的人，雖然其關(guān)注的人相應(yīng)地較多(原社交網(wǎng)絡(luò)中入度隨出度遞增)，但是他所關(guān)注的人中能夠?qū)嵸|(zhì)影響他的人并不多。我們認為這是因為個體的信息處理能力是有限的，從而只能維持一個較小規(guī)模的信任對象群體，而不可能呈現(xiàn)無上界的線性增長。

相應(yīng)地，我們也選擇入度為某一特定值的節(jié)點計算其平均出度，畫出平均出度關(guān)于入度分布的散點圖，以分析給定受影響傾向的人群所具有的影響力。圖3右側(cè)兩圖給出了兩個影響力骨架上的分布情況。平均出度關(guān)于入度的分布在兩個數(shù)據(jù)集上表現(xiàn)出不同的趨勢。豆瓣表現(xiàn)出較弱的負相關(guān)性，入度越大的節(jié)點的平均出度越低， 表明容易受影響的用戶的影響力較弱。與之相反，Goodreads表現(xiàn)出一定程度的正相關(guān)性，入度越大的節(jié)點的平均出度越大，表明Goodreads社區(qū)中有較多的樞紐節(jié)點。這些樞紐節(jié)點具有較強的信息轉(zhuǎn)發(fā)能力，既能受到多個來源的影響，又能利用自己的高影響力將信息擴散出去。

3．3 傳播拓撲

在個體角色的微觀分析基礎(chǔ)上，我們進一步考察網(wǎng)絡(luò)的拓撲連通性，以便在宏觀層面討論信息傳播。我們在社交網(wǎng)絡(luò)和影響力骨架上分別隨機選擇一個節(jié)點，將其五階以內(nèi)的鄰居節(jié)點構(gòu)成的子圖作為局部切片，在一定程度上提供對網(wǎng)絡(luò)連通性的直觀認識。在豆瓣和Goodreads上重復(fù)多次實驗，所得切片結(jié)構(gòu)類似，篇幅所限僅在圖4中列出Good-reads的兩個切片。

從圖4中可以看到，Goodreads社交網(wǎng)絡(luò)的局部切片呈現(xiàn)出明顯的復(fù)連通性質(zhì)，任何兩個節(jié)點之間都有多條路徑可達。這是社交網(wǎng)絡(luò)作為復(fù)雜網(wǎng)絡(luò)的典型特征，路徑的冗余程度保證了連通能力的魯棒性，隨機移除少量節(jié)點并不會嚴重破壞網(wǎng)絡(luò)的連通性。同時，節(jié)點之間的相對地位是模糊的，缺乏清晰的拓撲結(jié)構(gòu)。與之形成鮮明對比的是，影響力骨架的局部切片表現(xiàn)出清晰的層級關(guān)系，接近于單連通的樹狀結(jié)構(gòu)，絕大多數(shù)節(jié)點只有一個父節(jié)點，任意兩個節(jié)點之間通常只有一條路徑。可以很容易把這一切片分成若干個小團體， 每個小團體是一個典型的星型結(jié)構(gòu)，由一個中心節(jié)點和一組邊緣節(jié)點構(gòu)成。中心節(jié)點在小團體中的重要地位遠遠超過邊緣節(jié)點，一方面它是連接外部的主要(常常是唯一)通道，承擔整個小團體的信息外源角色，另一方面它是連接內(nèi)部各個節(jié)點的橋節(jié)點，承擔小團體的內(nèi)部交互功能。

圖3 影響力骨架中，固定出度/入度的節(jié)點的平均入度/出度值(a)和(b)：豆瓣；(c)和(d)：Goodreads

圖4 Goodreads社交網(wǎng)絡(luò)(上圖)和影響力骨架(下圖)的局部切片

這兩個切片的顯著對比引發(fā)了我們對社交網(wǎng)絡(luò)的信息傳播能力的思考。從表面上看，社交網(wǎng)絡(luò)上的信息傳播的途徑是冗余而多樣化的，具有很強的魯棒性。但由于很多連邊并不具有實質(zhì)影響的能力，真實的信息傳播是沿著樹狀結(jié)構(gòu)的層級進行的。信息在一個個小團體之間傳遞，很多情況下信息必須到達每個小團體的中心節(jié)點才能接觸到圍繞在其周圍的邊緣節(jié)點。這些中心節(jié)點作為結(jié)構(gòu)洞大量存在，導(dǎo)致信息傳播嚴重依賴于這類節(jié)點。這提醒我們，真實信息傳播的抗干擾能力并不像直接分析社交網(wǎng)絡(luò)所表現(xiàn)出來的那么強，事實上只需要識別出具有結(jié)構(gòu)洞地位的局部中心節(jié)點就能有針對性地對信息傳播發(fā)起有效攻擊、監(jiān)測和干預(yù)。

3．4 傳播效率

圖5 豆瓣(左)和Goodreads(右)的社交網(wǎng)絡(luò)(圓圈)和影響力骨架(十字)的節(jié)點出度分布

圖6 豆瓣(左)和Goodreads(右)的社交網(wǎng)絡(luò)(實線)和影響力骨架(虛線)的節(jié)點覆蓋率，即出度排序靠前的一部分節(jié)點(橫軸)的出邊所能覆蓋的節(jié)點數(shù)(縱軸)

信息傳播的效率是信息傳播分析的重要尺度。能否從少量節(jié)點出發(fā)讓信息覆蓋大部分節(jié)點，體現(xiàn)了信息傳播的效率，構(gòu)成了病毒式營銷等各種應(yīng)用的基礎(chǔ)。在社交網(wǎng)絡(luò)中，節(jié)點的影響力通常被定義為節(jié)點作為信息源能夠把信息擴散到的范圍大小。雖然社交網(wǎng)絡(luò)和影響力骨架都具有相同的度分布(如圖5所示，社交網(wǎng)絡(luò)和影響力骨架的節(jié)點出度分布都服從冪律分布且冪指數(shù)接近)，但這并不保證它們具有相似的傳播效率。我們以大度節(jié)點的覆蓋能力作為網(wǎng)絡(luò)擴散能力的度量。將社交網(wǎng)絡(luò)中的節(jié)點按出度排序，選擇出度最大的一部分節(jié)點，觀察這些節(jié)點的出邊所能覆蓋的節(jié)點占全網(wǎng)的比例，類似于按出度選擇一組種子節(jié)點以激發(fā)病毒式營銷。我們看到，社交網(wǎng)絡(luò)上出度最大的20%的節(jié)點的出邊能夠覆蓋全網(wǎng)80%的節(jié)點，表明社交網(wǎng)絡(luò)是一個直徑較小且大多數(shù)節(jié)點圍繞在大度節(jié)點周圍的網(wǎng)絡(luò)。這樣的網(wǎng)絡(luò)具有高效的傳播能力，符合20-80帕累托定律，只需借助20%的高影響力者就可以將信息擴散到達80%的人群。然而，真實的信息傳播效率并沒有這么高。對影響力骨架進行同樣的分析，我們發(fā)現(xiàn)影響力骨架中出度最大的20%的節(jié)點只能覆蓋到全網(wǎng)50%的節(jié)點。要覆蓋全網(wǎng)80%的節(jié)點，我們需要動員出度排名靠前的60%的節(jié)點。影響力骨架較低的連邊密度和接近單連通的拓撲性質(zhì)是其主要因素。也就是說，要讓80%的人群“知道”某一觀點，只需發(fā)動少量高影響力者即可，但要讓80%的人群“同意”某一觀點，需要動員過半人群才能實現(xiàn)。這昂貴的動員成本表明，無論是病毒營銷還是輿論干預(yù)，其真實難度都高于我們此前對社交網(wǎng)絡(luò)分析所得的認識。

5 小結(jié)

社交網(wǎng)絡(luò)表征了信息傳播的基礎(chǔ)結(jié)構(gòu)，而通過量化用戶之間影響力提取的影響力骨架則表征了信息傳播的功能。這兩個網(wǎng)絡(luò)在各方面存在一定的差異，表明了結(jié)構(gòu)與功能的不一致性。我們認為影響力骨架體現(xiàn)了信息傳播的真實路徑和范圍，對其拓撲結(jié)構(gòu)分析可以幫助我們更準確地認識社交網(wǎng)絡(luò)上的信息傳播的規(guī)律。我們首先從符號網(wǎng)絡(luò)的角度探討了信息借以傳播的影響力邊的正負性，利用社會平衡理論驗證了影響力邊是正關(guān)系，指出信息傳播的結(jié)果是意見同步，即促使相鄰個體的態(tài)度趨向一致。在微觀層面，我們討論了個體在信息傳播中的角色分化，雖然社交網(wǎng)絡(luò)的高互惠系數(shù)導(dǎo)致絕大部分節(jié)點的出度入度平衡，難以劃分出清晰的角色。但在真實信息傳播中個體明顯分化為兩類不同的節(jié)點，即出度遠大于入度的主導(dǎo)者和入度遠大于出度的追隨者，信息在這兩類個體之間的傳播構(gòu)成了信息的微觀傳播機制。同時我們發(fā)現(xiàn)，對于任何個體，能真實影響到他的影響力來源總是有限的，這一現(xiàn)象可能歸因于個體接受信息的能力是有限的。在宏觀層面，我們討論了網(wǎng)絡(luò)的拓撲性質(zhì)對于信息傳播的影響。在冗余的復(fù)連通社交網(wǎng)絡(luò)上，真實信息傳播路徑更接近于單連通的樹狀結(jié)構(gòu)，信息在大小不一的星型結(jié)構(gòu)小團體之間跳轉(zhuǎn)，存在相當數(shù)量的結(jié)構(gòu)洞可以對信息傳播產(chǎn)生關(guān)鍵性影響。因此信息傳播的抗干擾能力是比較脆弱的，只需識別并控制結(jié)構(gòu)洞即可實現(xiàn)高效的攻擊和干預(yù)。最后我們討論了信息傳播效率。旨在“了解”的信息傳播符合傳統(tǒng)的20-80帕累托定律，只需動員20%的高影響力人群即可幫助信息到達80%的目標人群，但旨在“說服”的信息傳播的效率較低，需要動員過半的高影響力人群才能讓80%的目標人群接受一條信息，高昂的動員成本可能導(dǎo)致病毒營銷等信息傳播應(yīng)用的難度高于預(yù)期。

[1] Robert M Bond，et al. A 61-million-person experiment in social influence and political mobilization [J]. Nature, 2012, 489(7415): 295-298.

[2] Johan Bollen, Huina Mao. Twitter Mood as a Stock Market Predictor [J]. Computer, 2011, 44(10): 91-94.

[3] David Kempe, Jon Kleinberg, Eva Tardos. Maximizing the spread of influence through a social network [C]//Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining. Washington, D.C. 2003.

[4] Jeremy Ginsberg,et al. Detecting influenza epidemics using search engine query data [J]. Nature, 2009. 457(7232): 1012-1014.

[5] Jimeng Sun, Jie Tang. A Survey of Models and Algorithms for Social Influence Analysis [M]. Social Network Data Analytics. C. C. Aggarwal, Springer US, 2011: 177-214.

[6] Lü Linyuan, Chen Duan-Bing, Zhou Tao. The small world yields the most effective information spreading [J]. New Journal of Physics, 2011, 13(12): 123005.

[7] Lü Linyuan,et al. Leaders in Social Networks, the Delicious Case [J]. PLoS ONE, 2011, 6(6): e21202.

[8] Jie Tang, Tiancheng Lou, Jon Kleinberg. Inferring social ties across heterogenous networks [C]//Proceedings of the 5th ACM international conference on Web search and data mining. Seattle, Washington, USA, ACM, 2012: 743-752.

[9] Johan Ugander,et al. Structural diversity in social contagion [J]. Proceedings of the National Academy of Sciences, 2012, 109(16): 5962-5966.

[10] Peng Bao,et al. Popularity prediction in microblogging network: a case study on sina weibo [C]//Proceedings of the 22nd international conference on World Wide Web companion, Rio de Janeiro, Brazil, 2013

[11] Kazumi Saito,Ryohei Nakano, Masahiro Kimura. Prediction of Information Diffusion Probabilities for Independent Cascade Model [C]//Proceedings of the Knowledge-Based Intelligent Information and Engineering Systems. Springer Berlin Heidelberg. 2008: 67-75.

[12] Amit Goyal, Francesco Bonchi, Laks V S Lakshmanan. Learning influence probabilities in social networks [C]//Proceedings of the 3rd ACM international conference on Web search and data mining, New York, USA, ACM, 2010.

[13] Manuel Gomez-Rodriguez, Jure Leskovec, Andreas Krause. Inferring Networks of Diffusion and Influence [J]. ACM Trans. Knowl. Discov. Data, 2012, 5(4): 1-37.

[14] Manuel Gomez-Rodriguez, et al. Structure and dynamics of information pathways in online media [C]//Proceedings of the 6th ACM international conference on Web search and data mining, Rome, Italy, ACM, 2013.

[15] Paula Fitzgerald Bone. Word-of-mouth effects on short-term and long-term product judgments [J]. Journal of Business Research, 1995, 32(3): 213-223.

[16] Sinan Aral, Dylan Walker. Identifying influential and susceptible members of social networks [J]. Science, 2012, 337(6092):337-341.

[17] Fang Wu, Bernardo A. Huberman. Novelty and collective attention [J]. Proceedings of the National Academy of Sciences, 2007, 104(45): 17599-17601.

[18] MeredithRingel Morris, et al. Tweeting is believing? understanding microblog credibility perceptions [C]//Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work. Seattle, Washington, USA, ACM, 2012.

[19] Mark SGranovetter. The strength of weak ties [J]. American journal of sociology, 1973, 78(6): 1360-1380.

[20] Junming Huang, 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. Seattle, Washington, USA, ACM, 2012.

[21] Ruslan Salakhutdinov, Andriy Mnih. Probabilistic Matrix Factorization [J]. Advances in Neural Information Processing Systems 20. Cambridge, MA, MIT Press, 2008: 1257-1264.

[22] Heider F. Attitudes and cognitive organization [J]. Journal of Psychology, 1946, 21(1):107-112.

Understanding Information Propagations via Influence Backbone Analysis on Social Networks

HUANG Junming, SHEN Huawei, CHENG Xueqi

(CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy Sciences, Beijing 100190, China)

Understanding intrinsic mechanism of information propagations on social networks has attracted growing attention, including social network topology analysis and user behavior analysis. Due to the heterogeneity of links in social networks, only a portion of links significantly contribute to information propagations. The influence backbone of a social network, consisting of those links, might provide deeper insight to information propagations. Focused on the influence backbone, we analyzes the signs of links with social structural balance theory, and the roles of nodes with heterogeneous distributions of out-degrees, so as to find the roles played by links and nodes in information propagations in a microscopic. Furthermore, we investigate the network connectivity and information spread efficiency of the influence backbone, finding that information propagations are more fragile and less effective.

information propagations; social networks; influence backbone

黃俊銘(1984—)，博士，主要研究領(lǐng)域為信息傳播、社交網(wǎng)絡(luò)分析。E?mail：mail@junminghuang．com沈華偉(1982—)，博士，副研究員、碩士生導(dǎo)師，主要研究領(lǐng)域為網(wǎng)絡(luò)科學(xué)、社會網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘。E?mail：shenhuawei@ict．a(chǎn)c．cn程學(xué)旗(1971—)，研究員、博士生導(dǎo)師，主要研究領(lǐng)域為網(wǎng)絡(luò)科學(xué)、網(wǎng)絡(luò)與信息安全、互聯(lián)網(wǎng)搜索與服務(wù)。E?mail：cxq@ict．a(chǎn)c．cn

1003-0077(2016)02-0074-09

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

國家基礎(chǔ)研究發(fā)展計劃(973)(2012CB316303,2013CB329602);國家自然科學(xué)基金(61232010，61202215);北京市自然科學(xué)基金(4122077)

TP391

A