0 引言

    近年來,，隨著互聯網和Web技術的不斷革新，影響最大化問題作為社會網絡分析領域的重要問題得到了快速發(fā)展，并已引起越來越多的學者關注,。Li等^[1]研究了基于位置感知的影響力最大化問題,，通過用戶影響力的上界選擇種子節(jié)點并消除不重要的節(jié)點，減少了初始種子節(jié)點的選擇范圍,。Kim等^[2]基于IC模型將獨立影響路徑作為影響評估單元,，但是算法未考慮不同節(jié)點影響力的相關性。Zhao等^[3]提出基于網絡社區(qū)結構的節(jié)點影響力度量策略,，但是算法未考慮節(jié)點度在信息傳播中的重要性,。Jung等^[4]提出了基于IC擴展模型的IRIE算法。Guo等^[5]提出基于個性化的影響力最大化算法,，對給定目標用戶,，尋找對該目標用戶影響力最大的節(jié)點。Cao等^[6]提出動態(tài)規(guī)劃算法(OASNET)解決影響力最大化,但此算法沒有考慮社區(qū)間的連通性,。Tian等^[7]提出結合啟發(fā)算法和貪心算法的影響力最大化算法HPG,，但算法在啟發(fā)階段僅以節(jié)點的度計算潛在影響力，沒有充分考慮節(jié)點的其他屬性,。與上述研究不同,，本文將社區(qū)間的邊界節(jié)點作為初始種子節(jié)點集的候選集，以減少社區(qū)內大量非邊界點的計算時間,，提高運行效率。同時,，傳統(tǒng)以節(jié)點度的倒數衡量節(jié)點間影響力忽略了鄰居節(jié)點對節(jié)點影響的差異,，基于此本文綜合考慮邊界節(jié)點的度、所連社區(qū)數,、所連社區(qū)規(guī)模均值3個因素衡量節(jié)點對鄰居的影響力傳播的重要性,，以更準確衡量節(jié)點影響力。

1 基于社區(qū)度的邊界節(jié)點影響力最大化算法

    本文提出的基于社區(qū)度的邊界節(jié)點影響力最大化算法(CDEA)建立在具有社區(qū)結構的社會網絡基礎上,，利用HPG算法框架實施,。CDEA算法將社區(qū)連接邊的兩端節(jié)點作為邊界節(jié)點，從邊界節(jié)點集中選擇初始傳播種子節(jié)點,，通過LT模型在社會網絡中傳播,，使初始種子節(jié)點產生的影響范圍最大。CDEA算法從邊界節(jié)點集中選擇初始種子節(jié)點是由于在具有社區(qū)結構的社會網絡中,，跨社區(qū)的信息最大化傳播往往更有現實意義,，而邊界節(jié)點是社區(qū)間信息交流的大使，跨社區(qū)的信息傳播必然會經過社區(qū)邊界節(jié)點,，因此可以先不考慮社區(qū)內大量的非邊界節(jié)點,，只考慮少量的邊界節(jié)點，可極大降低算法運行時間。同時CDEA算法用邊界節(jié)點的度和與邊界節(jié)點直接相連的社區(qū)數以及社區(qū)規(guī)模均值綜合衡量節(jié)點的潛在影響力,，提高計算節(jié)點在貪心階段被快速激活的可能性,。

