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.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.