社會網絡影響力最大化的核重構算法及傳播模型

劉鈺峰 郅歡歡 周喻鑫(湖南大學信息科學與工程學院 湖南 長沙 410082)

0 引 言

近年來，大規模社會網絡(如facebook、新浪微博、人人網等)迅速發展，這為“口碑”與“病毒營銷”提供了機遇，隨之也產生了一個關鍵的問題，即如何從大規模的社會網絡中挖掘一些節點，并使這些節點在網絡中傳播影響最大化[1-4]。

在社會網絡中，判斷初始節點的影響力需要借助相應的傳播模型。獨立級聯傳播模型IC(Independent Cascade Model)和線性閾值傳播模型LT(Linear Threshold Model)是最基本的傳播模型，除此之外，在社會網絡傳播過程中通用的信息傳播模型還有SI、SIR、SIS[5-7]等。Gopalan等[8]提出SI信息傳播模型在社交網絡中運用廣泛，且效果比較好。Zhang等[9]經過對社會網絡結構分析，根據節點的度將節點進行分類，提出了改進的SI信息傳播模型。Xu等[10]接著提出了SIS的信息傳播模型。Hacid等[11]基于SIR信息傳播模型和SIS信息傳播模型進行影響力的傳播預測。本文針對SI信息傳播模型未考慮節點間親密關系對信息傳播的影響，提出了一種ESI信息傳播模型。

社會網絡節點影響力最大化問題的研究由來已久，Richardson等[12]最先將社會網絡節點影響力最大化作為一個算法問題提出，選取特定初始節點使影響力最大化。之后，相關研究者[13-23]先后提出了不同的算法來解決社會網絡節點影響最大化問題。Kempe等提出了貪心爬山算法[16]，影響結果達到最優解的63%。但該算法運算量大且時間復雜度較高，不適用于大型網絡。Goyal[17]等對貪心算法改進后提出了一種影響最大化算法Celf++。Chen等[18]提出了一種啟發式算法DegreeDiscount，當一個節點被選為初始節點后，那么計算這個節點的鄰居節點的度時就打一定的折扣。Kitsak[19]等提出了一種基于覆蓋的最大核算法和最大度算法。Zhou等[20]基于節點的位置特征提出了一種效率較高的影響最大化算法。Estevez等[21]提出了SCG(Slow Crack Growth)算法，選取度大的初始節點，考慮到度大的初始節點會存在重復鄰居節點，所以選取的初始節點需要盡可能的分散。曹玖新等[22]提出了基于k核的影響最大化算法CCA(Core Cover-ing Algorithm)，用一個距離因子d控制初始節點的距離。Zhou[23]基于SI信息傳播模型，利用社團劃分來選擇影響最大化的節點(本文稱之為MSI算法)。對于影響最大化問題，許多研究者提出了時間復雜度相對較低的啟發式算法，但其節點影響力效果卻不如貪心算法。針對該問題，本文提出了一種影響效率高且時間復雜度較低的啟發式算法CRA。

1 信息傳播模型

1.1 SI信息傳播模型

SI信息傳播模型是最重要的社會網絡信息傳播模型之一，該模型認為每個節點只有兩種狀態：影響狀態是S(i)與未影響狀態I(i)，且節點只能從未影響狀態向影響狀態單向轉變。SI傳播模型基本思想如下：首先得到節點t-1時的影響狀態，根據鄰居節點的影響狀態與已影響的鄰居節點的影響概率α，得到所有鄰居節點對該節點的影響概率，最后得到t時該節點的影響狀態。

1.2 ESI信息傳播模型

在SI信息傳播模型中，節點與已影響鄰居節點間的影響程度用一個常數α來進行計算，但在真實社會網絡節點影響傳播過程中，節點間的關系不同，被影響的程度也不同。通常兩個節點之間越親密，就會更加關注對方的消息，節點間的影響概率就會越大。比如兩個相鄰節點表示的用戶關系比較親密，那么其中一個用戶發的消息就可能很快影響另一個用戶，而對于相鄰的是個幾乎沒有聯系的用戶，那么就不一定會被影響，所以在信息傳播的過程中，要考慮節點間的這種影響因素?；诖?，本文提出了ESI信息傳播模型。

1.2.1 節點影響過程

本文引入節點間親密度的概念表示節點間互動的親密程度，用Ai,j表示節點i和節點j的親密度，則節點間親密度計算如下：

(1)

式中：Si表示該節點i的消息集合，Sj表示節點i的鄰居節點j的消息集合，Zi表示節點i的鄰居節點集合，用ei,j表示鄰居節點j對節點i的影響概率，則其計算如下：

ei,j=cα+(1-c)Ai,ji∈Vj∈Zi

