Influential node identification in a constrained greedy way

Abstract Influence maximization aims to identify a set of influential nodes as seeds to initiate the propagation of influence so that the influence can be spread most widely. It plays critical roles in the areas such as rumor controlling, viral marketing and so on. Greedy algorithms have been exploited to identify seeds. They have been proved to provide the results approximating the optimum. However, non-neglectable iterative calculations and influence overlap between seeds degrade the performance and the efficiency of those algorithms. To alleviate the performance and efficiency degradation, we propose an influence maximization approach based on the property of submodularity. The approach selects seeds according to the influence propagated in a constrained greedy way to alleviate the performance degradation caused by non-neglectable iterative calculations. It performs rigorous overlap cost checks on the nodes which could be taken as seeds to relieve the efficiency degradation caused by the influence overlap. The experiments verify the performance and the efficiency of the approach.