ComIM: A community-based algorithm for influence maximization under the weighted cascade model on social networks

Abstract

Influence maximization (IM) is a problem of selecting $k$ nodes from social networks to make the expected number of the active node maximum. Recently, with the popularity of Internet technology, more and more researchers have paid attention to this problem. However, the existing influence maximization algorithms with high accuracy are usually difficult to be applied to the large-scale social network. To solve this problem the paper proposes a new algorithm, called community-based influence maximization (ComIM). Its core idea is “divide and conquer”. In detail, this algorithm first utilizes the Louvain algorithm to divide the large-scale networks into some small-scale networks. Afterwards, the algorithm utilizes the one-hop diffusion value (ODV) and two-hop diffusion value (TDV) functions to calculate the influence of a node and select nodes on these small-scale networks, which can improve the accuracy of our proposed algorithm. By using the above methods, the paper proposes a community influence-estimating method called CDV, which can improve the efficiency of the algorithm. Experimental results on six real-world datasets demonstrate that our proposed algorithm outperforms all comparison algorithms when comprehensively considering the accuracy and efficiency.