Issue |
EPL
Volume 117, Number 6, March 2017
|
|
---|---|---|
Article Number | 66001 | |
Number of page(s) | 7 | |
Section | Condensed Matter: Structural, Mechanical and Thermal Properties | |
DOI | https://doi.org/10.1209/0295-5075/117/66001 | |
Published online | 24 May 2017 |
Statistical mechanics of influence maximization with thermal noise
1 Department of Physics and Astronomy, University of Pennsylvania - Philadelphia, PA, USA
2 Department of Electrical and Systems Engineering, University of Pennsylvania - Philadelphia, PA, USA
Received: 9 January 2017
Accepted: 5 May 2017
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.
PACS: 64.60.De – Statistical mechanics of model systems (Ising model, Potts model, field-theory models, Monte Carlo techniques, etc.) / 64.60.aq – Networks / 89.75.Fb – Structures and organization in complex systems
© EPLA, 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.