謝世娜，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

基于用戶復(fù)雜聯(lián)系的最大影響力節(jié)點(diǎn)發(fā)現(xiàn)算法

謝世娜，李川

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

提出基于用戶聯(lián)系的信息網(wǎng)絡(luò)中最具影響力用戶的發(fā)現(xiàn)算法，基于現(xiàn)實(shí)社會(huì)網(wǎng)絡(luò)啟示得到的假定“與越多易受影響用戶有聯(lián)系的這類用戶的影響力越大”，且給出無(wú)向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的度量模型。實(shí)驗(yàn)表明，該方案優(yōu)于求解影響力最大化的貪心算法達(dá)到的影響范圍，能夠較準(zhǔn)確地刻畫(huà)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力。

影響力；有影響力的節(jié)點(diǎn)；貪心算法

0 引言

社會(huì)網(wǎng)絡(luò)（Social Network）通常指實(shí)體與實(shí)體間聯(lián)系構(gòu)成的復(fù)雜信息網(wǎng)絡(luò)（Information Network），即由節(jié)點(diǎn)和邊組成的，反映一定社會(huì)結(jié)構(gòu)關(guān)系的網(wǎng)絡(luò)或圖。其中，節(jié)點(diǎn)可表示個(gè)人或組織等實(shí)體，節(jié)點(diǎn)之間的鏈接或邊表示實(shí)體之間的聯(lián)系，例如合作關(guān)系、朋友關(guān)系、認(rèn)同關(guān)系等。當(dāng)我們考察信息傳播時(shí)，發(fā)現(xiàn)：社會(huì)網(wǎng)絡(luò)的結(jié)構(gòu)擔(dān)當(dāng)著非常重要的作用。當(dāng)一用戶接受某新事物之后，會(huì)向其鄰居、好友推薦該事物，其中一部分人就會(huì)受其影響接受該新事物，且進(jìn)一步向他們的鄰居、朋友推薦。在這樣一個(gè)傳播過(guò)程中，一個(gè)人的社會(huì)關(guān)系及其朋友的行為會(huì)影響到他的決策[1]。社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的研究由來(lái)已久[2～7]。近年來(lái)，隨著各大社交網(wǎng)站的興起，如Facebook、Twitter等，使得該研究再次成為熱點(diǎn)。而這些社交網(wǎng)站的龐大用戶數(shù)量以及用戶間的復(fù)雜聯(lián)系等特點(diǎn)也給相關(guān)研究帶來(lái)巨大的挑戰(zhàn)。一個(gè)基礎(chǔ)的問(wèn)題是：如何在這些龐大的用戶網(wǎng)絡(luò)中找到最具影響力的小部分用戶使得信息通過(guò)他們能夠傳播或擴(kuò)散的范圍更廣[2～4]？通過(guò)對(duì)影響力分析還可以發(fā)現(xiàn)意見(jiàn)領(lǐng)袖，改進(jìn)個(gè)性化推薦等[5～8]。

直觀來(lái)講，網(wǎng)絡(luò)中度越大的節(jié)點(diǎn)影響力應(yīng)該越大，這是許多其他相關(guān)研究的基礎(chǔ)假設(shè)。其他常用的影響力度量為緊密度中心性（Closeness Centrality），介數(shù)中心性（Betweenness Centrality）等[9]。有研究[10]表明：大眾思想的大規(guī)模改變也即新事物的傳播，是由容易被影響的用戶去影響其他容易被影響的用戶推動(dòng)，從而促進(jìn)信息的廣泛傳播。

1 相關(guān)工作

1.1 獨(dú)立級(jí)聯(lián)模型

