基于線(xiàn)性閾值模型的影響力傳播權(quán)重學(xué)習(xí)

郭 靜曹亞男周 川張 鵬郭 莉

①(北京郵電大學(xué)計(jì)算機(jī)學(xué)院 北京 100876)②(中國(guó)科學(xué)院信息工程研究所 北京 100093)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，社交網(wǎng)絡(luò)成為人們交流互動(dòng)的新場(chǎng)所[1]。在社交網(wǎng)絡(luò)中，用戶(hù)通過(guò)影響力的傳播作用影響著網(wǎng)絡(luò)中其他用戶(hù)的情感、觀(guān)點(diǎn)和行為。因此，用戶(hù)間的影響力度量問(wèn)題引起大量研究[212]-。早期的研究往往基于社交網(wǎng)絡(luò)的拓?fù)湫畔ⅲ贸?shù)賦值法、度平均計(jì)算法[25]-、隨機(jī)賦值法[2,6]來(lái)估算用戶(hù)間的影響力。然而，這些方法缺少系統(tǒng)的學(xué)習(xí)與分析，且忽略了用戶(hù)歷史行為的作用。為此，一些研究工作以用戶(hù)的歷史行為為基礎(chǔ)，利用統(tǒng)計(jì)和模型學(xué)習(xí)的方法來(lái)度量用戶(hù)之間的影響力。例如：文獻(xiàn)[7]在用戶(hù)歷史行為記錄的基礎(chǔ)上，利用期望最大化(Expectation-Maximization,EM)算法估算用戶(hù)間的影響力。文獻(xiàn)[8]以 Jaccard系數(shù)和伯努利分布為基礎(chǔ)，提出若干概率模型來(lái)建模用戶(hù)間的影響力學(xué)習(xí)問(wèn)題。文獻(xiàn)[9]從主題模型的角度研究傳播影響力, 并計(jì)算出基于主題有效的獨(dú)立級(jí)聯(lián)模型(Topic-aware Independent Cascade,TIC)的相關(guān)參數(shù)。然而，此類(lèi)方法在建模時(shí)，都假設(shè)用戶(hù)的激活行為是相互獨(dú)立的。在現(xiàn)實(shí)中，用戶(hù)的朋友可能共同影響其做出某一行為，所以上述方法不能全面度量用戶(hù)之間的影響力。

為解決上述問(wèn)題，本文以線(xiàn)性閾值(Linear Threshold, LT)模型[4,13]為基礎(chǔ)來(lái)學(xué)習(xí)用戶(hù)之間的影響力。為此，我們將會(huì)面臨下列挑戰(zhàn)。首先，LT模型以權(quán)值來(lái)度量用戶(hù)間影響力，缺少相應(yīng)的概率描述，所以無(wú)法直接使用最大似然估計(jì)方法對(duì)問(wèn)題建模。其次，由于用戶(hù)間影響力度量與多個(gè)鄰居用戶(hù)的歷史行為相關(guān)，所以每個(gè)用戶(hù)都需要建立不同目標(biāo)函數(shù)，如何對(duì)不同的目標(biāo)函數(shù)有效求解是一個(gè)難點(diǎn)。

為此，本文基于 LT模型，利用最大熵原理估計(jì)激活閾值的概率密度函數(shù)；并以此計(jì)算鄰居激活給定用戶(hù)的概率，并將用戶(hù)的歷史行為日志看作樣本，借鑒最大似然估計(jì)的思想對(duì)用戶(hù)間影響力學(xué)習(xí)問(wèn)題建模；最后，設(shè)計(jì)一種改進(jìn)的粒子群算法來(lái)求解問(wèn)題。該算法根據(jù)問(wèn)題目標(biāo)函數(shù)和約束的特點(diǎn)，通過(guò)問(wèn)題映射、適應(yīng)度函數(shù)建立、越界阻止、動(dòng)態(tài)參數(shù)設(shè)置和最優(yōu)粒子變異等優(yōu)化策略，有效地學(xué)習(xí)用戶(hù)間影響力。

2 相關(guān)預(yù)備知識(shí)

LT模型是一種能夠刻畫(huà)“影響力累計(jì)特性”的傳播模型。考慮到現(xiàn)實(shí)中用戶(hù)可能被其若干朋友共同影響，本文基于LT模型來(lái)學(xué)習(xí)用戶(hù)間的影響力。本節(jié)先回顧相關(guān)預(yù)備知識(shí)，表1是相關(guān)數(shù)學(xué)符號(hào)表示。

