A Heuristic Algorithm Focusing on the Rich-Club Phenomenon for the Influence Maximization Problem in Social Networks

Abstract

The strength of information diffusion on social networks depends on many factors, including the selected influential nodes. The problem of finding such nodes in the network is modeled by influence maximization problem, which faces two essential challenges: (1) inadequate selection of the seed nodes due to the lack of focus on the rich-club phenomenon and (2) high running time due to the lack of focus on pruning the graph nodes and localization. To solve these challenges, a computational localization-based RLIM algorithm is presented here to prevent the rich-club phenomenon. In this algorithm, the graph nodes are pruned based on the eigenvector centrality to reduce the computational overhead, and then the computations are performed locally using localization criteria. After that, influential nodes are selected by avoiding the rich-club phenomenon. In the RLIM algorithm, the seed nodes provided a better influence spread than the other algorithms. Experimental results on the synthetic and real-world datasets shows that the RLIM algorithm can verify the high effectiveness and efficiency than the comparable algorithms for an influence maximization problem.