(2)

式中:假設α是節點起初可能被已影響節點影響的概率，屬于[0,1]。c表示一個調和因子，屬于[0,1]。

以下考慮節點被影響的過程，本文使用Pi,t表示節點t時刻被影響的概率。Pi,t主要與三個因素有關：1) 該節點的鄰居節點t-1時刻到t時刻對其影響的概率；2) 該節點t-1時刻的影響概率；3) 該節點的鄰居節點的影響狀態。

本文使用χi,t來表示節點i在t-1時刻到t時刻未被已影響的鄰居節點j影響的概率：

χi,t=((1-ei,j)pj,t-1)i∈Vj∈Zi

(3)

鄰居節點j在t-1時刻未影響的概率為(1-pj,t-1)。

δi,t用來表示節點i在t-1時刻到t時刻未被鄰居節點j影響的概率為：

δi,t=χi,t+(1-pj,t-1)=((1-ei,j)pj,t-1)

i∈Vj∈Zi

(4)

節點i存在的鄰居節點j有多個，所以用βi,t來表示所有鄰居節點j∈Zi從t-1時刻到t時刻未能影響節點i的概率為：

i∈V

(5)

相反，用φi,t來表示節點i在t-1時刻到t時刻被它的鄰居節點影響的概率為：

i∈V

(6)

節點i在t-1時刻未被影響的概率為(1-pi,t-1)，節點i從t-1時刻到t時刻未被影響的概率為(1-φi,t)，所以節點t時刻被影響的概率為：

pi,t=1-(1-pi,t-1)(1-φi,t)i∈V

(7)

由式(6)代入式(7)可得：

pi,t= 1-(1-pi,t-1)(1-(1-

(8)

…i∈V

(9)

式(9)后面的值非常小，可忽略不計，得到：

(10)

由式(8)和式(10)得到：

(11)

(12)

(13)

式(13)表示了一個節點從t-1到t影響概率變化的過程，也反映了節點的影響狀態的變化。

1.2.2 模型框架

用向量Pt=[p1,t,p2,t,…,pn,t]表示所有節點i∈V在t時刻的影響概率，pi,t=1表示節點i在t時刻已被影響，pi,t=0表示節點i在t時刻未被影響。用矩陣E表示節點與鄰居節點影響的概率矩陣，表示如下：

(14)

由傳播過程得：

(15)

在t足夠大時，節點的概率可能大于1，所以運用控制概率函數如下：

G([x1,x2,…,xn])= [min{x1,1},min{x2,1},…,

min{xn,1}]

(16)

將式(14)代入式(15)得到：

(17)

式(17)主要表示了ESI信息傳播模型中所有節點隨時間被影響的變化過程，在t=0時，初始節點的影響概率為1，通過任意時間t，可得到整個網絡節點的影響狀態。

社會網絡影響最大化問題除了借助相應傳播模型外，最重要的是初始節點的挖掘。

2 基于k階核心集的影響最大化算法

2.1 k階核心集

不同于曹玖新等[22]提出的k核，本文提出k階核心集的概念。對網絡中的每一個節點，其k階核心集的定義是與之k級關聯的節點集合，而k核是度值不少于k的節點推出的最大連通子圖。以下是具體定義：

定義1k階。在圖G=(V,S)社交網絡拓撲結構中，節點i(i∈V)會存在直接相連的節點，本文將其直接相連的節點稱為第一階節點，將它的間接節點稱為第二階節點，以此類推可以得到k階的節點。

如圖1所示一個網絡節點無向圖，節點1的一階節點是4、8、21，二階節點是2、5、7、12、13、14、16，三階節點是9、11、15、18。當k=2時，可以得到S2(1)={4,8,21,2,5,7,12,13,14,16}。

圖1 網絡節點關系示意圖

定義3重合率定義為節點i與鄰居節點j的k階共同節點集合與兩節點k階核心集占比，使用P(i,j)表示如下:

(18)

重合率的范圍控制初始節點的影響狀況，P太高，易局部影響最大化；P太低，初始節點k階核心集邊緣節點的連通性不好，不易被影響。所以本文提出了合適的重合率計算方法如下：

P(i,j)∈(α,β)α,β∈(0,1)

(19)

(20)

(21)

本文討論的CRA算法主要根據節點k階核心集初步選取，再通過重合率確定。當k為1，通過重合率范圍得到的新的初始節點一般處于上一個初始節點一階節點附近，這樣得到的初始節點集沒有足夠的擴散，進而可能造成局部影響最大化，所以一般k從2開始選取。

2.2 CRA算法

CRA算法的基本思想簡述如下：1) 根據k階核心集，選擇核心集數量大且一階核心集不小于平均每階核心集的節點；2) 將選擇滿足條件的節點進行標記，并將其一階核心集進行標記，表示不能再被選擇；3) 重合率范圍判斷，將新選節點與所有已選初始節點進行重合率計算。重合率的控制給各初始節點的k階核心集邊緣節點提供了多次被影響的機會。

