基于友好度的影響力最大化算法

吳 旭，胡一清

(西安郵電大學 計算機學院, 陜西 西安 710121)

?

基于友好度的影響力最大化算法

吳 旭，胡一清

(西安郵電大學 計算機學院, 陜西 西安 710121)

提出一種基于友好度的影響力最大化算法。利用社交網絡中用戶行為信息計算友好度并構建友好關系網絡，通過友好度調整節點的擴散概率，同時啟發式地選取友好度積累值較高的節點作為啟發節點以此提升算法的實現效率，最后采用CELF++算法計算影響力最大的節點集。實驗結果表明，該算法與CELF++算法、TIM算法和DegreeDiscount算法相比，在獲得較好的擴散效果的同時亦將執行時間有效的控制在一定范圍內。

影響力最大化；友好關系；社交網絡；社會計算

社會網絡中的影響力最大化算法[1, 2]可以幫助發現現實生活中不易發現的社會現象或者社會問題。其目的是尋找若干個種子節點使影響力擴散最大化，得到影響力最大化的最優解決方案。

利用自然貪心算法計算影響力最大化的效果雖然明顯好于基于節點度或中心性的啟發式的影響力最大化算法，但其計算效率不高，特別是面對擁有海量用戶節點和邊社交網站，低效問題更加明顯[3]。CELF(Cost-Effective Lazy Forward selection)算法[4]在自然貪心算法的基礎上，利用影響力最大化的子模塊特性提升了貪心算法的效率；CELF++算法[5]是對CELF算法的改進，利用堆特性進一步提升了算法效率。 NewGreedy算法[6]和CELF算法[4]融合得到的MixedGreedy算法，計算效率也有所提高，但是計算得出的種子節點個數與最佳的影響力最大化的節點集仍有差距； DegreeDiscount算法[6]利用節點度啟發式選取種子節點，并沒有考慮到網絡中用戶間的關系信息，通過犧牲擴散范圍來降低時間復雜度；與DegreeDiscount 算法相似，TIM(Two-phase Influence Maximization)算法[7]雖然效率較高，但是也沒有對個體間的相互關系進行分析和量化，導致擴散效果受到限制。

目前,影響最大化問題中的影響力擴散模型主要有線性閾值模型(Linear Threshold Model，LTM)和獨立級聯模型(Independent Cascade Model，ICM)[3]。擴散模型中個體之間的影響力權值默認是已知的常量或者提前賦予的數值，但是在現實環境中這種假設不成立，因此有必要對個體間的影響力因素及其相互關系進行分析和量化。

在信息擴散過程中，用戶之間的友好關系是主要影響因素之一[8-11]。針對用戶之間行為和交互信息較少所導致的度量結果與實際情況有偏差的問題,本文擬提出基于友好度的影響力最大化算法(Friendliness-based Influence Maximization Method, FIMM)，并基于獨立級聯模型構建FIMM算法框架。利用用戶間友好度調整擴散概率，可使友好度較高的用戶之間的傳播概率更大。同時將啟發式的選取友好度積累值較高的節點作為最有潛力的影響力節點以期提升算法的實現效率。

1 基于友好度的影響力最大化算法

1.1 FIMM算法框架

FIMM算法的實現框架，如圖1所示，包括兩個階段：(1)友好關系網絡建立階段。通過計算用戶間的友好度得到用戶間的友好關系網絡。(2)FIMM算法的具體實現階段。通過友好度調整節點的激活概率，同時啟發式的選取友好度積累值較高的節點作為最有潛力的影響力節點。

圖1 FIMM算法的實現框架

1.2 友好關系網絡的建立

采集用戶間的歷史交互行為信息。通過分析這些行為的分布規律和因果關系得到社交網絡中用戶間的熟悉度與相似度。根據用戶間的熟悉度與相似度計算用戶間友好度,并利用友好度建立用戶間友好關系網絡。友好度計算公式為

T(a,b)=F(a,b)S(a,b),