1.1 節(jié)點社區(qū)度

    節(jié)點社區(qū)度是指邊界節(jié)點的度、與邊界節(jié)點直接連接的社區(qū)數,、直接相連的社區(qū)規(guī)模均值三者疊加,。社區(qū)度既考慮節(jié)點度，也結合節(jié)點在社會網絡中的位置和連通性,，可以較好地評估節(jié)點對影響力傳播的重要性,。

    定義1 （社區(qū)度）社區(qū)度主要用于衡量邊界節(jié)點在影響力傳播中的重要性。社區(qū)度是節(jié)點在社區(qū)中鄰居數,、與節(jié)點直接相連的社區(qū)數以及所連社區(qū)規(guī)模均值的疊加和,。節(jié)點在社區(qū)中的鄰居數越多，表明節(jié)點在社區(qū)中越重要,，對其他節(jié)點產生影響的可能更大,。節(jié)點直接相連的社區(qū)數越多，說明節(jié)點與其他社區(qū)產生交流的機會越大,，對信息的廣泛傳播具有重要意義,。而所連社區(qū)規(guī)模的大小將直接影響信息能否通過所連社區(qū)繼續(xù)向下一個社區(qū)擴散，所連社區(qū)規(guī)模越大,，則此社區(qū)在整個社會網絡中對信息的快速傳播作用越大,。因此采用三者的疊加和可以突出節(jié)點在信息傳播中的重要性。社區(qū)度CDeg(u)定義如下：

    社區(qū)規(guī)模均值可縮小,，因為鄰居社區(qū)數少而鄰居社區(qū)節(jié)點數多或鄰居社區(qū)多而鄰居社區(qū)節(jié)點數少所造成的差異能更好地平衡社區(qū)數和每個社區(qū)規(guī)模間的關系,，因此綜合考慮與節(jié)點直接相連的鄰居社區(qū)以及相應社區(qū)規(guī)模均值，可更準確描述社區(qū)度,，提高節(jié)點獲取潛在影響力節(jié)點的精度,。

1.2 節(jié)點影響概率

    本文綜合邊的權重和節(jié)點間的交流頻度計算節(jié)點間的影響概率，更有效地度量節(jié)點間相互影響的概率,。影響概率即為節(jié)點激活鄰居的可能性,，當節(jié)點的所有已激活鄰居對其影響概率和大于等于特定的閾值θ，則節(jié)點被激活,。本文定義節(jié)點u對鄰居節(jié)點v的影響概率為其中t_uv為社會網絡G中節(jié)點u和v信息交流頻度,，w_uv為節(jié)點u到v的邊權重值，Nei(v)表示節(jié)點v的鄰居節(jié)點集,。

1.3 CDEA算法框架

    社區(qū)度描述了邊界節(jié)點在整個網絡中的拓撲結構和重要性,，與傳統(tǒng)單一采用節(jié)點度描述節(jié)點與鄰居的關聯度相比，可更好地衡量節(jié)點潛在影響力,。本文對HPG算法改進,，基于社區(qū)度提出新的混合算法CDEA,。CDEA算法分為啟發(fā)階段和貪心階段。

    基于LT傳播模型的影響累積特性在啟發(fā)階段對邊界節(jié)點啟發(fā)式尋找最有影響力的k′個節(jié)點作為種子節(jié)點,。這些節(jié)點不是局部影響力最大的節(jié)點,，但是其潛在影響力在后續(xù)信息傳播激活過程中將會被充分挖掘，最終獲得比KK算法更大的影響范圍,。令inf(u)為節(jié)點u對所有未被激活鄰居節(jié)點的影響力之和,，則：

    這里CDeg(u)表示節(jié)點u的社區(qū)度，Nei(u)表示節(jié)點u的鄰居節(jié)點集合,，A(u)表示節(jié)點u的鄰居中未被激活的節(jié)點集,。PI綜合考慮了節(jié)點的社區(qū)度和對鄰居中未激活節(jié)點的影響范圍。啟發(fā)階段從未激活的節(jié)點中選擇潛在影響力最大的節(jié)點,，并將其加入初始集合,，直到出現k₁個已經被激活的節(jié)點。貪心階段基于LT信息傳播模型,，應用KK算法不斷計算邊際影響收益,，在局部最優(yōu)的情況下獲取k-k₁個最有影響力的節(jié)點。

    CDEA算法具體步驟如下：

    輸入：社會網絡G=(V,，E,，W)={C₁，C₂,，C₃,，…，C_M},，閾值θ,，啟發(fā)因子c，初始集合大小k,。

    輸出：大小為k的目標節(jié)點集S，最終激活節(jié)點數k₀,，啟發(fā)階段激活節(jié)點數k₁,，貪心階段激活節(jié)點數k₂。