常用的信息傳播模型為獨(dú)立級(jí)聯(lián)模型[4]。它借鑒交互粒子系統(tǒng)和概率論的理念[1]。在獨(dú)立級(jí)聯(lián)模型中，若節(jié)點(diǎn)u在第t步被激活，則它只有一次機(jī)會(huì)去激活其鄰居節(jié)點(diǎn)；而其鄰居節(jié)點(diǎn)v被u激活的概率為p，也被稱為信息轉(zhuǎn)移概率，換句話說(shuō)，若節(jié)點(diǎn)v的鄰居中有l(wèi)個(gè)節(jié)點(diǎn)處于活動(dòng)狀態(tài)，則v以1-（1-p）l的概率被激活。如果節(jié)點(diǎn)v被成功激活，v將成為t+1步被激活的節(jié)點(diǎn)；在以后的激活過(guò)程中節(jié)點(diǎn)u就失去激活其他節(jié)點(diǎn)的機(jī)會(huì)。若v有多個(gè)已激活的鄰居節(jié)點(diǎn)，則他們激活v的順序是隨機(jī)的。與線性閾值模型類似，獨(dú)立級(jí)聯(lián)模型下的激活過(guò)程也是從一個(gè)初始激活的節(jié)點(diǎn)集合開(kāi)始直到網(wǎng)絡(luò)中沒(méi)有節(jié)點(diǎn)可以激活為止。具體激活過(guò)程如圖1所示。

圖1中灰色表示活動(dòng)狀態(tài)，綠色表示新被激活狀態(tài)，紅色表示第t步激活失敗的節(jié)點(diǎn)，空白表示不活動(dòng)狀態(tài)。初始活動(dòng)節(jié)點(diǎn)為1、2，第一步成功激活節(jié)點(diǎn)3、5，節(jié)點(diǎn)4激活失?。坏诙?，節(jié)點(diǎn)3、5有能力激活其他節(jié)點(diǎn)，繼續(xù)以p概率影響其他鄰居，此時(shí)成功激活節(jié)點(diǎn)4、6；第三步，以節(jié)點(diǎn)4、6為給定活動(dòng)節(jié)點(diǎn)，此時(shí)成功激活節(jié)點(diǎn)7。節(jié)點(diǎn)9激活失敗。

圖1 獨(dú)立級(jí)聯(lián)激活過(guò)程

1.2 傳統(tǒng)方案的不足

隨著社交網(wǎng)站的興起，社會(huì)網(wǎng)絡(luò)等信息網(wǎng)絡(luò)已成為學(xué)術(shù)界的研究熱點(diǎn)，研究者從不同的角度對(duì)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力的進(jìn)行研究[6～8]。

傳統(tǒng)的研究節(jié)點(diǎn)影響力的度量方式有度中心性、介數(shù)中心性、接近中心性等，但這些指標(biāo)并不適用于所有場(chǎng)合[9]。度雖易計(jì)算但并不能很好地刻畫(huà)節(jié)點(diǎn)的影響力，而介數(shù)、接近性等在大規(guī)模網(wǎng)絡(luò)中則很難計(jì)算。Chen等人[11]提出考慮兩階鄰居的局部中心性指標(biāo)來(lái)描述節(jié)點(diǎn)的傳播影響力。近年來(lái)，也有對(duì)Kempe等人[4]提出的貪心算法的改進(jìn)算法，雖然提高了貪心算法的計(jì)算效率，但因其計(jì)算復(fù)雜度過(guò)高很難適用于大規(guī)模社會(huì)網(wǎng)絡(luò)中。Leskovec等[12]利用集函數(shù)子模塊性提出CELF算法。子模塊性是指，在向初始節(jié)點(diǎn)集合S中添加一個(gè)節(jié)點(diǎn)v時(shí)，若該集合S越大，則v對(duì)影響范圍的增量就越小，即滿足收益遞減原則。CELF算法去掉了大量重復(fù)計(jì)算，提高了貪心算法的計(jì)算速度，但并沒(méi)有擴(kuò)大貪心算法的影響范圍。本文在實(shí)驗(yàn)部分用到的貪心算法即CELF算法。但是這些算法也很難達(dá)到理想的效果，即使是貪心算法也只是找到最有影響力的節(jié)點(diǎn)集合，并未給出刻畫(huà)節(jié)點(diǎn)影響力的度量。

2 基于易受影響的節(jié)點(diǎn)影響力度量

本文提出挖掘信息網(wǎng)絡(luò)中最具影響力節(jié)點(diǎn)的新思想：一個(gè)用戶周圍有越多的容易受影響的用戶，則該用戶發(fā)布一條消息或者推廣某新事物就越容易被擴(kuò)散，進(jìn)而影響網(wǎng)絡(luò)中更多的其他用戶。本文認(rèn)為與越多容易受影響用戶有聯(lián)系的這類用戶的影響力越大。同時(shí)，本文提出用節(jié)點(diǎn)間的相似性來(lái)度量節(jié)點(diǎn)的易受影響程度。

