基于用戶復雜聯系的最大影響力節點發現算法

謝世娜，李川

（四川大學計算機學院，成都 610065）

基于用戶復雜聯系的最大影響力節點發現算法

謝世娜，李川

（四川大學計算機學院，成都 610065）

提出基于用戶聯系的信息網絡中最具影響力用戶的發現算法，基于現實社會網絡啟示得到的假定“與越多易受影響用戶有聯系的這類用戶的影響力越大”，且給出無向網絡和有向網絡中節點影響力的度量模型。實驗表明，該方案優于求解影響力最大化的貪心算法達到的影響范圍，能夠較準確地刻畫社會網絡中節點影響力。

影響力；有影響力的節點；貪心算法

0 引言

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

直觀來講，網絡中度越大的節點影響力應該越大，這是許多其他相關研究的基礎假設。其他常用的影響力度量為緊密度中心性（Closeness Centrality），介數中心性（Betweenness Centrality）等[9]。有研究[10]表明：大眾思想的大規模改變也即新事物的傳播，是由容易被影響的用戶去影響其他容易被影響的用戶推動，從而促進信息的廣泛傳播。

1 相關工作

1.1 獨立級聯模型

常用的信息傳播模型為獨立級聯模型[4]。它借鑒交互粒子系統和概率論的理念[1]。在獨立級聯模型中，若節點u在第t步被激活，則它只有一次機會去激活其鄰居節點；而其鄰居節點v被u激活的概率為p，也被稱為信息轉移概率，換句話說，若節點v的鄰居中有l個節點處于活動狀態，則v以1-（1-p）l的概率被激活。如果節點v被成功激活，v將成為t+1步被激活的節點；在以后的激活過程中節點u就失去激活其他節點的機會。若v有多個已激活的鄰居節點，則他們激活v的順序是隨機的。與線性閾值模型類似，獨立級聯模型下的激活過程也是從一個初始激活的節點集合開始直到網絡中沒有節點可以激活為止。具體激活過程如圖1所示。

圖1中灰色表示活動狀態，綠色表示新被激活狀態，紅色表示第t步激活失敗的節點，空白表示不活動狀態。初始活動節點為1、2，第一步成功激活節點3、5，節點4激活失??；第二步，節點3、5有能力激活其他節點，繼續以p概率影響其他鄰居，此時成功激活節點4、6；第三步，以節點4、6為給定活動節點，此時成功激活節點7。節點9激活失敗。

圖1 獨立級聯激活過程

1.2 傳統方案的不足

隨著社交網站的興起，社會網絡等信息網絡已成為學術界的研究熱點，研究者從不同的角度對社會網絡中節點的影響力的進行研究[6～8]。

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

2 基于易受影響的節點影響力度量

本文提出挖掘信息網絡中最具影響力節點的新思想：一個用戶周圍有越多的容易受影響的用戶，則該用戶發布一條消息或者推廣某新事物就越容易被擴散，進而影響網絡中更多的其他用戶。本文認為與越多容易受影響用戶有聯系的這類用戶的影響力越大。同時，本文提出用節點間的相似性來度量節點的易受影響程度。

信息網絡可表示為一無向（有向）圖，其中用戶用節點表示，用戶之間的關系用節點間的邊表示，設G（V，E）為一個無向（有向）圖，V表示節點的集合，E表示節點間連邊的集合。

2.1 無向網絡影響力度量方案

得益于社會網絡分析中經典的“越相似的用戶就越容易相互影響”這一結論[9]，本文提出了基于節點相似性來度量節點容易受影響的程度。具體如下：

定義1易受影響程度。設Sv，u表示節點v與u之間的相似性，Nv表示節點v的鄰居節點集合，則節點v易受影響程度Ev定義為：

定義2節點v受節點u的影響程度。設ev，u為節點v受節點u的影響程度，Ev表示節點v易受影響程度，Sv，u表示節點v與u之間的相似性，則節點v受節點u的影響程度為：

易知：一個用戶與越多的容易受影響的用戶有聯系，則這個用戶的影響力就越大。

定義3節點v的影響力。設eu，v表示節點u受節點v的影響程度，即v的鄰居節點受v的影響程度；Nv表示節點v的鄰居節點集合，則節點v的影響力Iv定義為：

2.2 有向網絡影響力度量方案

本文對無向網絡中度量節點影響力方案進行擴展，考慮了影響傳播的方向性，提出了針對有向網絡中節點影響力的度量方案，具體如下：

定義4有向網絡中節點v與u之間的相似性。設Sv，uOUT表示出度方向的相似性，代表用戶間共同投票的用戶，表示共同感興趣的用戶越多越相似；Sv，uIN表示入度方向的相似性，表示共同投票給他們的用戶越多則這兩個用戶越相似，則有向網絡節點v與u之間的相似性Sv，u定義為：

2.3 算法框架

本文實現了2.1、2.2節提出的節點影響力度量方案，用到的算法偽代碼見算法1。該算法用到了節點間的相似度，1～7行為按網絡是否向有計算網絡中節點v易受影響的程度；第8～12行為計算節點v受節點u的影響程度。13～15行為按網絡關系計算網絡中節點v的影響力。

算法1算法框架

3 實驗分析

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

4 結語

本研究通過考察社會網絡中節點影響力的傳播機制，提出基于節點相似性的度量影響力的新的模型，進一步研究探討無向網絡與有向網絡的度量方法。實驗表明，本文方法優于貪心算法的影響范圍，驗證了新方案的有效性。

圖2 本文方案與CELFgreedy實驗結果對比

[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] 汪小帆，李翔，陳關榮.網絡科學導論[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-），女，四川達州人，研究生，研究方向為信息網絡、圖數據挖掘

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導師，研究方向為數據庫、數據挖掘

2014-12-25

2015-01-14