大型社群網路中影響力最大化的效率演算法

Abstract

在病毒式行銷網路中一個常見的問題是影響力最大化問題。此問 題為如何在有限資源下從人群中找出具有影響力的人，使其能影響整 個網路中最多的人。這個問題已被證明是NP-Hard 的問題。貪婪演算 法不僅能保證有(1 − 1/e) 最佳近似解，而且貪婪演算法在其他啟發性 演算法中表現為最好的。但是，貪婪演算法在大型網路中的計算複雜 度非常高。因此，目前許多研究都注重在表現和計算時間的取捨。跟 其他多數的研究不同的是，我們想知道我們是否有辦法擊敗(或是改 善) 貪婪演算法的表現但又不需要額外增加太多的計算量。藉由把影 響力最大化問題對照到k-medians 問題，我們推導出影響力最佳化問 題可以轉換為k-medians 中找出最佳的k 個medoid 問題。基於此，我 們提出KMIC 演算法利用k-medians 的方式解決在independent cascade model 上的影響力最大化問題。我們的實驗顯示(1) 利用貪婪演算法的 結果當作KMIC 演算法的初始點，是有機會改善貪婪演算法的表現(2) 在一個比較緊密連結的網路中適當選取KMIC 演算法的初始點，亦可 以改善貪婪演算法的表現(3)KMIC 演算法適用在大型網路中。

One of the essential problems for viral marketing is the influence maximization problem that finds a small set of seed people to maximize their influence in the whole social network. Such a problem is known to be NP-hard and it is also known that the greedy algorithm not only achieves (1 − 1/e)-approximation for the influence maximization problem but also yields larger influence than the other heuristic algorithms in the literature. By mapping the influence maximization problem to a k-medians problem, we show that the difference between the optimal influence and the influence deduced from the optimal k medoids of the corresponding k-medians problem can be bounded by a constant. Based on this, we propose the KMIC algorithm for the influence maximization problem in the Independent Cascade model. Our experiments show that (i) it is possible to improve the performance of the greedy algorithm by using the output of the greedy algorithm as the initial setting of the KMIC algorithm, (ii) it is also possible to beat the performance of the greedy algorithm for a densely connected network by choosing an appropriate initial setting of the KMIC algorithm, and (iii) the KMIC algorithm is applicable for large networks.