  Influence diffusion and influence maximization in large-scale online social
networks (OSNs) have been extensively studied, because of their impacts on
enabling effective online viral marketing. Existing studies focus on social
networks with only friendship relations, whereas the foe or enemy relations
that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely
ignored. In this paper, we make the first attempt to investigate the influence
diffusion and influence maximization in OSNs with both friend and foe
relations, which are modeled using positive and negative edges on signed
networks. In particular, we extend the classic voter model to signed networks
and analyze the dynamics of influence diffusion of two opposite opinions. We
first provide systematic characterization of both short-term and long-term
dynamics of influence diffusion in this model, and illustrate that the steady
state behaviors of the dynamics depend on three types of graph structures,
which we refer to as balanced graphs, anti-balanced graphs, and strictly
unbalanced graphs. We then apply our results to solve the influence
maximization problem and develop efficient algorithms to select initial seeds
of one opinion that maximize either its short-term influence coverage or
long-term steady state influence coverage. Extensive simulation results on both
synthetic and real-world networks, such as Epinions and Slashdot, confirm our
theoretical analysis on influence diffusion dynamics, and demonstrate the
efficacy of our influence maximization algorithm over other heuristic
algorithms.
