Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model

By Xinran He, Guojie Song, Qingye Jiang. SDM, 2011

450 citations recorded by the source corpus.

In many real-world situations, different and often opposite opinions, innovations, or products are competing with one another for their social influence in a networked society. In this paper, we study competitive influence propagation in social networks under the competitive linear threshold (CLT) model, an extension to the classic linear threshold model. Under the CLT model, we focus on the problem that one entity tries to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate its own influence propagation. We call this problem the influence blocking maximization (IBM) problem. We prove that the objective function of IBM in the CLT model is submodular, and thus a greedy algorithm could achieve 1 − 1/e approximation ratio. However, the greedy algorithm requires Monte-Carlo simulations of competitive influence propagation, which makes the algorithm not efficient. We design an efficient algorithm CLDAG, which utilizes the properties of the CLT model, to address this issue. We conduct extensive simulations of CLDAG, the greedy algorithm, and other baseline algorithms on real-world and synthetic datasets. Our results show that CLDAG is able to provide best accuracy in par with the greedy algorithm and often better than other algorithms, while it is two orders of magnitude faster than the greedy algorithm.

Subfields: Management Science and Operations Research, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/392ea58ff65d855c06d9035bb72ef4448e7c15e1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Statistical and Nonlinear Physics

Citations in the corpus

Dynamic Network Embedding : An Extended Approach for Skip-gram based Network Embedding (2018, methodology): “As the input of machine learning models, the lowdimensional features help to complete specific tasks efficiently, such as vertex classification, clustering, graph visualization, link prediction and social influence analysis [He et al., 2012; Song et al., 2015].”
Influence Maximization on Social Graphs: A Survey (2018, methodology): “[5] propose greedy solutions for this problem in the IC and LT models respectively.”
Combating Fake News (2019, background): “[39] similarly showed that under the Linear Threshold model, the greedy algorithm ratio is (1 − 1/e ) without requiring restrictions on the influence weights.”
Scalable diffusion-aware optimization of network topology (2014, background): “The node deletion problem can be considered a special case of the “influence blocking maximization” problem described in [3, 9].”