基于線性閾值模型的影響力傳播權重學習

郭 靜曹亞男周 川張 鵬郭 莉

①(北京郵電大學計算機學院 北京 100876)②(中國科學院信息工程研究所 北京 100093)

1 引言

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

為解決上述問題，本文以線性閾值(Linear Threshold, LT)模型[4,13]為基礎來學習用戶之間的影響力。為此，我們將會面臨下列挑戰。首先，LT模型以權值來度量用戶間影響力，缺少相應的概率描述，所以無法直接使用最大似然估計方法對問題建模。其次，由于用戶間影響力度量與多個鄰居用戶的歷史行為相關，所以每個用戶都需要建立不同目標函數，如何對不同的目標函數有效求解是一個難點。

為此，本文基于 LT模型，利用最大熵原理估計激活閾值的概率密度函數；并以此計算鄰居激活給定用戶的概率，并將用戶的歷史行為日志看作樣本，借鑒最大似然估計的思想對用戶間影響力學習問題建模；最后，設計一種改進的粒子群算法來求解問題。該算法根據問題目標函數和約束的特點，通過問題映射、適應度函數建立、越界阻止、動態參數設置和最優粒子變異等優化策略，有效地學習用戶間影響力。

2 相關預備知識

LT模型是一種能夠刻畫“影響力累計特性”的傳播模型。考慮到現實中用戶可能被其若干朋友共同影響，本文基于LT模型來學習用戶間的影響力。本節先回顧相關預備知識，表1是相關數學符號表示。

表1 對應數學符號表示

在 LT模型中，每個節點存在激活或未激活狀態，且只處于兩者之一。每條邊都被賦予，以表示w對u的影響力，反映u被鄰居激活的可能性。當激活鄰居的所有權重和超過該點閾，如式(1)，則該節點被激活；否則激活失敗。

另外，對每個節點u，所有鄰居對其產生的影響力權重之和不能超過1。

3 基于LT模型的影響力傳播權重學習方法

3.1 基于最大熵的激活概率計算

LT模型以權值來度量用戶之間的影響力，缺少相應的概率描述，無法直接借鑒最大似然估計的思想來對問題進行建模。為此，本文首先根據 LT模型的特點來估計鄰居激活用戶的概率。

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

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

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

為此，首先用拉格朗日乘子法將約束加入目標形成新目標函數式(5)，然后使用求導方法計算問題的最優值。

證畢

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

3.2 問題建模

根據用戶的歷史行為日志，本文借鑒最大似然估計的思想，對用戶影響力學習問題建模。即：將日志信息看作是基于 LT模型產生的樣本，利用用戶影響力取值使樣本觀測的概率最大的思想對問題建模。本文使用三元組{用戶-事件-時間}來表現日志中用戶在事件上的激活狀態，U表示用戶集合，D表示事件集合，T表示時間集合。針對歷史日志中的某事件，用戶u的狀態分兩種情況討論：

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

(2)u未激活：若其所有鄰居都處于未激活狀態，則表示u既沒有受到來自鄰居的影響，也沒有自發地參與；若存在激活的鄰居，則表示鄰居對u的激活失敗，它是鄰居激活用戶失敗的樣本。

根據日志里的用戶信息，本文利用式(10)描述用戶間影響力學習的目標函數。即

3.3 求解算法

本文根據問題目標和約束條件，設計一種改進粒子群算法(Improved Particle Swarm Optimization Algorithm for Influence Weights Learning, IWL-IPSO)來求解問題。其優化策略包括：(1)問題映射，(2)適應度函數建立，(3)越界阻止，(4)動態參數設置，(5)最優粒子變異等。

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

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

圖1 問題的粒子映射

3.3.3適應度函數設計 適應度函數是粒子群算法學習用戶間影響力的關鍵。由于的計算結果與歷史事件的數量| |D 相關，且滿足約束條件和，故當較大時，有，難以評價方案適應度；此外，不滿足約束方案中也可能包含著最優解的影響力取值。為此，本文設計一種新的適應度函數，即采用開| |D 次方的形式來增大適應度的取值，并使用分段處理策略來綜合評價影響力權重，如式(16)。

