An efficient variable neighbourhood search heuristic for the influential selection problem

Abstract

A online social network consists of individuals or entities which are tied by a certain type of interdependency such as collaboration, friendship or acquaintance. Due to the wide usage of internet, many companies actively use this new media in their marketing campaigns. Given an online social network, a person that influences his/her connections is called an influential. Since companies have limited budgets for advertising, they have to correctly select the influentials, which will forward their message to their connections over various online social networks and hope that a cascade will be triggered so that a maximum number of individuals are reached. In most of the previous studies the social networks are modeled as stochastic fields where the cascading process is represented by linear threshold or independent cascade models. It is shown that determining the top-k influential nodes within the network under this setting is NP-hard and a greedy based heuristic provides a provable approximation guarantee. Following these initial efforts many researchers worked on the improvement of the efficiency of the greedy algorithm without focusing on the solution quality. In this study, the problem of selecting the best k-influentials in social netrowk is studied from the solution quality perspective and using a Variable Neighbourhood Serach(VNS) heuristic optimal solutions are sought. Experimental analysis on certain real-life data is carried out to determine the performance of the techniques proposed.