  The spread of influence in social networks is studied in two main categories:
the progressive model and the non-progressive model (see e.g. the seminal work
of Kempe, Kleinberg, and Tardos in KDD 2003). While the progressive models are
suitable for modeling the spread of influence in monopolistic settings,
non-progressive are more appropriate for modeling non-monopolistic settings,
e.g., modeling diffusion of two competing technologies over a social network.
Despite the extensive work on the progressive model, non-progressive models
have not been studied well. In this paper, we study the spread of influence in
the non-progressive model under the strict majority threshold: given a graph
$G$ with a set of initially infected nodes, each node gets infected at time
$\tau$ iff a majority of its neighbors are infected at time $\tau-1$. Our goal
in the \textit{MinPTS} problem is to find a minimum-cardinality initial set of
infected nodes that would eventually converge to a steady state where all nodes
of $G$ are infected.
  We prove that while the MinPTS is NP-hard for a restricted family of graphs,
it admits an improved constant-factor approximation algorithm for power-law
graphs. We do so by proving lower and upper bounds in terms of the minimum and
maximum degree of nodes in the graph. The upper bound is achieved in turn by
applying a natural greedy algorithm. Our experimental evaluation of the greedy
algorithm also shows its superior performance compared to other algorithms for
a set of real-world graphs as well as the random power-law graphs. Finally, we
study the convergence properties of these algorithms and show that the
non-progressive model converges in at most $O(|E(G)|)$ steps.
