2026-07-24T01:45:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19558 2024-03-06T11:04:19Z ddc:004 open_access

Influence Maximization in Ising Models Chen, Zongchen Mossel, Elchanan Influence maximization Ising model phase transition correlation decay Given a complex high-dimensional distribution over {± 1}ⁿ, what is the best way to increase the expected number of +1’s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been widely studied in social networks, biology, and computer science. In this paper, we consider influence maximization on the Ising model which is a prototypical example of undirected graphical models and has wide applications in many real-world problems. We establish a sharp computational phase transition for influence maximization on sparse Ising models under a bounded budget: In the high-temperature regime, we give a linear-time algorithm for finding a small subset of variables and their values which achieve nearly optimal influence; In the low-temperature regime, we show that the influence maximization problem cannot be solved in polynomial time under commonly-believed complexity assumption. The critical temperature coincides with the tree uniqueness/non-uniqueness threshold for Ising models which is also a critical point for other computational problems including approximate sampling and counting. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zongchen Chen and Elchanan Mossel 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.30 urn:nbn:de:0030-drops-195588 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode