Influence maximization based on partial network structure information : A comparative analysis on seed selection heuristics

Abstract

In this study, the problem of seed selection is investigated. This problem is mainly treated as an optimization problem, which is proved to be NP-hard. There are several heuristic approaches in the literature which mostly use algorithmic heuristics. These approaches mainly focus on the trade-o between computational complexity and accuracy. Although the accuracy of algorithmic heuristics are high, they also have a high computational complexity. Furthermore, in the literature it is generally assumed that complete information on the structure and features of a network is available, which is not the case in most of the times. For the study, a simulation model is constructed, which is capable of creating networks, performing seed selection heuristics, and simulating di usion models. Novel metric-based seed selection heuristics that rely on partial information are proposed and tested using the simulation model. These heuristics use local information available from nodes in the synthetically created networks. The performances of heuristics are comparatively analyzed on three di erent networks and two di erent di usion models, i.e. six combinations. The results suggest that the performance of a heuristic depends on the structure of a network. A heuristic to be used should be selected after investigating the properties of the network at hand. Also, the approach of partial information provided promising results. It has approximated to the performances of heuristics relying on complete information in most of the cases.