(1)

其中T(a,b)為a與b之間的友好度，S(a,b)為a與b的相似度，F(a,b)為a與b間的熟悉度。熟悉度計算表達式為

，

其中Wa,b表示a與b相互回應的消息次數，N(a)表示a的鄰居節點集合，Wa,m表示a與所有鄰居m的相互回應的消息次數。用戶間的交往時間對熟悉度的計算有影響，將式(1)通過時間因子tΔ進行修正，得到

(3)

(4)

其中ΔTa,b表示用戶雙方首次相互回應的時間點和最新交互回應的時間點的差值。ΔTuniverse為友好關系網絡中所有節點間首次相互回應的時間點和最新交互回應的時間點的差值。最后將ΔTa,b進行平滑處理得到時間因子tΔ。

通過Pearson相 關 系 數(Pearson Correlation Coefficient)[12]調整得到相似度的計算公式為

(5)

(6)

其中，Ia和Ib分別表示a和b打過分的項目的數量。

計算用戶對其鄰居友好度的積累得到累加的友好度積累值C(a)，該值被用來度量用戶的潛在影響力，其表達式為

(7)

其中Ar表示第r輪影響力擴散的種子節點集。友好度積累值C(a) 較高的節點將作為最有潛力的影響力節點。

1.3 FIMM算法

(8)

FIMM算法將分為3步選取k個種子節點，并引入啟發因子h(0≤h≤1)，啟發因子h意味著啟發階段選取啟發節點個數所占比率。FIMM算法的具體實現步驟如下。

步驟1 調整激活概率。

在友好關系網絡的基礎上，通過式(8)調整激活概率p。

步驟2 啟發式地選取種子節點。

利用式(7)計算節點在友好關系網絡上的友好度積累值，友好度積累值較高的節點被選取作為啟發節點。選取[hk]個節點作為啟發節點。重復執行[hk]輪，每輪選取未激活的友好度累積值較高的節點作為啟發節點(種子節點)，然后在保留上一輪擴散的節點的基礎上用啟發節點經行擴散。

步驟3 利用貪心算法選取種子節點。

利用CELF++算法計算剩余的k-[hk]個種子節點。重復執行k-[hk]輪，直到得到具有k個種子節點的集合S。輸出集合S。

當h=0時，算法跳過步驟2直接步驟3。其中啟發因子h為經驗值，因此需要確定h的值才能得到一個確定的影響最大化方法。

2 實驗結果及分析

2.1 實驗數據集

為驗證FIMM算法在社交網絡中的有效性，選取兩組用戶數據集作為仿真驗證對象。從社交網絡抽取用戶節點及節點信息形成社交網絡圖，其中用戶節點包括用戶對電影、音樂、書籍的評分。評分項直接反應了用戶的興趣。通過這些節點數據信息得到節點間的熟悉度與相似度以構建友好關系網絡。節點數據為：

(1) 用戶信息。包括用戶名ID、用戶名、關注用戶數和被關注用戶數。

(2) 用戶關注關系。包括當前用戶ID、當用戶關注用戶的ID和被當前用戶關注的用戶ID。

(3) 評分信息。當前用戶對電影、書籍及音樂專輯的評分。

最后通過用戶關注關系中相互關注的行為形成邊。數據集描述如表1所示。

表1 數據集描述

2.2 實驗對比

選取種子集合個數k作為輸入參數，影響范圍和算法執行時間作為種子集合S在擴散模型之上的仿真效果的評價指標。其中影響范圍表示算法利用種子節點S擴散一定的輪數所影響的節點個數。將CELF++算法、TIM算法和DegreeDiscount算法3種影響力最大化算法與FIMM算法進行比較，共進行兩組實驗。

實驗1 選取種子集合個數k作為參數，用以考察在k值一定的情況下取不同啟發因子h所得到的影響范圍。數據集1的實驗結果如圖2所示。