表1 對(duì)應(yīng)數(shù)學(xué)符號(hào)表示

在 LT模型中，每個(gè)節(jié)點(diǎn)存在激活或未激活狀態(tài)，且只處于兩者之一。每條邊都被賦予，以表示w對(duì)u的影響力，反映u被鄰居激活的可能性。當(dāng)激活鄰居的所有權(quán)重和超過(guò)該點(diǎn)閾，如式(1)，則該節(jié)點(diǎn)被激活；否則激活失敗。

另外，對(duì)每個(gè)節(jié)點(diǎn)u，所有鄰居對(duì)其產(chǎn)生的影響力權(quán)重之和不能超過(guò)1。

3 基于LT模型的影響力傳播權(quán)重學(xué)習(xí)方法

3.1 基于最大熵的激活概率計(jì)算

LT模型以權(quán)值來(lái)度量用戶(hù)之間的影響力，缺少相應(yīng)的概率描述，無(wú)法直接借鑒最大似然估計(jì)的思想來(lái)對(duì)問(wèn)題進(jìn)行建模。為此，本文首先根據(jù) LT模型的特點(diǎn)來(lái)估計(jì)鄰居激活用戶(hù)的概率。

在 LT模型中，鄰居是否能激活給定用戶(hù)，是由鄰居對(duì)給定用戶(hù)的影響力和激活閾值所共同確定的。因此在影響力確定的條件下，鄰居激活用戶(hù)的概率是由激活閾值uθ所決定的。用戶(hù)是否發(fā)生行為受多種因素影響，所以激活閾值具有很強(qiáng)的不確定性。為刻畫(huà)這種不確定性，本文以最大熵原理來(lái)估計(jì)激活閾值的概率密度，并以此為基礎(chǔ)來(lái)計(jì)算鄰居激活用戶(hù)的概率。

定理1 已知激活閾值uθ的取值范圍在[0,1]之間，且的概率密度函數(shù)滿(mǎn)足等式(4)，則激活閾值的最大熵分布的概率密度函數(shù)滿(mǎn)足。

證明 根據(jù)最大熵原理[14]，在滿(mǎn)足約束的條件下，熵值最大的分布就是符合實(shí)際的分布。由于沒(méi)有先驗(yàn)知識(shí)，僅知道uθ的取值范圍在[0,1]之間，所以求解的概率密度，就是求解下列約束優(yōu)化問(wèn)題。其中，是激活閾值的熵值，C為常數(shù)。

為此，首先用拉格朗日乘子法將約束加入目標(biāo)形成新目標(biāo)函數(shù)式(5)，然后使用求導(dǎo)方法計(jì)算問(wèn)題的最優(yōu)值。

證畢

在定理1的基礎(chǔ)上，本文利用激活閾值uθ的概率密度函數(shù)來(lái)計(jì)算鄰居激活用戶(hù)的概率。假設(shè)鄰居對(duì)用戶(hù)u的影響力為，則鄰居成功激活用戶(hù)的概率可由式(8)計(jì)算獲得，鄰居激活用戶(hù)失敗的概率可由式(9)計(jì)算獲得。

3.2 問(wèn)題建模

根據(jù)用戶(hù)的歷史行為日志，本文借鑒最大似然估計(jì)的思想，對(duì)用戶(hù)影響力學(xué)習(xí)問(wèn)題建模。即：將日志信息看作是基于 LT模型產(chǎn)生的樣本，利用用戶(hù)影響力取值使樣本觀(guān)測(cè)的概率最大的思想對(duì)問(wèn)題建模。本文使用三元組{用戶(hù)-事件-時(shí)間}來(lái)表現(xiàn)日志中用戶(hù)在事件上的激活狀態(tài)，U表示用戶(hù)集合，D表示事件集合，T表示時(shí)間集合。針對(duì)歷史日志中的某事件，用戶(hù)u的狀態(tài)分兩種情況討論：

(1)u激活：若其所有鄰居的激活時(shí)間都晚于u，則表示u自發(fā)參與到iD的傳播中；若存在鄰居的激活時(shí)間都早于u，則表示u受到鄰居影響才參與到的傳播中，它是鄰居成功激活用戶(hù)的樣本。

(2)u未激活：若其所有鄰居都處于未激活狀態(tài)，則表示u既沒(méi)有受到來(lái)自鄰居的影響，也沒(méi)有自發(fā)地參與；若存在激活的鄰居，則表示鄰居對(duì)u的激活失敗，它是鄰居激活用戶(hù)失敗的樣本。

