  While influence maximization in social networks has been studied extensively
in computer science community for the last decade the focus has been on the
progressive influence models, such as independent cascade (IC) and Linear
threshold (LT) models, which cannot capture the reversibility of choices. In
this paper, we present the Heat Conduction (HC) model which is a
non-progressive influence model with real-world interpretations. We show that
HC unifies, generalizes, and extends the existing nonprogressive models, such
as the Voter model [1] and non-progressive LT [2]. We then prove that selecting
the optimal seed set of influential nodes is NP-hard for HC but by establishing
the submodularity of influence spread, we can tackle the influence maximization
problem with a scalable and provably near-optimal greedy algorithm. We are the
first to present a scalable solution for influence maximization under
nonprogressive LT model, as a special case of the HC model. In sharp contrast
to the other greedy influence maximization methods, our fast and efficient
C2GREEDY algorithm benefits from two analytically computable steps: closed-form
computation for finding the influence spread as well as the greedy seed
selection. Through extensive experiments on several large real and synthetic
networks, we show that C2GREEDY outperforms the state-of-the-art methods, in
terms of both influence spread and scalability.
