Article Preview
TopIntroduction
This “word-of-mouth” (WOM) dissemination of information through social networks is of paramount importance in our everyday life. There is a wide range of situations (epidemiology, computer virus, marketing, political science, and agriculture etc.), in which users coordinate their decisions and form conventions through being influenced by behaviors of their friends or neighbors, e.g., either to adopt a new behavior or product or not. Consider the following hypothetical scenario as a motivating example. A small company develops a new product and wants to market it through real social networks through the effect of WOM. Due to the limited budget for marketing, it can only select a small number of initial users in social networks to use it (by giving them gifts or payments). The company wishes that these initial users would start influencing their friends on the social network to use it, and their friends would influence their friends' friends and so on, and thus through so-called contagion process, a large population in the social network would finally adopt the application. The problem is whom to be selected as the initial users so that they eventually influence the largest number of people in the network.
The above problem, called influence maximization, was firstly stated by (Domingos, & Richardson, 2001): if we can try to convince a subset of individuals to adopt a new product and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target in order to achieve a maximized influence? It was shown that, finding the influential set of nodes is NP-hard problem. Only for submodular function of diffusion model, the greedy algorithm can approximately work, with bounded threshold. (Kempe, Kleinberg, & Tardos, 2003) have proved that a simple greedy algorithm (choosing the nodes with maximal marginal gain) can approximate the optimal solution by a (1-1/e), i.e., within 63% of optimal. However, the simple greedy-based approach has a heavy computation load. Specifically, the Greedy-based algorithm calculates the influence power precisely by enumeration. The more rounds the enumeration takes, the more accurate the result will get. However, when the network size increases, the computational time will increase dramatically, which prevents the greedy algorithm to become a feasible solution for the influence maximization problem in the real world. The research community has greatly studied the algorithmic aspects of maximizing influence in social networks, basically from two directions to solve the problem of efficiency: improving the greedy algorithm to further reduce its running time; the second is to propose new heuristics.
(Leskovec, Krause, Guestrin, Faloutsos, VanBriesen, & Glance, 2007) presented an optimized greed algorithm, which is referred as the “Cost-Effective Lazy Forward (CELF)” scheme. The CELF optimization uses the submodular property of the influence maximization objective to reduce the number of evaluations on the influence spread of nodes. Their experimental results demonstrate that, in comparison with simple greedy-based approach, CELF optimization could achieve as much as 700 times speedup in selecting seeds.
Considering the fundamental step of the greedy algorithm is to pick a node in each iteration from the remaining nodes, which attempts to make the maximum marginal contribution to the process of spread of information, (Narayanam, & Narahari, 2011) proposed a SPIN (ShaPley value based Influential Nodes) algorithms for computing the marginal contributions using the concept of Shapley (a well-known solution concept in cooperative game theory). Specifically, the Shapley value of a coalitional game provides the marginal contributions of the individual players to the overall value that can be achieved by the grand coalition of all the players.