A Note on Maximizing the Spread of Influence in Social Networks
We consider the spread maximization problem that was defined by Domingos and Richardson [6,15]. In this problem, we are given a social network represented as a graph and are required to find the set of the most “influential” individuals that by introducin
- PDF / 334,966 Bytes
- 6 Pages / 430 x 660 pts Page_size
- 27 Downloads / 173 Views
Google Research [email protected] 2 Microsoft Research [email protected]
Abstract. We consider the spread maximization problem that was defined by Domingos and Richardson [6,15]. In this problem, we are given a social network represented as a graph and are required to find the set of the most “influential” individuals that by introducing them with a new technology, we maximize the expected number of individuals in the network, later in time, that adopt the new technology. This problem has applications in viral marketing, where a company may wish to spread the rumor of a new product via the most influential individuals in popular social networks such as Myspace and Blogsphere. The spread maximization problem was recently studied in several models of social networks [10,11,13]. In this short paper we study this problem in the context of the well studied probabilistic voter model. We provide very simple and efficient algorithms for solving this problem. An interesting special case of our result is that the most natural heuristic solution, which picks the nodes in the network with the highest degree, is indeed the optimal solution.
1
Introduction
With the emerging Web 2.0, the importance of social networks as a marketing tool is growing rapidly and the use of social networks as a marketing tool spans diverse areas, and has even been recently used by the campaigns of presidential candidates in the United States. Social networks are networks (i.e. graphs) in which the nodes represent individuals and the edges represent relations between them. To illustrate the viral marketing channel (see [2,3,6]), consider a new company that wishes to promote its new specialized search engine. A promising way these days would be through popular social network such as Myspace, Blogsphere etc, rather than using classical advertising channels. By convincing several key persons in each network to adopt (or even to try) the new search engine, the company can obtain an effective marketing campaign and to enjoy the diffusion effect over the network. If we assume that “convincing” each key person to “spread” the rumor on the new product costs money, then a natural problem is the following: given a social network, how can we detect the players through which we can spread, or “diffuse”, the new technology in the most effective way. X. Deng and F.C. Graham (Eds.): WINE 2007, LNCS 4858, pp. 281–286, 2007. c Springer-Verlag Berlin Heidelberg 2007
282
E. Even-Dar and A. Shapira
Diffusion processes in social network have been studied for a long time in social sciences, see e.g. [5,8,3,16]. The algorithmic aspect of marketing in social networks was introduced by Domingos and Richardson [6,15] and can be formulated as follows. Given a social network structure and a diffusion dynamics (i.e. how the individuals influence each other), find a set S of nodes of cost at most K that by introducing them with a new technology/product, the spread of the technology/product will be maximized. We refer to the problem of finding such a maximizing set S as the Spread max
Data Loading...
