Maximizing the Spread of Influence in a Social Network

A social network – the graph of relationships and interactions within a group of individuals – plays a fundamental role as a medium for the spread of information, ideas, and influence among its members. An idea or innovation will appear – for example, the use of cell phones among college students, the adoption of a new drug within the medical profession, or the rise of a political movement in an unstable society – and it can either die out quickly or make significant inroads into the population.

The resulting collective behavior of individuals in a social network has a long history of study in sociology. Recently, motivated by applications to word-of-mouth marketing, Domingos and Richardson proposed the following optimization problem: allocate a given «advertising» budget so as to maximize the (expected) number of individuals who will have adopted a given product or behavior.

In this talk, we will investigate this question under the mathematical models of influence studied by sociologists. We present and analyze a simple approximation algorithm, and show that it guarantees to reach at least a 1-1/e (roughly 63%) fraction of what the optimal solution can achieve, under many quite general models. In addition, we experimentally validate our algorithm, comparing it to several widely used heuristics on a data set consisting of collaborations among scientists.

(joint work with Jon Kleinberg and Eva Tardos)