Timezone: »
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
-
2017 : Poster Session (encompasses coffee break) »
Beidi Chen · Borja Balle · Daniel Lee · iuri frosio · Jitendra Malik · Jan Kautz · Ke Li · Masashi Sugiyama · Miguel A. Carreira-Perpinan · Ramin Raziperchikolaei · Theja Tulabandhula · Yung-Kyun Noh · Adams Wei Yu -
2017 Poster: Generative Local Metric Learning for Kernel Regression »
Yung-Kyun Noh · Masashi Sugiyama · Kee-Eung Kim · Frank Park · Daniel Lee -
2016 Poster: Efficient Neural Codes under Metabolic Constraints »
Zhuo Wang · Xue-Xin Wei · Alan A Stocker · Daniel Lee -
2014 Workshop: Novel Trends and Applications in Reinforcement Learning »
Csaba Szepesvari · Marc Deisenroth · Sergey Levine · Pedro Ortega · Brian Ziebart · Emma Brunskill · Naftali Tishby · Gerhard Neumann · Daniel Lee · Sridhar Mahadevan · Pieter Abbeel · David Silver · Vicenç Gómez -
2013 Poster: Optimal Neural Population Codes for High-dimensional Stimulus Variables »
Zhuo Wang · Alan A Stocker · Daniel Lee -
2012 Poster: Optimal Neural Tuning Curves for Arbitrary Stimulus Distributions: Discrimax, Infomax and Minimum $L_p$ Loss »
Zhuo Wang · Alan A Stocker · Daniel Lee -
2012 Poster: Diffusion Decision Making for Adaptive k-Nearest Neighbor Classification »
Yung-Kyun Noh · Frank Park · Daniel Lee -
2010 Poster: Learning via Gaussian Herding »
Yacov Crammer · Daniel Lee -
2010 Poster: Generative Local Metric Learning for Nearest Neighbor Classification »
Yung-Kyun Noh · Byoung-Tak Zhang · Daniel Lee -
2008 Poster: Extended Grassmann Kernels for Subspace-Based Learning »
Jihun Hamm · Daniel Lee -
2007 Oral: Blind channel identification for speech dereverberation using l1-norm sparse learning »
Yuanqing Lin · Jingdong Chen · Youngmoo E Kim · Daniel Lee -
2007 Poster: Blind channel identification for speech dereverberation using l1-norm sparse learning »
Yuanqing Lin · Jingdong Chen · Youngmoo E Kim · Daniel Lee