Timezone: »

Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
Christopher W Lynn · Daniel Lee

Mon Dec 05 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #23

Influence maximization in social networks has typically been studied in the context of contagion models and irreversible processes. In this paper, we consider an alternate model that treats individual opinions as spins in an Ising system at dynamic equilibrium. We formalize the \textit{Ising influence maximization} problem, which has a natural physical interpretation as maximizing the magnetization given a budget of external magnetic field. Under the mean-field (MF) approximation, we present a gradient ascent algorithm that uses the susceptibility to efficiently calculate local maxima of the magnetization, and we develop a number of sufficient conditions for when the MF magnetization is concave and our algorithm converges to a global optimum. We apply our algorithm on random and real-world networks, demonstrating, remarkably, that the MF optimal external fields (i.e., the external fields which maximize the MF magnetization) exhibit a phase transition from focusing on high-degree individuals at high temperatures to focusing on low-degree individuals at low temperatures. We also establish a number of novel results about the structure of steady-states in the ferromagnetic MF Ising model on general graphs, which are of independent interest.

Author Information

Christopher W Lynn (University of Pennsylvania)

I am a physics PhD student at the University of Pennsylvania working with Professor Daniel D. Lee. My work is focused on exloring how tools and ideas from statistical mechanics can be used to study the behavior and optimization of dynamic processes on social networks. I received my BAs in Physics and Mathematics from Swarthmore College in 2014, where I played on the varsity soccer team.

Daniel Lee (University of Pennsylvania)

More from the Same Authors