根據(jù)日志里的用戶(hù)信息，本文利用式(10)描述用戶(hù)間影響力學(xué)習(xí)的目標(biāo)函數(shù)。即

3.3 求解算法

本文根據(jù)問(wèn)題目標(biāo)和約束條件，設(shè)計(jì)一種改進(jìn)粒子群算法(Improved Particle Swarm Optimization Algorithm for Influence Weights Learning, IWL-IPSO)來(lái)求解問(wèn)題。其優(yōu)化策略包括：(1)問(wèn)題映射，(2)適應(yīng)度函數(shù)建立，(3)越界阻止，(4)動(dòng)態(tài)參數(shù)設(shè)置，(5)最優(yōu)粒子變異等。

3.3.1粒子群算法回顧 粒子群算法[15]是一種基于群體智能的啟發(fā)式全局搜索算法。它從隨機(jī)解出發(fā)，迭代搜索問(wèn)題的最優(yōu)解。即根據(jù)粒子的最好位置和粒子群中最優(yōu)粒子的位置，使用式(14)和式(15)來(lái)更新位置信息。

3.3.2問(wèn)題的粒子映射 問(wèn)題的合理映射是粒子群算法求解問(wèn)題的前提，由于線(xiàn)性閾值模型中用戶(hù)的狀態(tài)受鄰居的影響，所以本文將鄰居用戶(hù)對(duì)用戶(hù)u的影響力的組合表示成一個(gè)粒子，具體如圖1所示。

圖1 問(wèn)題的粒子映射

3.3.3適應(yīng)度函數(shù)設(shè)計(jì) 適應(yīng)度函數(shù)是粒子群算法學(xué)習(xí)用戶(hù)間影響力的關(guān)鍵。由于的計(jì)算結(jié)果與歷史事件的數(shù)量| |D 相關(guān)，且滿(mǎn)足約束條件和，故當(dāng)較大時(shí)，有，難以評(píng)價(jià)方案適應(yīng)度；此外，不滿(mǎn)足約束方案中也可能包含著最優(yōu)解的影響力取值。為此，本文設(shè)計(jì)一種新的適應(yīng)度函數(shù)，即采用開(kāi)| |D 次方的形式來(lái)增大適應(yīng)度的取值，并使用分段處理策略來(lái)綜合評(píng)價(jià)影響力權(quán)重，如式(16)。

3.3.4約束違背控制 由于LT模型中的用戶(hù)影響力取值范圍在[0,1]，傳統(tǒng)粒子群算法沒(méi)有直接方法來(lái)限制粒子位置，使得粒子在搜索過(guò)程容易飛離搜索區(qū)域，產(chǎn)生無(wú)效的影響力權(quán)重。為了使更多粒子在有效的區(qū)域中搜索，本文在位置更新式(15)中加入動(dòng)力參數(shù)設(shè)置，具體如式(17)所示。

3.3.5動(dòng)態(tài)參數(shù)設(shè)置 在用戶(hù)影響力學(xué)習(xí)的過(guò)程中，算法的全局和局部搜索能力共同決定了學(xué)習(xí)的效果。文獻(xiàn)[16]指出，當(dāng)慣性權(quán)重取值w較小時(shí)，算法將擁有較強(qiáng)的局部搜索能力，有利于粒子收斂。當(dāng)慣性權(quán)重取值w較大，將增強(qiáng)粒子的探索能力，使得算法的全局搜索能力得到提高。為平衡二者的關(guān)系，本文以遞減函數(shù)來(lái)改變w的取值，讓w的取值隨著迭代過(guò)程逐漸遞減，其函數(shù)表達(dá)如式(18)所示。

4 實(shí)驗(yàn)

為驗(yàn)證本方法的合理性，在多次實(shí)驗(yàn)的結(jié)果上，以方法執(zhí)行時(shí)間、用戶(hù)間影響力的適應(yīng)度為評(píng)價(jià)指標(biāo)來(lái)綜合分析IWL-IPSO算法的性能。其中，數(shù)據(jù)集合來(lái)自文獻(xiàn)[17]，對(duì)比算法的描述情況：

(1)IWL-PSO(Particle Swarm Optimization algorithm for Influence Weights Learning)：該算法直接利用傳統(tǒng)粒子群算法來(lái)學(xué)習(xí)用戶(hù)間的影響力。

