Efficient influence maximization by employing the K -core algorithm in social networks

Influence maximization (IM) is the problem of finding k sample nodes or seed nodes in a social network that maximize the spread of influence. This issue can be used in many areas including optimal advertising, viral marketing, neuroscience, traffic, etc. IM under most propagation models has been proven to be an NP-hard problem, therefore, many heuristics have been introduced since then to solve the problem and find an efficient solution including the greedy algorithm. The problem with this heuristic is the costly running time. In this paper, a hybrid model is proposed and the greedy algorithm is improved by preprocessing throughout the network and pruning ineffective nodes with low degrees. The pruning algorithm would be the k-core algorithm. The influence rate is evaluated in the next phase by employing a new version of the independent cascade model (IC) to be more compatible with dense graphs. Notwithstanding the simplicity, the experimental results show that this hybrid algorithm achieves very efficient running time, and the calculations are way low. It runs in less than a few milliseconds while many simulation-based algorithms such as the greedy algorithm last hours.

کلیدواژه ها:

Influence maximization ، Social networks ، Social networks marketing ، Social influence