## Diffusion of Influence in Social Networks

#### Sebastien RochUC BerkeleyStatistics

A social network can be represented by a directed graph where the nodes are individuals and the edges indicate a form of social relationship. A simple way to model the diffusion of ideas, innovative behavior, or "word-of-mouth" effects on such a graph is to consider an increasing process of infected'' nodes: each node becomes infected once an activation function of the set of its infected neighbors crosses a threshold value. I will prove a conjecture of Kempe, Kleinberg, and Tardos which, roughly speaking, states that if such a process is locally''
submodular then it must be globally'' submodular. The significance of this result is that it leads to a good approximation algorithm for the problem of maximizing the spread of influence on the network---a problem known in data mining as viral marketing''. This is joint work with Elchanan Mossel.

Back to Workshop III: Random and Dynamic Graphs and Networks