0 引言

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

1 基于社區度的邊界節點影響力最大化算法

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

1.1 節點社區度

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

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

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

1.2 節點影響概率

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

1.3 CDEA算法框架

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

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

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

    CDEA算法具體步驟如下：

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

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

1.4 CDEA算法復雜度分析

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

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

2 實驗

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

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

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

2.1 影響范圍對比

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

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

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

2.2 運行時間對比

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

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

3 總結

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

參考文獻

[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] 趙之瀅，于海，朱志良，等.基于網絡社團結構的節點傳播影響力分析[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.