算法1基于核重構的社會網絡影響最大化算法

輸入：社會網絡節點G=(V,S)，節點個數N,初始節點個數m

輸出：初始節點集合M

1. InitializeM=?

3.x1∈MAnd mark(x1,C(x1))

5. Ifx2∈(Cv(x1∪C(x1)))

6. CalculateP(x1,x2),Calculateα,Calculateβ

7. IfP(x1,x2)∈(α,β)

8.x2∈MAnd mark(x2,C(x2))

9. Else

10. markx2And Return step 4

11. End If

12. End If

該算法中的get(MaxSk(xi))表示選擇出k階核心集數量最大的節點，mark(x1,C(x1))表示選擇滿足條件的節點進行標記，并將其一階核心集進行標記。Cv(x1∪C(x1))表示節點V中未標記節點。

2.3 時間復雜度分析

CRA算法節點核心集比較過程是對每一個節點的k階核心集進行對比，故時間復雜度為O(n)；節點標記的過程是只對選擇的初始節點的一階的核心集進行標記，故時間復雜度小于O(n)；重合率計算與范圍比較過程是只對選擇的初始節點進行比較，所以CRA算法的時間復雜度是O(n)。

3 實驗設計

3.1 數據集

本文通過新浪微博開放的API接口[24]，利用網絡數據挖掘器挖掘出部分用戶和對應的粉絲，以及用戶轉發的微博。通過爬蟲程序預處理總共得到11 080個節點，1 288 045條邊，以及節點在2014年8月1日到12月31日對應轉發的微博消息806 854條。

3.2 實驗對比

為了驗證CRA算法，與其他算法進行實驗對比。

對比實驗算法如表1所示。

表1 對比算法

3.3 結果分析

本文的實驗結果評價指標可概括為以下兩點：(1) 影響范圍。通過相同的時間，節點最終被影響的數量。(2) 算法的運行時間。如何用較短的時間找到初始節點。在傳播影響節點圖中，x軸表示信息傳播模型中的時間步t，y軸表示節點的影響數量。

本文將初始節點m分別為5和10進行實驗。在SI信息傳播模型和ESI信息傳播模型上，α分別為0.01、0.02和0.03。實驗結果如圖2、圖3所示。

(a) m=5 α=0.01

(b) m=5 α=0.02

(c) m=5 α=0.03

(d) m=10 α=0.01

(e) m=10 α=0.02

(f) m=10 α=0.03圖2 SI信息傳播模型上各算法的影響效果

(a) m=5 α=0.01

(b) m=5 α=0.02

(c) m=5 α=0.03

(d) m=10 α=0.01

(e) m=10 α=0.02

(f) m=10 α=0.03圖3 ESI信息傳播模型上各算法的影響效果

從圖2和圖3的對比可以看出，算法在ESI信息傳播模型上節點影響效果要優于SI信息傳播模型，其中CRA、CCA、Degree算法比較明顯，這表明節點間的親密關系對節點的傳播也起很重要的作用。而且本文提出的CRA算法比其他四種算法的最終的影響效果明顯更好。在影響數量上，相同的初始節點m和影響概率α情況下，CRA的最終影響節點數量都是最多的。在影響速度上，CRA算法影響節點速度也是最快的。如圖2(b-f)和圖3(b-f)所示，CRA(3)比CCA(2)算法的性能更好，這充分證明考慮節點的k級節點關聯特性比節點的層次性更重要。如圖2(e-f)和圖3(e-f)所示，DC算法的影響效果優于MSI算法，同時Degree算法影響效果變的趨于平緩。這表明節點的影響最大化過程一定要考慮初始節點的距離因素。在本文實驗中，CRA(2)、CRA(3)比CRA(4)算法的影響效果更優。這主要是因為CRA(4)算法考慮的是四階鄰居節點特征，在節點的傳播過程中，離初始節點遠的節點不易被影響。一旦存在未影響的節點，那么這些未影響節點的鄰居節點更不易影響。雖然重合率保證存在一些重復的邊緣節點，使它們可以多次被影響，但是并不能保證這些重復節點一定被影響。所以并非階數k越大，CRA算法性能越好。階數k需要根據總節點數適宜選取。

4 結 語

