Wednesday, April 9th, 6:30 PM in Kemeny 004

Abstract: The problem of seeding "contagion" in social networks has attracted substantial attention for its connection to viral marketing. Simple information-spread models yield nice mathematical properties that allow theoretical algorithmic traction. This work often points to some form of "exposure" as the best paradigm for designing seed sets. While exposure-based seeding may spread awareness effectively, being aware of a behavior often doesn't result in a decision to adopt it. When environmental economists describe decisions to engage in green behaviors, when sociologists model norm-spread, and when game theorists consider choices to adopt cooperative strategies in repeated-game-play, a common more-complex spread mechanism emerges.  What can we learn about how to virally market biking to work, adopting health-related behaviors, and cooperating at an equilibrium that is mutually beneficial?

I'll mention convergence results for this spread mechanism, (daunting) hardness results for the seeding question, and (heartening) computational results from heuristics derived by truncating an exact (inefficient) Integer Program.   Compared to exposure-based seeding, the advantage of a seeding paradigm that establishes "critical mass locally" appears largest when the network is highly clustered (as social networks often are).