An efficient preprocessing method for influence maximization problem in complex networks

The influence maximization (IM) is aimed at finding a small set of nodes in a social network that can maximize the spread of influence. One of the main challenges in IM problem is high computational time. This paper proposes an efficient preprocessing method to filter less important nodes in original graph regarding to optimal selection and improving computational time, called OPIM algorithm. It is based on the elimination of low degree and high clustering coefficient nodes in low importance positions. OPIM algorithm reduces the search space for finding final influential nodes. The proposed method improves the time complexity and infection rate. Consequently, the final seed nodes are selected based on the combination of shortest path effect and the degree centrality over the reduced graph. The result depicts that the new algorithm outperforms other algorithms in terms of efficiency and time complexity

Keywords:

Influence maximization , Seed node , Social networks , Independent cascade model