本文針對社交網絡節點影響最大化問題，根據節點的k階核心集與重合率，提出了CRA算法。針對SI信息傳播模型未考慮鄰居節點間的親密度的問題，對其進行改進得出ESI傳播模型。分別在SI信息傳播模型和ESI信息傳播模型進行實驗，與其他幾種算法進行比較，得到如下結論：1) 所有算法在ESI信息傳播模型下，節點影響效果更好。2) 在不同的傳播概率下，CRA算法的影響效果都是最好的，傳播過程中影響節點的速度也是最快的。在接下來的研究中，一方面是通過機器學習的方法來更加準確地預測節點間的影響概率。另一方面是推算數據集節點總數與k階核心集特性對k值的影響，并推導使節點影響最大化的k值。

[1] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2009:199- 208.

[2] Zhang H, Dinh T N, Thai M T. Maximizing the Spread of Positive Influence in Online Social Networks[C]// IEEE, International Conference on Distributed Computing Systems. IEEE, 2013:317- 326.

[3] Jiang B, Hegde N, Massoulie L, et al. How to Optimally allocate your budget of attention in social networks[C]// INFOCOM,2013 Proceedings IEEE.IEEE,2013:2373- 2381.

[4] Borgs C, Brautbar M, Chayes J, et al. Maximizing social influence in nearly optimal time[C]// Acm-Siam Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics, 2014:946- 957.

[5] Wei Z, Ye Y, Tan H, et al. Information Diffusion Model Based on Social Network[C]// Proceedings of the 2012 International Conference of Modern Computer Science and Applications. Springer Berlin Heidelberg, 2013:145- 150．

[6] Xu B,Liu L.Information diffusion through online social networks[C]// IEEE International Conference on Emergency Management and Management Sciences.IEEE,2010:53- 56.

[7] Lu Z, Wen Y, Cao G. Information diffusion in mobile social networks: The speed perspective[C]// INFOCOM, 2014 Proceedings IEEE. IEEE, 2014:1932- 1940.

[8] Gopalan A, Banerjee S, Das A K, et al. Random mobility and the spread of infection[C]// INFOCOM, 2011 Proceedings IEEE. IEEE, 2011:999- 1007.

[9] Zhang H, Dinh T N, Thai M T. Maximizing the Spread of Positive Influence in Online Social Networks [C]//IEEE, International Conference on Distributed Computing Systems.IEEE,2013:317- 326.

[10] Xu B,Liu L.Information diffusion through online social networks[C]// IEEE International Conference on Emergency Management and Management Sciences.IEEE,2010:53- 56.

[11] Hacid H,Hacid H.A predictive model for the temporal dynamics of information diffusion in online social networks[C]// International Conference on World Wide Web.ACM,2012:1145- 1152.

[12] Richardson M,Domingos P. Mining knowledge-sharing sites for viral marketing[C]//Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2002:61- 70.

[13] Zhang Wei,Ye Yanqing,Tan Hanlin, et al. Information Diffusion Model Based on Social Network[C]// Proceedings of the 2012 International Conference of Modern Computer Science and Applications. Springer Berlin Heidelberg, 2013: 145- 150．

[14] Tang Y, Xiao X, Shi Y. Influence maximization: near-optimal time complexity meets practical efficiency[C]// SIGMOD’14 Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.2014: 75- 86.

[15] Kimura M, Saito K. Approximate Solutions for the Influence Maximization Problem in a Social Network[C]// Knowledge-Based Intelligent Information and Engineering Systems, International Conference, Kes 2006, Bournemouth, Uk, October 9- 11, 2006, Proceedings. DBLP, 2006:937- 944.

[16] Kempe D, Kleinberg J. Maximizing the spread of influence through a social network[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137- 146.

[17] Goyal A, Lu W, Lakshmanan L V S. CELF++: optimizing the greedy algorithm for influence maximization in social networks[C]// International Conference Companion on World Wide Web. ACM, 2011:47- 48.

[18] Chen W,Lu W,Zhang N.Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process[J]. Chinese Journal of Engineering Design, 2012, 19(5):340- 344.

[19] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2011, 6(11):888- 893.

[20] Zhou T, Cao J, Liu B, et al. Location Based Influence Maximization in Social Networks[C]// ACM International on Conference on Information and Knowledge Management. ACM, 2015:1211- 1220.

[21] Estevez P A, Vera P, Saito K. Selecting the Most Influential Nodes in Social Networks[C]// International Joint Conference on Neural Networks. IEEE, 2007:2397- 2402.

[22] 曹玖新, 董丹, 徐順,等. 一種基于k-核的社會網絡影響最大化算法[J]. 計算機學報, 2015, 38(2):238- 248.

[23] Zhao J.Initial spreaders in online social networks[C]// Communication,Control,and Computing.IEEE,2017:180- 186.

[24] http://open.weibo.com/.