由圖2可知，排除h=1的情況，h取其它值所得到的影響范圍均比h=1時要大。當k=50，h=0.5，FIMM算法所得的影響范圍比h的其他取值要高出3%。當h=1時,FIMM算法變為靜態選取潛在影響力最大的節點，將其作為種子節點，這種選取方式未考慮影響力的傳播過程，因此所得的影響范圍也最差。而當h=0時，FIMM算法退化為CELF++算法。

圖2 參數k與h在數據集1中的影響范圍曲線

數據集2的實驗結果如圖3。當h≠0且取合適的值時，所得的影響范圍優于h=0情況。這說明在友好關系網絡的環境下啟發式的選取一部分種子節點優于直接使用CELF++算法。同時，當h=0.5時，所取得的影響范圍仍高于h取其他值的情況。

圖3 參數k與h在數據集2中的影響范圍曲線

實驗2 將CELF++算法、TIM算法、DegreeDiscount算法與FIMM算法分別在影響范圍和算法執行時間上進行比較。其中FIMM算法的啟發因子取h=0.5。實驗結果分別如圖4和圖5所示。

圖4 不同算法在數據集1中的影響范圍曲線

從圖4可以看出，在k=50時，由FIMM算法得到種子節點的擴散范圍(即所影響的種子節點數)比CEFL++算法得到的擴散范圍高出7%。這說明FIMM算法框架通過友好關系網絡有效地模擬了社交網絡中影響力傳播過程進而使挖掘出的最具影響力的種子節點集合的擴散效果得到提升。由于FIMM算法通過計算節點的友好度累積值，啟發式的選取種子節點，因此當種子節點個數k的取值較小時會影響FIMM的擴散效果。從實驗結果上看，k>25時，FIMM算法的擴散范圍開始優于其他影響力最大化算法。

圖5 不同算法在數據集1中所消耗的時間

從圖5中可以看出，CELF++算法的執行時間高于其他算法，這是由于該算法在整個社交網絡中利用蒙特卡洛模擬估算節點影響力。而 FIMM算法在構建友好關系網絡后利用節點友好度的積累選取啟發節點將有效減少算法執行時間，并且最終的擴散范圍優于CELF++算法。 FIMM算法與其他算法相比在獲得較好的擴散效果的同時亦將執行時間有效的控制在一定范圍內。實驗結果驗證了友好度的引入和啟發式的選取種子節點較好地優化了影響力最大化算法。

3 結語

FIMM算法利用獨立級聯模型模擬擴散過程，采集用戶間的歷史交互行為信息計算用戶間的友好度，以此建立用戶間的友好關系網絡；啟發式的選取友好度積累值較高的節點作為最有潛力的影響力節點，以減少尋找種子節點所消耗的時間。與CELF++算法、TIM算法和DegreeDiscount算法對比實驗結果表明， FIMM算法在獲得較好的擴散效果的同時亦將執行時間有效的控制在一定范圍內，這表明友好度的引入和啟發式的選取種子節點較好地優化了影響力最大化算法。

[1] DOMINGOS P, RICHARDSON M. Mining the Network Value of Customers[C/OL]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York, NY, USA:ACM,2001:57-66[2016-5-20]. http://dx.doi.org/10.1145/502512.502525.

[2] RICHARDSON M, DOMINGOS P. Mining Knowledge-sharing Sites for Viral Marketing[C/OL]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York, NY, USA:ACM,2002:61-70[2016-5-20]. http://dx.doi.org/10.1145/775056.775057.

[3] KEMPEL D, KLEINBERG J, TARDOS. Maximizing the Spread of Influence Through a Social Network[C/OL]//Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, USA: ACM, 2003: 137-146[2016-5-20].http://dx.doi.org/10.1145/956750.956769.

[4] LESKOVEC J, KRAUSE A, GUESTRIN C. Cost-effective Outbreak Detection in Networks[C/OL]//Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York, NY, USA: ACM, 2007: 420-429[2016-5-20].http://dx.doi.org/10.1145/1281192.1281239.

