##### Department of Mathematics,

University of California San Diego

****************************

### Special Colloquium

## Sebastien Roch

#### Microsoft Research

## Cascade Processes in Social Networks

##### Abstract:

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.

Host: Pat Fitzsimmons

### January 10, 2008

### 1:00 PM

### AP&M 2402

****************************