Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation

ACM Special Interest Group on Management of Data

Hao Liao¹   Sheng Bi¹   Jiao Wu¹  Wei Zhang¹  Mingyang Zhou¹  Rui Mao¹  Wei Chen^2*

¹Shenzhen University    ²Microsoft Research China

Abstract

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 popularity ratio is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate 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 our proposed 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.

Fig. 1. A numerical example of the PA-IC model with the overlapping influence setting. In this example, we show the changes in popularity measure of two items, within two rounds. In this directed graph, every edge’s activation probability is equal to 1. Black nodes is the "active" nodes in each round.

Fig. 2. The popularity ratio vs. budgets for different algorithms in OINS setting.

Fig. 3. The popularity ratio vs. budgets for different algorithms in NIOS setting

Fig. 4. The popularity ratio vs. budgets for different algorithms when the popular item has promotion.

Acknowledgement

The authors acknowledge financial support from the National Natural Science Foundation of China (Grant Nos. 62276171 and 62072311), National Key R&D Program of China (Grant Nos. 2021YFB3301502 and 2021YFB3301503), Shenzhen Fundamental Research-General Project (Grant Nos. JCYJ20190808162601658, 20220811155803001 and 20210324094402008), MSRA Star track project, CCF-Baidu Open Fund (Grant No. OF2022028), and SZU Swiftlet (FinTech) Fund.

Bibtex

@inproceedings{HaoL23,

 author = { Hao Liao and Sheng Bi and Jiao Wu and Wei Zhang and Mingyang Zhou and Rui Mao and Wei Chen},

 title = {Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation},

 booktitle = {{SIGMOD} '23: International Conference on Management of Data, Seattle, WA, USA, June 18 - 23, 2023},

pages = {1--26},

publisher = {{ACM}}

 year = {2023},

 url = { https://doi.org/10.1145/3589309},

 doi = {10.1145/3589309},

}

Downloads