Elsevier

Computer Networks

Volume 123, 4 August 2017, Pages 38-50
Computer Networks

Scalable influence blocking maximization in social networks under competitive independent cascade models

https://doi.org/10.1016/j.comnet.2017.05.004Get rights and content

Abstract

Bad information propagation in online social networks (OSNs) can cause undesirable effects. The opposite good information propagating competitively with bad information can restrain the propagation of bad information. In this paper, we address the Influence Blocking Maximization (IBM) problem aiming to find a set of influential people initiating good information propagation to maximize the blocking effect on the bad information propagation in OSNs. The problem is studied on two competitive propagation models describing competitive propagation processes in two classic situations in OSNs. Two models are derived from the Independent Cascade Model (ICM). Greedy algorithms for IBM problem under two competitive propagation models are slow and not scalable. Thus, we design two heuristics CMIA-H and CMIA-O based on the maximum influence arborescence (MIA) structure to efficiently solve the IBM problem under two competitive propagation models, respectively. Extensive experiments are conducted on real-world and synthetic datasets to compare the proposed algorithms with the greedy algorithms and other baseline heuristics. The results demonstrate that both CMIA-H and CMIA-O achieve matching influence blocking performance to the greedy algorithms and consistently outperform other baseline heuristics, while they are several orders of magnitude faster than the greedy algorithms.

Introduction

Online Social Networks (OSNs), such as Facebook, Twitter and Weibo, etc., have become one of the most important platforms for the propagation of news, ideas, opinions, adoption of new products, etc.. Such information propagation is generally referred as influence propagation [1]. While OSNs are very beneficial for genuine and trustworthy information dissemination, their openness also facilitates the propagation of rumors, gossips and other kinds of misinformation which could potentially cause undesirable effects and even lead to serious economic and political consequences [2], [3], [4], [5]. For example, the rumor that “Two bombs had exploded at the White House, injuring Barack Obama” from hacked Associated Press Twitter account resulted to 10 billion USD losses [6]. Similarly, the negative information about a product propagating in OSNs can cause huge losses to a company. Misinformation and negative information are collectively called bad information in this paper.

In order to make OSNs a more reliable platform for information dissemination, it is crucial to seek effective strategies to reduce the devastating effects of bad information [2], [7]. If users have accepted good information used to correct bad information, they will hardly be influenced by such bad information [1], [2], [7], [8]. Thus the propagation of good information can restrain the propagation of corresponding bad information in OSNs [1], [2], [7], [8], [9], [10], [11], [12]. Given a set of bad information sources that initiate bad information propagation in OSNs, we study the Influence Blocking Maximization (IBM) problem of finding a set of users from whom the good information is disseminated so that the blocked negative influence range of bad information is maximized. The problem is studied on two competitive propagation models in this paper, i.e., Multi-Campaign Independent Cascade Model (MCICM) with high-effectiveness property and Campaign-Oblivious Independent Cascade Model (COICM) [2]. These two models are extended from Independent Cascade Model (ICM) [13] which is a classic stochastic propagation model describing how single information is propagated on the network starting from a set of seed nodes [1]. MCICM with high-effectiveness property and COICM describe and model competitive propagation processes in two classic situations, respectively. It has been proved that the IBM problems under above two models are NP-hard and their objective functions are submodular [2]. Thus, greedy algorithms can achieve an approximation ratio of 11/eϵ of the optimal solution, where e is the base of natural logarithm, and ϵ depends on the accuracy of the Monte–Carlo estimate of the influence spread range. However, the greedy algorithms are very slow for large networks, if we want to keep the above ϵ small by running the Monte–Carlo simulations a large number of times. Given that OSNs are usually very large and blocking bad information propagation typically requires immediate strategies before it propagates too far, we believe that the scalability issue of the greedy algorithms for IBM problems will hinder their application in containment of bad information propagation in OSNs.

