  In this paper, we present an algorithmic study on how to surpass competitors
in popularity by strategic promotions in social networks. We first propose a
novel model, in which we integrate the Preferential Attachment (PA) model for
popularity growth with the Independent Cascade (IC) model for influence
propagation in social networks called PA-IC model. In PA-IC, a popular item and
a novice item grab shares of popularity from the natural popularity growth via
the PA model, while the novice item tries to gain extra popularity via
influence cascade in a social network. The {\em popularity ratio} is defined as
the ratio of the popularity measure between the novice item and the popular
item. We formulate {\em Popularity Ratio Maximization (PRM)} as the problem of
selecting seeds in multiple rounds to maximize the popularity ratio in the end.
We analyze the popularity ratio and show that it is monotone but not
submodular. To provide an effective solution, we devise a surrogate objective
function and show that empirically it is very close to the original objective
function while theoretically, it is monotone and submodular. We design two
efficient algorithms, one for the overlapping influence and non-overlapping
seeds (across rounds) setting and the other for the non-overlapping influence
and overlapping seed setting, and further discuss how to deal with other models
and problem variants. Our empirical evaluation further demonstrates that the
proposed PRM-IMM method consistently achieves the best popularity promotion
compared to other methods. Our theoretical and empirical analyses shed light on
the interplay between influence maximization and preferential attachment in
social networks.