1.4 CDEA算法復雜度分析

    啟發(fā)階段,，由于靜態(tài)社會網絡中式(2)中節(jié)點社區(qū)度是固定的,，并且只需要計算社區(qū)間的邊界節(jié)點的社區(qū)度，而非整個網絡中所有節(jié)點,，且inf(u)是基于前一個初始種子節(jié)點并更新整個網絡后確定,，基本不耗時間，因此時間復雜度為O(C),。同時啟發(fā)階段不但獲取了大量具有潛在影響力的節(jié)點,，而且也激活了大量節(jié)點。貪心階段，由于有大量節(jié)點已被激活,，未激活節(jié)點比初始狀態(tài)下需要激活節(jié)點數減少了大部分,，即可看作KK算法運行在小規(guī)模數據集，因此算法復雜度比KK小,。  

    KK,、HPG以及CDEA算法不同階段的時間復雜度如表1所示。其中Q1,、Q2分別表示啟發(fā)階段CDEA算法和HPG算法每個種子節(jié)點的平均激活節(jié)點數,。T₁、T₂,、T₃分別表示貪心階段CDEA算法,、HPG算法、KK算法每個種子的平均激活范圍,。N,、M、M′分別表示社會網絡G的節(jié)點數,、邊數,、社區(qū)邊界節(jié)點數。M′<<M<<N,，因此可推斷CDEA算法比LPG算法,、KK算法時間復雜度低很多。

2 實驗

    本文實驗中線性閾值模型中的每個節(jié)點閾值?茲取固定值0.5,，啟發(fā)因子c用于平衡不同階段的步數,，其中啟發(fā)階段為當c=1時表明此時為純KK貪心算法。實驗使用的數據集來自公開數據^[8],，社區(qū)密度是每個社區(qū)平均所含節(jié)點數,。數據集統(tǒng)計信息如表2所示。

    第一個數據集是計算機類英文文獻數據中的論文作者合作網絡,，邊代表兩個作者共同發(fā)表過論文,，邊上的權重值表示作者間的合作次數。第二個數據集是視頻分享網站Youtube中的用戶視頻分享網,，邊代表用戶間為彼此分享過視頻,，邊上的權重值代表用戶共享視頻的次數。第三個數據集是Google公司推出的免費在線社交網站Orkut的朋友關系網,，邊代表用戶間是朋友關系,，邊上權重值表示用戶交流次數。

    為了充分說明本文提出的基于社區(qū)度影響力最大化算法,，實驗在3個數據集上,，從不同k值下的影響范圍和算法運行時間兩方面將本文提出的CDEA算法與KK算法,、HPG算法進行對比，驗證算法在大規(guī)模社會網絡下的準確性和高效性,。

2.1 影響范圍對比

    首先考察Youtube數據集中CDEA算法在不同啟發(fā)因子c下影響范圍的變化,，實驗結果如圖1所示。由圖可知,，除c=0外,，其他c值影響范圍基本都比c=1大，且c=0.5時影響范圍最大,。由于c=1時,，CDEA算法只有貪心階段沒有啟發(fā)階段，因此影響范圍比其他c值的影響范圍小,。c=0表明此時CDEA算法只有啟發(fā)階段沒有貪心階段,，所有初始節(jié)點都是靜態(tài)選擇PI最大的節(jié)點，沒有傳播過程參與,，因此影響范圍最小,。實驗結果表明c=0.5時CDEA算法影響范圍最大，因此下面的實驗中設c=0.5,。

    其次考察3個數據集上CDEA算法影響范圍的變化,，實驗結果如圖2所示。由圖可知相同k值下,，Youtube數據集上CDEA算法的影響范圍最大,，Orkut數據集中影響范圍最小，這說明本文提出的算法更適用于社區(qū)密度比較大的社會網絡,。隨著初始種子節(jié)點k逐漸變大,，CDEA算法在3個數據集上影響范圍隨之擴大，且當k在[80,，160]之間時影響范圍的變化速率比較大,，k值超過160后影響范圍變化速率逐漸減小，這是因為隨著k的增大,，新增加的種子節(jié)點能激活的節(jié)點不斷減少,，其影響范圍也在降低。

    最后考察Youtube數據集中KK算法,、HPG算法、CDEA算法在不同k值下影響范圍的變化,，實驗結果如圖3所示,。由圖可知，KK算法的影響范圍呈線性,，HPG和CDEA算法呈曲線上升,，且CDEA算法在k值大于120時比HPG算法影響范圍大,，這是因為CDEA算法綜合考慮了節(jié)點度、社區(qū)度以及社區(qū)規(guī)模均值3個因素,，使影響傳播的范圍在大規(guī)模社會網絡中更廣,。