信息網(wǎng)絡(luò)可表示為一無(wú)向（有向）圖，其中用戶用節(jié)點(diǎn)表示，用戶之間的關(guān)系用節(jié)點(diǎn)間的邊表示，設(shè)G（V，E）為一個(gè)無(wú)向（有向）圖，V表示節(jié)點(diǎn)的集合，E表示節(jié)點(diǎn)間連邊的集合。

2.1 無(wú)向網(wǎng)絡(luò)影響力度量方案

得益于社會(huì)網(wǎng)絡(luò)分析中經(jīng)典的“越相似的用戶就越容易相互影響”這一結(jié)論[9]，本文提出了基于節(jié)點(diǎn)相似性來(lái)度量節(jié)點(diǎn)容易受影響的程度。具體如下：

定義1易受影響程度。設(shè)Sv，u表示節(jié)點(diǎn)v與u之間的相似性，Nv表示節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合，則節(jié)點(diǎn)v易受影響程度Ev定義為：

定義2節(jié)點(diǎn)v受節(jié)點(diǎn)u的影響程度。設(shè)ev，u為節(jié)點(diǎn)v受節(jié)點(diǎn)u的影響程度，Ev表示節(jié)點(diǎn)v易受影響程度，Sv，u表示節(jié)點(diǎn)v與u之間的相似性，則節(jié)點(diǎn)v受節(jié)點(diǎn)u的影響程度為：

易知：一個(gè)用戶與越多的容易受影響的用戶有聯(lián)系，則這個(gè)用戶的影響力就越大。

定義3節(jié)點(diǎn)v的影響力。設(shè)eu，v表示節(jié)點(diǎn)u受節(jié)點(diǎn)v的影響程度，即v的鄰居節(jié)點(diǎn)受v的影響程度；Nv表示節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合，則節(jié)點(diǎn)v的影響力Iv定義為：

2.2 有向網(wǎng)絡(luò)影響力度量方案

本文對(duì)無(wú)向網(wǎng)絡(luò)中度量節(jié)點(diǎn)影響力方案進(jìn)行擴(kuò)展，考慮了影響傳播的方向性，提出了針對(duì)有向網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的度量方案，具體如下：

定義4有向網(wǎng)絡(luò)中節(jié)點(diǎn)v與u之間的相似性。設(shè)Sv，uOUT表示出度方向的相似性，代表用戶間共同投票的用戶，表示共同感興趣的用戶越多越相似；Sv，uIN表示入度方向的相似性，表示共同投票給他們的用戶越多則這兩個(gè)用戶越相似，則有向網(wǎng)絡(luò)節(jié)點(diǎn)v與u之間的相似性Sv，u定義為：

2.3 算法框架

本文實(shí)現(xiàn)了2.1、2.2節(jié)提出的節(jié)點(diǎn)影響力度量方案，用到的算法偽代碼見(jiàn)算法1。該算法用到了節(jié)點(diǎn)間的相似度，1～7行為按網(wǎng)絡(luò)是否向有計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)v易受影響的程度；第8～12行為計(jì)算節(jié)點(diǎn)v受節(jié)點(diǎn)u的影響程度。13～15行為按網(wǎng)絡(luò)關(guān)系計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)v的影響力。

算法1算法框架

3 實(shí)驗(yàn)分析

本文實(shí)驗(yàn)使用常用于社會(huì)網(wǎng)絡(luò)研究領(lǐng)域中各項(xiàng)試驗(yàn)分析的真實(shí)數(shù)據(jù)集（Ca-HepTh），代表的社會(huì)語(yǔ)義為合作關(guān)系。本文使用獨(dú)立級(jí)聯(lián)模型來(lái)驗(yàn)證本文方案提出的節(jié)點(diǎn)影響力度量方法的有效性，并與貪心的算法比較其在網(wǎng)絡(luò)中的影響范圍。本文選取的為p=0.01，每次模擬傳播過(guò)程100次。在計(jì)算節(jié)點(diǎn)影響力的時(shí)候，本文選取了6種節(jié)點(diǎn)局部相似性[13]，計(jì)算了其相應(yīng)的節(jié)點(diǎn)影響力，分別是Sorenson指標(biāo)、Salton指標(biāo)、CN、Jaccard指標(biāo)、HPI、HDI。實(shí)驗(yàn)結(jié)果如圖2所示。橫坐標(biāo)均表示初始活動(dòng)節(jié)點(diǎn)的規(guī)模，縱坐標(biāo)均表示影響范圍，即初始活動(dòng)節(jié)點(diǎn)集對(duì)應(yīng)的平均激活節(jié)點(diǎn)數(shù)。從圖中可以看到，（a）和（b）為在數(shù)據(jù)集Ca-HepTh上的實(shí)驗(yàn)結(jié)果。從中可以看到本文方案優(yōu)于貪心算法的影響范圍，且可以給出節(jié)點(diǎn)影響力的具體大小，這是貪心算法不能實(shí)現(xiàn)的。由此，說(shuō)明本文提出影響力度量方案是可行且有效的，能較準(zhǔn)確刻畫(huà)社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力。因本文方案是基于網(wǎng)絡(luò)自身結(jié)構(gòu)，不需加入更多的額外信息，因此也具有普適性。

