大型社群網路中影響力最大化的巨型組件演算法

Abstract

在大型社群網路的病毒式行銷中，影響力最大化是個常見的問題。 目前有許多的演算法可以解決影響力最大化問題，它們的目標是選一 組點，而這組點會讓整個社群的影響力最大化，這問題已經被證明 是個NP-Hard 的問題，貪婪演算法是最經典的演算法，它可以保證有 (1-1/e) 最佳近似解，然而，包括貪婪演算法在內，大部分的演算法 的進步都很微小，而且時間複雜度也相對高，另一方面，在大型隨機 網路中，存在著一個巨型組件，我們想嘗試把巨型組件的理論應用在 影響力最大化問題中。在這篇論文裡，我們瞄準於如何在影響力最大 化問題中，用比較低的時間複雜度達到巨型組件的大小，基於配置模 型理論，我們首先會證明在真實世界中的社群網路中存在著巨型組 件，另外，我們提出一些MD 系列的演算法來達成我們的目標，與其 它演算法不同，MD 系列演算法只考慮分支度和聯合分支度，相比於 其他演算法，我們可以展現MD 系列演算法表現得不錯，而且有相對 低的時間複雜度。

Influence maximization problem is a common problem for viral marketing in large social networks. There are several algorithms to solve influence maximization problem. The goal is to select a set of nodes that can maximize the influence in the network. It is proved that influence maximization problem is an NP-hard problem. The most classic one is the greedy algorithm, which achieves (1-1/e) approximation. However, most of the algorithms, including the greedy algorithm, improve slightly and the time complexity is relatively high. On the other hand, there exists a giant component in large random networks. We are curious about that if we can apply the giant component theorem to influence maximization problem. In this paper, we aim to state algorithms that can reach the giant component size in influence maximization problem with low time complexity. We will first show that there exists a giant component in a real-world social network based on the theorems on configuration model. Furthermore, we suggest new algorithms, MDs, which can reach our goal. Differing from other algorithms, MDs only consider degree correlation. Comparing with other algorithms, we can show that MDs perform well and have relatively low complexity.