0 引言

    近年來，隨著互聯(lián)網和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é)點度的倒數(shù)衡量節(jié)點間影響力忽略了鄰居節(jié)點對節(jié)點影響的差異，基于此本文綜合考慮邊界節(jié)點的度、所連社區(qū)數(shù)、所連社區(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ū)的信息最大化傳播往往更有現(xiàn)實意義，而邊界節(jié)點是社區(qū)間信息交流的大使，跨社區(qū)的信息傳播必然會經過社區(qū)邊界節(jié)點，因此可以先不考慮社區(qū)內大量的非邊界節(jié)點，只考慮少量的邊界節(jié)點，可極大降低算法運行時間。同時CDEA算法用邊界節(jié)點的度和與邊界節(jié)點直接相連的社區(qū)數(shù)以及社區(qū)規(guī)模均值綜合衡量節(jié)點的潛在影響力，提高計算節(jié)點在貪心階段被快速激活的可能性。

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

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

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

    社區(qū)規(guī)模均值可縮小，因為鄰居社區(qū)數(shù)少而鄰居社區(qū)節(jié)點數(shù)多或鄰居社區(qū)多而鄰居社區(qū)節(jié)點數(shù)少所造成的差異能更好地平衡社區(qū)數(shù)和每個社區(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é)點與鄰居的關聯(lián)度相比，可更好地衡量節(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é)點，并將其加入初始集合，直到出現(xiàn)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é)點數(shù)k₀，啟發(fā)階段激活節(jié)點數(shù)k₁，貪心階段激活節(jié)點數(shù)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é)點數(shù)減少了大部分，即可看作KK算法運行在小規(guī)模數(shù)據(jù)集，因此算法復雜度比KK小。  

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

2 實驗

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

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

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

2.1 影響范圍對比

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

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

2.2 運行時間對比

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

    最后在Youtube數(shù)據(jù)集中比較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ā)階段根據(jù)網絡社區(qū)從邊界節(jié)點中選擇具有潛在影響力的節(jié)點集，貪心階段在啟發(fā)階段基礎上應用KK算法計算。實驗表明，本文提出的算法既有效地降低了時間復雜度，又能較好地應用于大規(guī)模社會網絡。接下來的工作將對算法作進一步改進，改善評估節(jié)點影響力的因素，提高算法的精度。

參考文獻

[1] LI G，CHEN S，F(xiàn)ENG 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.