2.2 運行時間對比

    首先對比3個數據集上CDEA算法尋找k個種子節(jié)點需要的運行時間，實驗結果如圖4所示,。由圖可知,，算法在Youtube數據集上運行時間最小，在Orkut數據集上運行時間最大,，這是由于CDEA算法充分利用了節(jié)點的社區(qū)度屬性,，而Youtube數據集社區(qū)密度大，因此運行時間相對比較小,。當k值不斷變大時,，CDEA算法在不同數據集中運行時間的增長率比較小，因為該算法充分考慮了社會網絡中社區(qū)的邊界節(jié)點,，更適合大規(guī)模社會網絡,。

    最后在Youtube數據集中比較CDEA、HPG,、KK算法的運行時間,。實驗結果如圖5所示。由圖可知,，隨著k值的不斷增長,，KK算法的運行時間不斷變長，而CDEA和HPG算法的運行時間相對比較穩(wěn)定,，呈線性增長,，且當k不斷變大時，CDEA算法的運行時間低于HPG算法,。這是因為CDEA算法充分考慮了社區(qū)邊界節(jié)點,，尤其是在大規(guī)模社會網絡中，極大地減少了尋找初始種子節(jié)點的時間,。

3 總結

    本文提出一種基于社區(qū)度的邊界節(jié)點影響力最大化算法CDEA,，與其他關于影響力最大化問題研究不同的是：CDEA算法利用社會網絡的社區(qū)結構，將社區(qū)中的邊界節(jié)點作為最有影響力節(jié)點的候選集,，在兩層算法模型框架下,，啟發(fā)階段根據網絡社區(qū)從邊界節(jié)點中選擇具有潛在影響力的節(jié)點集，貪心階段在啟發(fā)階段基礎上應用KK算法計算,。實驗表明,，本文提出的算法既有效地降低了時間復雜度，又能較好地應用于大規(guī)模社會網絡,。接下來的工作將對算法作進一步改進,，改善評估節(jié)點影響力的因素,，提高算法的精度。

參考文獻

[1] LI G,，CHEN S,，FENG J，et al.Efficient location-aware influence maximization[C].Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.Snowbird,，Utah,，2014：1621.

[2] KIM J，KIM S K,，YU H.Scalable and parallelizable prcessing of influence maximization for large-scale social networks[C].Proceedings of the 29th IEEE International Conference on Data Engineering.Brisbane,，Australia，2013：266-277.

[3] 趙之瀅,，于海,，朱志良，等.基于網絡社團結構的節(jié)點傳播影響力分析[J].計算機學報,，2014,，37(4)：753-766.

[4] JUNG K，HEO W,，CHEN W.IRIE：Scalable and robust influence maximization in social networks[C].Proceedings of the 12th International Conference on Data Mining.Brussels,，Belgium，2012：918-923.

[5] GUO J,，ZHANG P,，ZHOU C，et al.Personalized influence maximization on social networks[C].Proceedings of the 22nd ACM International Conference on Information & Knowledge Management.San Francisco,，USA,，2013：199-208.

[6] CAO T，WU X,，WANG S,，et al.OASNET：an optimal allocation approach to influence maximization in modular social networks[C].Proceedings of the 2010 ACM Symposium on Applied Computing.ACM，2010：1088-1094.

[7] 田家堂,，王軼彤,，馮小軍.一種新型的社會網絡影響力最大化算法[J].計算機學報，2011,，34(10)：1956-1965.

[8] YANG J,，LESKOVEC J.Defining and evaluating network communities based on ground-truth[C].Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics.ACM，2012：3.