PHG: A Three-phase Algorithm for Influence Maximization based on Community Structure

The main purpose of influence maximization is to find a subset of key nodes that could maximize the spread of information under a certain diffusion model. In recent years, many studies have focused on the problem of influence maximization. However, these studies usually ignore the role of community structure which captures a significant effect on the process of influence propagation. To address above problem, we propose a novel hybrid algorithm PHG, which is a three-phase algorithm for influence maximization based on community structure. In our algorithm the influence propagation process is divided into three phases: 1) partition phase; 2) heuristic phase; and 3) greedy phase. Specifically, we first design an efficient algorithm CCSC that finds key nodes in each community to construct a candidate set by detecting community structure. Second, we find the most potential influence nodes from a candidate set by combing the influence weight of nodes and the community influence of nodes through the analysis of the community structure of the impact on nodes. Finally, we greedily select the nodes with maximization marginal gain from remaining a candidate set. The extensive experimental results on artificial and real-world social networks show that our algorithm obtains a better influence spread as well as an acceptable running time.