Authors: V. Tejaswi; P.V. Bindu; P. Santhi Thilagam
Addresses: Department of Computer Science and Engineering, National Institute of Technology Karnataka, India ' Department of Computer Science and Engineering, Government College of Engineering Kannur, Kerala, India ' Department of Computer Science and Engineering, National Institute of Technology Karnataka, India
Abstract: Influence maximisation is one of the significant research areas in social network analysis. It helps in identifying influential entities from social networks that can be used in marketing, election campaigns, outbreak detection and so on. Influence maximisation deals with the problem of finding a subset of nodes called seeds in the social network such that these nodes will eventually spread maximum influence in the network. This is an NP-hard problem. The aim of this paper is to provide a complete understanding of the influence maximisation problem. This paper focuses on providing an overview on the influence maximisation problem, and covers three major aspects: 1) different types of inputs required; 2) influence propagation models that map the spread of influence in the network; 3) the approximation algorithms proposed for seed set selection. In addition, we provide the state of the art and describe the open problems in this domain.
Keywords: social networks; social network analysis; influence maximisation; labelled influence maximisation; approximation algorithms; information diffusion; influence propagation models; threshold models; cascade models.
International Journal of Computational Science and Engineering, 2019 Vol.18 No.2, pp.103 - 117
Received: 02 Feb 2017
Accepted: 02 Dec 2017
Published online: 14 Feb 2019 *