Scalable influence blocking maximization in social networks under competitive independent cascade models
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 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 . 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 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)
- et al.
Influence blocking maximization in social networks under the competitive linear threshold model.
SDM
(2012) - et al.
Limiting the spread of misinformation in social networks
Proceedings of the 20th international conference on World wide web
(2011) - et al.
To shut them up or to clarify: restraining the spread of rumors in online social networks
IEEE Trans. Parallel Distrib. Syst.
(2014) - 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) - 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,...
- et al.
Containment of misinformation spread in online social networks
Proceedings of the 4th Annual ACM Web Science Conference
(2012) - et al.
Least cost rumor blocking in social networks
Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on
(2013) - et al.
Maximizing rumor containment in social networks with constrained time
Social Netw. Anal. Min.
(2014) - et al.
Sybil-aware least cost rumor blocking in social networks
2014 IEEE Global Communications Conference
(2014)
Containment of misinformation propagation in online social networks with given deadline.
PACIS
Limiting the spread of misinformation while effectively raising awareness in social networks
International Conference on Computational Social Networks
Maximizing the spread of influence through a social network
Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
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
Cost-effective outbreak detection in networks
Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining
Cited by (81)
Influence maximization through exploring structural information
2023, Applied Mathematics and ComputationCitation 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.
Targeted influence maximization in competitive social networks
2023, Information SciencesNon-Uniform Influence Blocking Maximization in Social Network
2022, Expert Systems with ApplicationsCitation 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 ReportsCitation 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.
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.