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

吳 旭，胡一清

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

?

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

吳 旭，胡一清

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

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

影響力最大化；友好關(guān)系；社交網(wǎng)絡(luò)；社會計算

社會網(wǎng)絡(luò)中的影響力最大化算法[1, 2]可以幫助發(fā)現(xiàn)現(xiàn)實生活中不易發(fā)現(xiàn)的社會現(xiàn)象或者社會問題。其目的是尋找若干個種子節(jié)點使影響力擴散最大化，得到影響力最大化的最優(yōu)解決方案。

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

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

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

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

1.1 FIMM算法框架

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

圖1 FIMM算法的實現(xiàn)框架

1.2 友好關(guān)系網(wǎng)絡(luò)的建立

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

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

(1)

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

，

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

(3)

(4)

其中ΔTa,b表示用戶雙方首次相互回應(yīng)的時間點和最新交互回應(yīng)的時間點的差值。ΔTuniverse為友好關(guān)系網(wǎng)絡(luò)中所有節(jié)點間首次相互回應(yīng)的時間點和最新交互回應(yīng)的時間點的差值。最后將ΔTa,b進行平滑處理得到時間因子tΔ。

通過Pearson相 關(guān) 系 數(shù)(Pearson Correlation Coefficient)[12]調(diào)整得到相似度的計算公式為

(5)

(6)

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

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

(7)

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

1.3 FIMM算法

(8)

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

步驟1 調(diào)整激活概率。

在友好關(guān)系網(wǎng)絡(luò)的基礎(chǔ)上，通過式(8)調(diào)整激活概率p。

步驟2 啟發(fā)式地選取種子節(jié)點。

利用式(7)計算節(jié)點在友好關(guān)系網(wǎng)絡(luò)上的友好度積累值，友好度積累值較高的節(jié)點被選取作為啟發(fā)節(jié)點。選取[hk]個節(jié)點作為啟發(fā)節(jié)點。重復(fù)執(zhí)行[hk]輪，每輪選取未激活的友好度累積值較高的節(jié)點作為啟發(fā)節(jié)點(種子節(jié)點)，然后在保留上一輪擴散的節(jié)點的基礎(chǔ)上用啟發(fā)節(jié)點經(jīng)行擴散。

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

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

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

2 實驗結(jié)果及分析

2.1 實驗數(shù)據(jù)集

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

(1) 用戶信息。包括用戶名ID、用戶名、關(guān)注用戶數(shù)和被關(guān)注用戶數(shù)。

(2) 用戶關(guān)注關(guān)系。包括當(dāng)前用戶ID、當(dāng)用戶關(guān)注用戶的ID和被當(dāng)前用戶關(guān)注的用戶ID。

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

最后通過用戶關(guān)注關(guān)系中相互關(guān)注的行為形成邊。數(shù)據(jù)集描述如表1所示。

表1 數(shù)據(jù)集描述

2.2 實驗對比

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

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

由圖2可知，排除h=1的情況，h取其它值所得到的影響范圍均比h=1時要大。當(dāng)k=50，h=0.5，F(xiàn)IMM算法所得的影響范圍比h的其他取值要高出3%。當(dāng)h=1時,FIMM算法變?yōu)殪o態(tài)選取潛在影響力最大的節(jié)點，將其作為種子節(jié)點，這種選取方式未考慮影響力的傳播過程，因此所得的影響范圍也最差。而當(dāng)h=0時，F(xiàn)IMM算法退化為CELF++算法。

圖2 參數(shù)k與h在數(shù)據(jù)集1中的影響范圍曲線

數(shù)據(jù)集2的實驗結(jié)果如圖3。當(dāng)h≠0且取合適的值時，所得的影響范圍優(yōu)于h=0情況。這說明在友好關(guān)系網(wǎng)絡(luò)的環(huán)境下啟發(fā)式的選取一部分種子節(jié)點優(yōu)于直接使用CELF++算法。同時，當(dāng)h=0.5時，所取得的影響范圍仍高于h取其他值的情況。

圖3 參數(shù)k與h在數(shù)據(jù)集2中的影響范圍曲線

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

圖4 不同算法在數(shù)據(jù)集1中的影響范圍曲線

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

圖5 不同算法在數(shù)據(jù)集1中所消耗的時間

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

3 結(jié)語

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

[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] 吳旭. 基于增強穩(wěn)定組模型的移動P2P網(wǎng)絡(luò)信任評估方[J/OL]．計算機學(xué)報, 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.

[責(zé)任編輯：祝劍]

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

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

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

TP393.093

A

2095-6533(2016)06-0118-05