  In the study of social networks, a fundamental problem is that of influence
maximization (IM): How can we maximize the collective opinion of individuals in
a network given constrained marketing resources? Traditionally, the IM problem
has been studied in the context of contagion models, which treat opinions as
irreversible viruses that propagate through the network. To study reverberant
opinion dynamics, which yield complex macroscopic behavior, the IM problem has
recently been proposed in the context of the Ising model of opinion dynamics,
in which individual opinions are treated as spins in an Ising system. In this
paper, we are among the first to explore the \textit{Ising influence
maximization (IIM)} problem, which has a natural physical interpretation as the
maximization of the magnetization given a budget of external magnetic field,
and we are the first to consider the IIM problem in general Ising systems with
negative couplings and negative external fields. For a general Ising system, we
show analytically that the optimal external field (i.e., that which maximizes
the magnetization) exhibits a phase shift from intuitively focusing on
high-degree nodes at high temperatures to counterintuitively focusing on
"loosely-connected" nodes, which are weakly energetically bound to the ground
state, at low temperatures. We also present a novel and efficient algorithm for
solving IIM with provable performance guarantees for ferromagnetic systems in
nonnegative external fields. We apply our algorithm on large random and
real-world networks, verifying the existence of phase shifts in the optimal
external fields and comparing the performance of our algorithm with the
state-of-the-art mean-field-based algorithm.
