Abstract
Influence maximization, defined by Kempe et al. [3] is a hot problem in the field of network analysis. This problem is to target k users as seeds in a network G and then maximize the spread of influence in that network. Many models are proposed to mimic certain behaviours of the social networks according to the observations on the network. Based on these models, various techniques are applied and they can give a feasible approximation solution even for large-scale networks. In this survey, the influence maximization problem will be formulated and some related theorems are proven. Models and techniques will be summarized following the popular datasets and applications. The future direction on this problem will also be talked in the last.
I. INTRODUCTION
With the rapid development of the Internet around the world, social networks become more and more popular. Social networks connect numerous people together within a short period of time and have revolutionized the way people communicate with each other. Information spreads on social networks, ideas and knowledge are shared through social networks, and people can influence others by interaction on social networks. These properties have attracted scientists from sociology, economics as well as computer science. Thus, many problems from social network analysis are studied, such as the diffusion models and the social influence. Diffusion models are studied to model the behaviour of social networks which further help solve some problems based on these models like influence maximization(IM) problem which is to find the k most influential nodes in a social network that maximize the spread of the influence. One of the goal to study the social influence is also to solve the IM problem.
VIII. CONCLUSION
This survey summarizes the models, techniques, datasets, and applications about the influence maximization problem. At first, the IM problem is formulated and simply analysed. The monotonicity and submodularity are also proven. Then models are summarised according to their behaviour. Following models, techniques are divided corresponding to the core idea inside. Datasets are also essential to know the details of the dataset will affect the design of models and algorithms. For the applications, influence maximization plays an important role in marketing since the influence propagation can contribute to the increment of profits. Of course, controlling influence spreading is also closely related to IM problem. At last, some future directions on this problem are discussed according to recent works.
