# Sebastien Roch : Cascade Processes in Social Networks

Social networks are often represented by directed graphs 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 a stochastic process of ``infection'': each node becomes infected once an activation function of the set of its infected neighbors crosses a random threshold value. I will prove a conjecture of Kempe, Kleinberg, and Tardos which roughly states that if such a process is ``locally'' submodular then it must be ``globally'' submodular on average. The significance of this result is that it leads to a good algorithmic solution to the problem of maximizing the spread of influence in the network--a problem known in data mining as "viral marketing"'. This is joint work with Elchanan Mossel.

**Category**: Probability**Duration**: 01:14:42**Date**: January 24, 2008 at 1:25 PM**Views**: 161-
**Tags:**seminar, Probability Seminar

## 0 Comments