4 結(jié)語(yǔ)

本研究通過(guò)考察社會(huì)網(wǎng)絡(luò)中節(jié)點(diǎn)影響力的傳播機(jī)制，提出基于節(jié)點(diǎn)相似性的度量影響力的新的模型，進(jìn)一步研究探討無(wú)向網(wǎng)絡(luò)與有向網(wǎng)絡(luò)的度量方法。實(shí)驗(yàn)表明，本文方法優(yōu)于貪心算法的影響范圍，驗(yàn)證了新方案的有效性。

圖2 本文方案與CELFgreedy實(shí)驗(yàn)結(jié)果對(duì)比

[1] Tang L,Liu H.Community Detection and Mining in Social Media[J].Synthesis Lectures on Data Mining and Knowledge Discovery, 2010,2（1）:1～137

[2] Serrat O.Social Network Analysis[J]，2009

[3] Chen W,Wang C,Wang Y.Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks[C].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:1029～1038

[4] Kempe D,Kleinberg J,Tardos.Maximizing the Spread of Influence Through a Social Network[C].Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137～146

[5] Song X,Chi Y,Hino K,et al.Identifying Opinion Leaders in the Blogosphere[C].Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management.ACM,2007:971～974

[6] Centola D.The Spread of Behavior in an Online Social Network Experiment[J].Science,2010,329（5996）:1194～1197

[7] Kimura M,Saito K,Nakano R.Extracting Influential Nodes for Information Diffusion on a Social Network[C].AAAI.2007,7:1371～ 1376.

[8] Guille A.Information Diffusion in Online Social Networks[C].Proceedings of the 2013 Sigmod/PODS PhD.Symposium on PhD Symposium.ACM,2013:31～36

[9] 汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京：高等教育出版社，2012

[10] Watts D J,Dodds P S.Influentials,Networks,and Public Opinion Formation[J].Journal of Consumer Research,2007,34（4）:441～ 458

[11] Chen D,Lü L,Shang M S,et al.Identifying Influential Nodes in Complex Networks[J].Physica A:Statistical Mechanics and Its Applications,2012,391（4）:1777～1787

[12] Leskovec J,Krause A,Guestrin C,et al.Cost-Effective Outbreak Detection in Networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2007:420～429

[13] Lin-yuan L.Link Prediction on Complex Networks[J].Journal of University of Electronic Science and Technology of China,2010,9: 5～39

The Most Influential Nodes Finding Algorithm Based on User Complex Relationships

XIE Shi-na，LI Chuan
（School of Computer Science,Sichuan University,Chengdu 610065）

Proposes a most influential node finding algorithm based on complex user relationship,which is based on such hypothesis that the nodes with more easily affected neighborhood users have more chances to be affected.Gives the measurement method of undirected and directed network.Experiments show that the method exceeds the greedy algorithm of influence maximization on the spread influence and is more likely to depict the influence in social network accurately.

Influence;Influential Node;Greedy Algorithm

1007-1423（2015）03-0006-04

10.3969/j.issn.1007-1423.2015.03.002

謝世娜（1990-），女，四川達(dá)州人，研究生，研究方向?yàn)樾畔⒕W(wǎng)絡(luò)、圖數(shù)據(jù)挖掘

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)閿?shù)據(jù)庫(kù)、數(shù)據(jù)挖掘

2014-12-25

2015-01-14