Maximizing Activity in Ising Networks via the TAP Approximation

Christopher W. Lynn, Daniel D. LeeAAAI 2018 · DOI

Introduction

Ising models are fundamental tools for understanding collective behavior in complex systems, ranging from neural firing patterns to the spread of opinions in social networks. In these systems, nodes exist in binary states (+1 or -1), influenced by their neighbors and external biases. A critical challenge in managing these networks is influence maximization: determining how to allocate a limited external budget to maximize the total network activity. Because the state space grows exponentially ($2^n$), exact solutions are computationally intractable for large networks, necessitating efficient approximation methods.

Theoretical Framework and Methodology

The authors address the influence maximization problem in two distinct settings:

  1. Continuous Setting: Influence is finely tuned across all nodes. The authors employ Projected Gradient Ascent (PGA). To calculate the necessary response functions, they utilize the Plefka expansion, moving beyond the standard Mean Field (MF) approximation to higher-order TAP (Thouless-Anderson-Palmer) and TAP3 approximations. These higher-order terms account for stochastic fluctuations and feedback loops often ignored by simpler models.
  2. Discrete Setting: A subset of nodes is selected to be "forced" into an active state. The authors use a Greedy Algorithm (GI).

A significant theoretical contribution of this work is the application of the GHS inequality from statistical physics. The authors prove that for networks with non-negative interactions, the total activity is a submodular function. This property ensures that the greedy approach provides a solution within at least 63% ($1 - 1/e$) of the global optimum.

Experimental Evaluation

The proposed algorithms were tested across diverse network topologies, including Erdős-Rényi random graphs, Preferential Attachment models (mimicking social structures), and a real-world arXiv collaboration network of 904 nodes.

Performance of MF, TAP, and TAP3 approximations across different network types. The relative error $(M(h)-M(h^*))/M(h^*)$ is plotted against the interaction strength $\rho(J)$.

As shown in the experimental results, the TAP approximation serves as a "sweet spot" for practical applications. While the first-order Mean Field (MF) approach is computationally fast, it frequently suffers from significant inaccuracies. Conversely, while Monte Carlo simulations provide high accuracy, they are prohibitively slow for large-scale optimization. The TAP-based methods consistently outperformed MF across all datasets, maintaining high accuracy while remaining computationally efficient—converging in seconds where gold-standard benchmarks took minutes.

Conclusion and Future Directions

By integrating statistical physics with network science, this research demonstrates that modeling stochastic noise is essential for effective influence maximization. The TAP approximation provides a robust framework for optimizing interventions in real-world social and biological networks. Future work aims to extend these methods to networks with inhibitory (negative) interactions and to develop control theories for steering networks toward specific target states rather than simple activity maximization.

Summary updated

BibTeX
@inproceedings{lynn2018maximizing,
  author = {Christopher W. Lynn and Daniel D. Lee},
  title = {{Maximizing Activity in Ising Networks via the TAP Approximation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11333},
}
Figure