(2)IWL-Degree(Degree algorithm for Influence Weights Learning)：該算法直接根據(jù)社交網(wǎng)絡(luò)中鄰居的數(shù)目計(jì)算用戶(hù)間的影響力。

(3)IWL-PSOA(Particle Swarm Optimization algorithm A for Influence Weights Learning)：該算法在IWL-IPSO的基礎(chǔ)上，通過(guò)去除約束違背控制操作來(lái)學(xué)習(xí)用戶(hù)間的影響力。

(4)IWL-PSOB(Particle Swarm Optimization algorithm B for Influence Weights Learning)：該算法在IWL-IPSO的基礎(chǔ)上，通過(guò)去除動(dòng)態(tài)參數(shù)設(shè)置操作來(lái)學(xué)習(xí)用戶(hù)間的影響力。

(5)IWL-PSOC(Particle Swarm Optimization algorithm C for Influence Weights Learning)：該算法在IWL-IPSO的基礎(chǔ)上，通過(guò)去除最優(yōu)粒子變異策略來(lái)學(xué)習(xí)用戶(hù)間的影響力。

4.1 方法有效性驗(yàn)證

為驗(yàn)證方法的有效性，本次實(shí)驗(yàn)將從數(shù)據(jù)集中選擇擁有不同歷史行為記錄的用戶(hù)為分析對(duì)象，利用IWL-IPSO, IWL-PSO和IWL-Degree來(lái)學(xué)習(xí)鄰居用戶(hù)對(duì)他們的影響力，并根據(jù)算法的執(zhí)行時(shí)間和用戶(hù)間影響力的適應(yīng)度來(lái)分析方法在不同歷史行為記錄下的性能。其中，被選目標(biāo)用戶(hù)的詳細(xì)信息如表2所示。

圖2和圖3是IWL-IPSO, IWL-PSO和IWLDegree在20次實(shí)驗(yàn)中對(duì)用戶(hù)間影響力學(xué)習(xí)所使用的平均時(shí)間及獲得的平均適應(yīng)度。從圖2中可以看出，在鄰居數(shù)目相同的情況下，IWL-IPSO的執(zhí)行時(shí)間隨歷史信息數(shù)量的增長(zhǎng)呈線(xiàn)性增長(zhǎng)。從圖3可以看出，IWL-IPSO在不同歷史行為記錄下均取得較好的適應(yīng)度。

表2 被選用戶(hù)的情況

圖2 不同算法執(zhí)行的平均時(shí)間

4.2 方法的性能分析

為進(jìn)一步分析方法的性能，實(shí)驗(yàn)選擇具有不同鄰居數(shù)目、不同歷史行為記錄的用戶(hù)為分析對(duì)象，通過(guò)去除IWL-IPSO的優(yōu)化步驟來(lái)分析它們對(duì)學(xué)習(xí)效果的影響。被選擇的用戶(hù)信息如表3所示，實(shí)驗(yàn)結(jié)果如表4和表5所示。

從表3和表4可以看出，每個(gè)改進(jìn)步驟都可以提高影響力學(xué)習(xí)的適應(yīng)度，且步驟的花費(fèi)時(shí)間較方法整體時(shí)間而言相對(duì)較少。其中，IWL-PSOA在使用約束違背控制策略后，其學(xué)習(xí)影響力的適應(yīng)度較原方法提高了0.34%，這是因?yàn)樵摬呗詫?duì)傳統(tǒng)的更新值進(jìn)行了縮放，盡可能讓用戶(hù)間的影響力滿(mǎn)足約束。IWL-PSOB在使用動(dòng)態(tài)參數(shù)設(shè)置策略后，其學(xué)習(xí)影響力的適應(yīng)度較原方法提高了0.25%，這是因?yàn)樵摬呗云胶饬怂惴ǖ木植亢腿炙阉鞯哪芰ΓＷ釉谒惴ǖ膱?zhí)行初期，更加注重信息的獲取；而在算法的執(zhí)行后期，更加傾向于對(duì)當(dāng)前最優(yōu)方案方向進(jìn)行搜索，從而提高算法的收斂性。IWL-PSOC在使用最優(yōu)粒子變異策略后，其學(xué)習(xí)影響力的適應(yīng)度較原方法提高了4.43%。這是因?yàn)樵趥鹘y(tǒng)的粒子群算法中，最優(yōu)粒子的運(yùn)動(dòng)具有盲目性，可導(dǎo)致算法收斂于局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象，而最優(yōu)粒子變異策略可以有效克服上述問(wèn)題。

