A Local Search Algorithm for the Influence Maximization Problem

Abstract

Read online

How to select a set of top k nodes (called seeds) in a social network, through which the spread of influence under some certain diffusion models can achieve the maximum, is a major issue considered in the social network analysis. This problem is known as the Influence Maximization Problem (IMP). Due to its NP-hard nature, designing a “good” algorithm for the IMP is a very challengeable work. In this paper, we propose an efficient local search algorithm called DomIM to solve the IMP, which involves two main ideas. The first one is an approach to constructing an initial solution based on a dominating set, while the second is a degree based greedy strategy in the local search phase. DomIM is evaluated on three real world networks, under three widely-used diffusion models, including independent cascade (IC) model, weighted cascade (WC) model, and linear threshold (LT) model. Experimental results show that DomIM is competitive and efficient, and under all of these diffusion models it can obtain the best performance (in terms of solution quality) on the networks we consider.

Keywords

• social network
• influence maximization
• dominating set
• local search
• heuristic