Evaluating the Effectiveness of Community Detection Algorithms for Influence Maximization in Social Networks

摘要

Influence maximization, a classic optimization problem in social networks, targets to find a set of influential users capable of producing maximum influence spread under a particular diffusion model. Community structure, an important topological property of social networks, also plays a significant role in various dynamical processes, including the spreading of information in networks. Realizing the impact of community structure in information spreading, some community-based influence maximization methods have been proposed recently, and these studies show that community-based influence maximization methods perform better than the traditional influence maximization. However, the impact of the method used to detect communities on influence spread in the influence maximization problem is unknown, the need to verify and find the most effective community detection method suitable for influence maximization is essential. This paper addresses this problem by computing the influence spread of k influential nodes selected by an influential node selection method from the k largest communities extracted by the various community detection algorithms on a network. Experiments have been conducted to evaluate the performance of community detection algorithms and their impact on influence maximization on both artificial and real-world networks by employing four heuristic influence maximization methods under IC diffusion model.