表3 性能分析所選擇用戶(hù)的情況

表4 不同算法學(xué)習(xí)用戶(hù)間影響力獲得的平均適應(yīng)度

圖3 不同算法學(xué)習(xí)用戶(hù)間影響力獲得的平均適應(yīng)度

表5 不同方法在影響力學(xué)習(xí)的計(jì)算時(shí)間(ms)

5 結(jié)束語(yǔ)

本文在線(xiàn)性閾值模型的框架下，提出一種影響力傳播權(quán)重的計(jì)算方法。該方法基于社交網(wǎng)絡(luò)中用戶(hù)的歷史行為日志信息，利用優(yōu)化的粒子群算法來(lái)學(xué)習(xí)用戶(hù)間的影響力。同時(shí)，本文基于真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)和相關(guān)用戶(hù)的歷史行為日志，實(shí)驗(yàn)證明了本文方法的有效性。

[1] Park B, Lee K, and Kang N. The impact of influential leaders in the formation and development of social networks[C].Proceedings of the 6th International Conference on Communities and Technologies(C＆amp;T), New York, USA,2013: 8-15.

[2] Chen Wei, Wang Chi, and Wang Ya-jun. Scalable influence maximization for prevalent viral marketing in large-scale social networks [C]. Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD), Washington, USA, 2010: 1029-1038.

[3] Chen Wei, Wang Ya-jun, and Yang Si-yu. Efficient influence maximization in social networks[C]. Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Paris, France, 2009: 199-208.

[4] Kempe David, Kleinberg Jon, and Tardos Eva. Maximizing the spread of influence through a social network[C].Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Washington, USA, 2003:137-146.

[5] Zhou Chuan, Zhang Peng, Guo Jing, et al.. UBLF: an upper bound based approach to discover influential nodes in social networks[C]. Proceedings of the IEEE International Conference on Data Mining (ICDM), Dallas, USA, 2013:907-916.

[6] Jung Kyomin, Heo Wooram, and Chen Wei. IRIE: scalable and robust influence maximization in social networks[C].Proceedings of the IEEE International Conference on Data Mining (ICDM), Brussels, Belgium, 2012: 918-923.

[7] Saito Kazumi, Nakano Ryohei, and Kimura Masahiro.Prediction of information diffusion probabilities for independent cascade model[C]. Proceedings of the International Conference on Knowledge-Based and Intelligent Information ＆amp; Engineering Systems (KES), Zagreb, Croatia,2008: 67-75.

[8] Goyal Amit, Bonchi Francesco, and Lakshmanan Laks V S.Learning influence probabilities in social networks[C].Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM), New York, USA, 2010:241-250.

[9] Barbieri Nicola, Bonchi Francesco, and Manco Giuseppe.Topic-aware social influence propagation models[C].Proceedings of the IEEE International Conference on Data Mining (ICDM), Brussels, Belgium, 2012: 81-90.

[10] Liu Lu, Tang Jie, Han Jia-wei, et al.. Learning influence from heterogeneous social networks[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 511-544.

[11] Konstantin Kutzkov, Albert Bifet, Francesco Bonchi, et al..STRIP: stream learning of influence probabilities[C].Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Chicago, USA, 2013:275-283.

[12] Goyal Amit, Bonchi Francesco, and Lakshmanan Laks V S.A data-based approach to social influence maximization[C].Proceedings of the International Conference on Very Large Data Bases (VLDB), Istanbul, Turkey, 2012: 73-84.

[13] Goyal Amit, Lu Wei, and Lakshmanan Laks V S. Simpath:an efficient algorithm for influence maximization under the linear threshold model[C]. Proceedings of the IEEE International Conference on Data Mining (ICDM),Vancouver, Canada, 2011: 211-220.

[14] Jaynes E T. Information theory and statistical mechanics[J].Physical Review, 1957, 106(4): 620-630.

[15] Eberhart Russell and James Kennedy. A new optimizer using particle swarm theory[C]. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995: 39-43.

[16] Shi Yuhui and Eberhart Russell. A modified particle swarm optimizer[C]. Proceedings of IEEE World Congress on Computational Intelligence, Anchorage, USA, 1998: 69-73.

[17] Liu Lu, Tang Jie, Han Jia-wei, et al.. Mining topic-level influence in heterogeneous networks[C]. Proceedings of the Conference on Information and Knowledge Management(CIKM), Toronto, Canada, 2010: 199-208.