In this paper, we address the scalability issue of the greedy algorithms by designing two efficient heuristic algorithms CMIA-H and CMIA-O for the IBM problem under MCICM with high-effectiveness property and COICM, respectively. The good (bad) information propagation is referred to as positive (negative) propagation and the good (bad) information spread range that measures the number of nodes accepting good (bad) information is referred to as positive (negative) influence spread. The main reason of the inefficiency of the greedy algorithms is that they spend a lot of time to estimate the negative influence spread by a large number of Monte–Carlo simulations. Inspired by [14], we approximately compute the negative influence spread in the local Maximum Influence Arborescence (MIA) structure of every node in two designed algorithms. The influence spread computation in MIA is more than three orders of magnitude faster than that by Monte–Carlo simulations. Thus two designed algorithms can be much faster than greedy algorithms. It should be noted that the influence spread computation procedures here are more complex than that in [14], since our propagation models model two competitive propagations while theirs only model a single propagation. Moreover, the computation procedures under MCICM with high-effectiveness property and COICM are different. Specifically, for MCICM with high-effectiveness property, we adopt the high-effectiveness property of the positive propagation to help compute the blocked negative influence of any node. While for COICM, we design a dynamic programming method to compute the blocked negative influence of any node. Then the node with the largest blocked negative influence is iteratively selected as the new positive seed. To test the efficiency and effectiveness of the proposed CMIA-H and CMIA-O, we conduct extensive experiments on several real-world and synthetic networks. The performance of two proposed algorithms is compared with both the greedy algorithms and several heuristic algorithms, and the results show that (a) compared with the greedy algorithms, CMIA-H and CMIA-O have matched influence blocking performance, while they are several orders of magnitude faster to run; and (b) compared with other scalable heuristics, CMIA-H and CMIA-O consistently outperform them in negative influence blocking performance with a significant margin.

The rest of the paper is organized as follows. Some related works are discussed in Section 2. Section 3 formalizes the IBM problem under the two competitive propagation models, i.e., MCICM with high-effectiveness property and COICM. In Section 4, we describe the CMIA-H algorithm for IBM problem under MCICM with high-effectiveness property, and the CMIA-O algorithm for IBM problem under COICM. The experiments results are analyzed in Section 5. Finally, Section 6 concludes the paper.

Section snippets

Related work

The influence maximization (IM) problem is first formulated as a combinatorial optimization problem by Kemp et al.[13]. They study the IM problem under the classic ICM and Linear Threshold Model (LTM), and propose a standard greedy algorithm with approximation guarantee of 11/eϵ. LTM is another single information stochastic propagation model. To address the scalability issue of the greedy algorithm, many follow-up studies [14], [15], [16], [17], [18], [19] try to propose much more efficient

Propagation models and problem definition

A social network is modeled as a directed graph G=(V,E), where V is a set of n nodes representing individuals and E is a set of m edges representing relationships. Each node is associated with some states indicating whether it accepts the information or not. Propagation is a state cascade process where the state changes of the nodes depend on the state changes of their in-neighbors, and will further influence the state changes of their out-neighbors. The propagation models define some rules to

Algorithms

Both CMIA-H and CMIA-O have the similar framework with the greedy algorithm that iteratively selects node that provides the largest marginal gain of blocked negative influence into the positive seed set until k nodes are selected. However, they compute the blocked negative influence and its marginal gain approximately in the local MIA structure [14] rather than by Monte–Carlo simulations. MIA structure is originally proposed to estimate influence spread in the ICM. MIA is a joint name of

Experiments

In this section, we conduct experiments on four real-world networks and a set of synthetic networks to evaluate the efficiency and effectiveness of our algorithms for IBM problem under the MCICM with high-effectiveness property and COICM. All experiments are carried out on a computer running 64bit Windows 10 and equipped with 3.4GHz Quad-Core Intel i7-6700 and 16GB RAM. All experiment code is written in C++.

Conclusion

The IBM problem aims to find a set of positive seeds initiating positive propagation to maximize the blocked negative influence of a given negative seed set. Though greedy algorithms for IBM problem under both MCICM with high-effectiveness property and COICM have approximation guarantee, they are too slow to run on large networks. In this paper, we address the scalability issue of solving the IBM problem under MCICM with high-effectiveness property and COICM, respectively. Two efficient

Acknowledgments

This work is supported by National Key Basic Research Program of China (2013CB329603), National Natural Science Foundation of China (U1636105).

Peng Wu is currently a PhD Student in Department of Electronic Engineering in Shanghai Jiao Tong University. He has received the B.S. degree in School of Information Science and Engineering in Southeast University, Nanjing, China, in 2012. His research interests include social network, data mining and computational intelligence.

