Statistical mechanics of influence maximization with thermal noise. (24th May 2017)

• Record Type: Journal Article
• Authors: Lynn, Christopher W.; Lee, Daniel D.
• Is Part Of: Europhysics letters. Volume 117:Number 6(2017:Mar.)
• Publication Date: 2017-05-24
• Subjects: 64.60.De -- 64.60.aq -- 89.75.Fb; Physics -- Periodicals; Electronic journals; 530.05
• DOI: 10.1209/0295-5075/117/66001
• Languages: English
• ISSNs: 0295-5075

Abstract

Abstract: The problem of optimally distributing a budget of influence among individuals in a social network, known as influence maximization, has typically been studied in the context of contagion models and deterministic processes, which fail to capture stochastic interactions inherent in real-world settings. Here, we show that by introducing thermal noise into influence models, the dynamics exactly resemble spins in a heterogeneous Ising system. In this way, influence maximization in the presence of thermal noise has a natural physical interpretation as maximizing the magnetization of an Ising system given a budget of external magnetic field. Using this statistical mechanical formulation, we demonstrate analytically that for small external-field budgets, the optimal influence solutions exhibit a highly non-trivial temperature dependence, focusing on high-degree hub nodes at high temperatures and on easily influenced peripheral nodes at low temperatures. For the general problem, we present a projected gradient ascent algorithm that uses the magnetic susceptibility to calculate locally optimal external-field distributions. We apply our algorithm to synthetic and real-world networks, demonstrating that our analytic results generalize qualitatively. Our work establishes a fruitful connection with statistical mechanics and demonstrates that influence maximization depends crucially on the temperature of the system, a fact that has not been appreciated by existing research.