3.3.4約束違背控制 由于LT模型中的用戶影響力取值范圍在[0,1]，傳統粒子群算法沒有直接方法來限制粒子位置，使得粒子在搜索過程容易飛離搜索區域，產生無效的影響力權重。為了使更多粒子在有效的區域中搜索，本文在位置更新式(15)中加入動力參數設置，具體如式(17)所示。

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

4 實驗

為驗證本方法的合理性，在多次實驗的結果上，以方法執行時間、用戶間影響力的適應度為評價指標來綜合分析IWL-IPSO算法的性能。其中，數據集合來自文獻[17]，對比算法的描述情況：

(1)IWL-PSO(Particle Swarm Optimization algorithm for Influence Weights Learning)：該算法直接利用傳統粒子群算法來學習用戶間的影響力。

(2)IWL-Degree(Degree algorithm for Influence Weights Learning)：該算法直接根據社交網絡中鄰居的數目計算用戶間的影響力。

(3)IWL-PSOA(Particle Swarm Optimization algorithm A for Influence Weights Learning)：該算法在IWL-IPSO的基礎上，通過去除約束違背控制操作來學習用戶間的影響力。

(4)IWL-PSOB(Particle Swarm Optimization algorithm B for Influence Weights Learning)：該算法在IWL-IPSO的基礎上，通過去除動態參數設置操作來學習用戶間的影響力。

(5)IWL-PSOC(Particle Swarm Optimization algorithm C for Influence Weights Learning)：該算法在IWL-IPSO的基礎上，通過去除最優粒子變異策略來學習用戶間的影響力。

4.1 方法有效性驗證

為驗證方法的有效性，本次實驗將從數據集中選擇擁有不同歷史行為記錄的用戶為分析對象，利用IWL-IPSO, IWL-PSO和IWL-Degree來學習鄰居用戶對他們的影響力，并根據算法的執行時間和用戶間影響力的適應度來分析方法在不同歷史行為記錄下的性能。其中，被選目標用戶的詳細信息如表2所示。

圖2和圖3是IWL-IPSO, IWL-PSO和IWLDegree在20次實驗中對用戶間影響力學習所使用的平均時間及獲得的平均適應度。從圖2中可以看出，在鄰居數目相同的情況下，IWL-IPSO的執行時間隨歷史信息數量的增長呈線性增長。從圖3可以看出，IWL-IPSO在不同歷史行為記錄下均取得較好的適應度。

表2 被選用戶的情況

圖2 不同算法執行的平均時間

4.2 方法的性能分析

為進一步分析方法的性能，實驗選擇具有不同鄰居數目、不同歷史行為記錄的用戶為分析對象，通過去除IWL-IPSO的優化步驟來分析它們對學習效果的影響。被選擇的用戶信息如表3所示，實驗結果如表4和表5所示。

從表3和表4可以看出，每個改進步驟都可以提高影響力學習的適應度，且步驟的花費時間較方法整體時間而言相對較少。其中，IWL-PSOA在使用約束違背控制策略后，其學習影響力的適應度較原方法提高了0.34%，這是因為該策略對傳統的更新值進行了縮放，盡可能讓用戶間的影響力滿足約束。IWL-PSOB在使用動態參數設置策略后，其學習影響力的適應度較原方法提高了0.25%，這是因為該策略平衡了算法的局部和全局搜索的能力，粒子在算法的執行初期，更加注重信息的獲取；而在算法的執行后期，更加傾向于對當前最優方案方向進行搜索，從而提高算法的收斂性。IWL-PSOC在使用最優粒子變異策略后，其學習影響力的適應度較原方法提高了4.43%。這是因為在傳統的粒子群算法中，最優粒子的運動具有盲目性，可導致算法收斂于局部最優解，出現早熟現象，而最優粒子變異策略可以有效克服上述問題。

表3 性能分析所選擇用戶的情況

表4 不同算法學習用戶間影響力獲得的平均適應度

圖3 不同算法學習用戶間影響力獲得的平均適應度

表5 不同方法在影響力學習的計算時間(ms)

5 結束語

本文在線性閾值模型的框架下，提出一種影響力傳播權重的計算方法。該方法基于社交網絡中用戶的歷史行為日志信息，利用優化的粒子群算法來學習用戶間的影響力。同時，本文基于真實的社交網絡數據和相關用戶的歷史行為日志，實驗證明了本文方法的有效性。

[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.