References (31)

  • X. He et al.

    Influence blocking maximization in social networks under the competitive linear threshold model.

    SDM

    (2012)
  • C. Budak et al.

    Limiting the spread of misinformation in social networks

    Proceedings of the 20th international conference on World wide web

    (2011)
  • S. Wen et al.

    To shut them up or to clarify: restraining the spread of rumors in online social networks

    IEEE Trans. Parallel Distrib. Syst.

    (2014)
  • Z. He et al.

    Modeling propagation dynamics and developing optimized countermeasures for rumor spreading in online social networks

    Distributed Computing Systems (ICDCS), 2015 IEEE 35th International Conference on

    (2015)
  • Y. Song et al.

    Optimal containment of misinformation in social media: A scenario-based approach

    International Conference on Combinatorial Optimization and Applications

    (2014)
  • P. Foster, ’bogus’ AP tweet about explosion at the white house wipes billions off US markets, 2013,...
  • N.P. Nguyen et al.

    Containment of misinformation spread in online social networks

    Proceedings of the 4th Annual ACM Web Science Conference

    (2012)
  • L. Fan et al.

    Least cost rumor blocking in social networks

    Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on

    (2013)
  • L. Fan et al.

    Maximizing rumor containment in social networks with constrained time

    Social Netw. Anal. Min.

    (2014)
  • Y. Ping et al.

    Sybil-aware least cost rumor blocking in social networks

    2014  IEEE Global Communications Conference

    (2014)
  • N. Wang et al.

    Containment of misinformation propagation in online social networks with given deadline.

    PACIS

    (2014)
  • H. Zhang et al.

    Limiting the spread of misinformation while effectively raising awareness in social networks

    International Conference on Computational Social Networks

    (2015)
  • D. Kempe et al.

    Maximizing the spread of influence through a social network

    Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    (2003)
  • W. Chen et al.

    Scalable influence maximization for prevalent viral marketing in large-scale social networks

    Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    (2010)
  • J. Leskovec et al.

    Cost-effective outbreak detection in networks

    Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining

    (2007)
  • Cited by (81)

    • Influence maximization through exploring structural information

      2023, Applied Mathematics and Computation
      Citation Excerpt :

      Scholars are interested in this topic due to its potential commercial value [5]. The IM problem has important and broad application prospects in various areas including viral marketing [6], network monitoring [7,8], rumor control [9,10], epidemic spreading [11,12], and social computing [13,14]. For instance, in viral marketing, a company wants to maximize the popularity of a new product; thus, they need to explore a group of key users, while a larger number of consumers can be attracted to endorse the product through the social connections of those key users.

    • Non-Uniform Influence Blocking Maximization in Social Network

      2022, Expert Systems with Applications
      Citation Excerpt :

      The computational cost of greedy algorithm is mostly caused by Monte-Carlo simulations. Therefore, Wu and Pan (2017) proposed an approximation algorithm to calculate negative influence spread based on Maximum Influence Arborescence (MIA) structure. Lin and Dai (2019) proposed BIOG (Block Influence Out Graph), a two-phase algorithm to constrain the propagation of rumor in OSN.

    • Influence blocking maximization on networks: Models, methods and applications

      2022, Physics Reports
      Citation Excerpt :

      Based on this possibility graph, the author used cost effective lazy forward (CELF) algorithm [204] to select competitive seed nodes. Wu et al. [88] proposed a heuristic algorithm CMIA-H to find a group of users who spread information that is beneficial to themselves. They also presented a heuristic algorithm CMIA-O, to counteract the spread of the competitor’s information by maximizing the blocking on competitors’ information sphere.

    View all citing articles on Scopus

    Peng Wu is currently a PhD Student in Department of Electronic Engineering in Shanghai Jiao Tong University. He has received the B.S. degree in School of Information Science and Engineering in Southeast University, Nanjing, China, in 2012. His research interests include social network, data mining and computational intelligence.

    Li Pan received the B.S. degree in electronic engineering from Xidian University, China, in 1996, and received the M.S. degree in computer science from Nanjing University of Telecommunications, China, in 1999, then received the Ph.D. degree in communication and information system from Shanghai Jiao Tong University, China, in 2002. Since 2002, he has been working in Shanghai Jiao Tong University. In 2008, he worked as a visiting scholar in IBM Research T.J. Watson Center, USA. In 2014, he worked as a visiting scholar in the computer department of Boston University, USA. His research interests focus on policy base access control, system security and social computing. He published over 60 papers, 5 co-authored books on operating system and network security, and hold 7 granted patents. In 2007 and 2008, he was awarded by Shanghai Rising-Star Program for Young Scientists in China, and Foundation for the Shanghai Talents in China respectively. In 2013, he was elected for the Shanghai Subject Chief Scientist in China.

    View full text