[5] GOYAL A, LU WEI, LAKSHMANAN L V S. CELF++: Optimizing the Greedy Algorithm for Influence Maximization in Social Networks[C/OL]//Proceedings of the international conference companion on World Wide Web. New York, NY, USA: ACM, 2011: 47-48[2016-5-20].http://dx.doi.org/10.1145/1963192.1963217.

[6] CHEN W, WANG Y, YANG S. Efficient Influence Maximization in Social Networks[C/OL]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, USA: ACM, 2009: 199-208[2016-5-20].http://dx.doi.org/10.1145/1557019.1557047.

[7] TANG Y Z, XIAO X K SHI Y C. Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency[C/OL]// Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, New York, NY, USA: ACM, 2014: 75-86[2016-5-20].http://dx.doi.org/10.1145/2588555.2593670.

[8] VACCARO A, ADARMS S K, KISLER T S, et al. The Use of Social Media for Navigating the Transitions Into and Through the First Year of College[J/OL]. Journal of the First-Year Experience & Students in Transition, 2015,27(2):29-48[2016-5-20]. http://eric.ed.gov/?q=social+AND+media+AND+school&pg=4&id=EJ1102760.

[9] LUO H, MA L. Empirical research on consumers' post-transaction general trust in B2C E-business[C/OL]// 2013 10th International Conference on Service Systems and Service Management, Hong Kong: ICSSSM, 2013:208-213[2016-5-20]. http://dx.doi.org/10.1109/ICSSSM.2013.6602639.

[10] 吳旭. 基于增強穩定組模型的移動P2P網絡信任評估方[J/OL]．計算機學報, 2014, 37(10) : 2118 - 2127[2016-5-20]. http://dx.chinadoi.cn/10.3724/SP.J.1016.2014.02118.

[11] ZHANG H, WANG Y, YANG J. Space Reduction for Contextual Transaction Trust Computation in E-Commerce and E-Service Environments[C/OL]// 2015 IEEE International Conference on Services Computing (SCC) , 2015: 680-687[2016-5-20].http://dx.doi.org/10.1109/SCC.2015.97.

[12] AHLGREN P, JAMEVING B, ROUSSEAU R. Requirements for a cocitation similarity measure, with special reference to Pearson’s correlation coefficient[J/OL]. Journal of the American Society for Information Science and Technology, 2003: 54(6):550-560[2016-5-20].http://dx.doi.org/10.1002/asi.10242.

[責任編輯：祝劍]

Influence maximization algorithm based on friendliness

WU Xu, HU Yiqing

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications Xi’an 710121, China)

A new influence maximization algorithm based on friendliness is proposed in this paper and named as Friendliness-based Influence Maximization Method (FIMM). FIMM uses behavior and interaction information of nodes in social network to compute friendliness and to build friendly relationship network. FIMM also adjusts the diffusion probability of nodes through the friendliness and improves the efficiency of implementation of the algorithm by selecting nodes. These nodes have higher accumulation of friendliness and have the most potential influence heuristically based on friendly relationship network. Experiment results show that FIMM can get better diffusion effect than CELF++, TIM and DegreeDiscount. FIMM can also limit implement time effectively in a smaller range, which means that using friendliness and selecting nodes heuristically can optimize influence maximization algorithm.

influence maximization, friendliness, social network, social computing

10.13682/j.issn.2095-6533.2016.06.023

2016-6-16

國家自然科學基金資助項目(71501156)；中國博士后基金資助項目(2014M560796)；陜西省教育廳科研計劃資助項目(15JK1679)；西安郵電大學創新基金資助項目(114-602080048)

吳旭 (1978- )，女，副教授，博士，從事可信計算、信任管理和云計算等研究。E-mail: xrdz2005@163.com. 胡一清 (1990- )，男，碩士研究生，研究方向為計算機網絡輿情。E-mail: 172142282@qq.com.

TP393.093

A

2095-6533(2016)06-0118-05