AnEfficientRandomizedAlgorithmforRumorBlockinginOnlineSocialNetworks资源-CSDN文库

研究论文

31 浏览量 2021-02-07 09:21:29 上传评论收藏 375KB PDF 举报

资源推荐

资源详情

资源评论

An Efﬁcient Randomized Algorithm for Rumor

Blocking in Online Social Networks

Guangmo (Amo) Tong

∗

, Weili Wu

†∗¶

, Ling Guo

‡

, Deying Li

‡

, Cong Liu

∗

, Bin Liu

and Ding-Zhu Du

∗

Dept. of Computer Science, University of Texas at Dallas, USA

†

Taiyuan University of Technology, China

‡

Renmin University, China

Ocean University of China, China

Corresponding author

{guangmo.tong, cxl131130, weiliwu, cxl137330, dzdu}@utdallas.edu

{guoling, deyingli}@ruc.edu.cn, binliu@ouc.edu.cn

Abstract—Social networks allow rapid spread of ideas and

innovations while the negative information can also propagate

widely. When the cascades with different opinions reaching the

same user, the cascade arriving ﬁrst is the most likely to be taken

by the user. Therefore, once misinformation or rumor is detected,

a natural containment method is to introduce a positive cascade

competing against the rumor. Given a budget k, the rumor

blocking problem asks for k seed users to trigger the spread of the

positive cascade such that the number of the users who are not

inﬂuenced by rumor can be maximized. The prior works have

shown that the rumor blocking problem can be approximated

within a factor of (1 − 1/e − δ) by a classic greedy algorithm

combined with Monte Carlo simulation with the running time

of O(

mn ln n

), where n and m are the number of users and

edges, respectively. Unfortunately, the Monte-Carlo-simulation-

based methods are extremely time consuming and the existing

algorithms either trade performance guarantees for practical

efﬁciency or vice versa. In this paper, we present a randomized

algorithm which runs in O(

km ln n

) expected time and provides

a (1 − 1/e − δ)-approximation with a high probability. The

experimentally results on both the real-world and synthetic

social networks have shown that the proposed randomized rumor

blocking algorithm is much more efﬁcient than the state-of-the-

art method and it is able to ﬁnd the seed nodes which are effective

in limiting the spread of rumor.

I. INTRODUCTION

The tremendous advance of the Internet of things (loT)

is making the online social networks be the most common

platform for communication. There have been totally 44.5

million users on Twitter and 1.4 million monthly active

users on Facebook. Admittedly the online social networks are

greatly beneﬁcial, they also lead the widespread of negative

information. Such negative inﬂuence, namely misinformation

and rumor, has been a cause of concern as it renders the

network unreliable and may cause further panic in population.

For example, the misinformation of swine ﬂu in Twitter threw

the people in Texas and Kansas into panic in 2009 [1], and

the endless report of Ebola in 2014 has caused unnecessary

worldwide terror. Therefore, effective strategies for rumor

containment are crucial for social networks and it has been

a hot topic in the last decades.

In a social network, information and innovations diffuse

from user to user via inﬂuence cascades where each cascade

starts to spread with a set of seed users. When two cascades

holding opposing views reach a certain user, the user is likely

to trust the cascade arriving ﬁrst. For the example of swine

ﬂu, if the international institutions like WHO would have

posts clariﬁcation for swine ﬂu, the users who have read such

posts will not be inﬂuenced by the misinformation. Therefore,

the most common method for rumor blocking is to generate

a corresponding positive cascade that competes against the

rumor. Due to the expense of deploying seed nodes, there is

a budget k for the positive cascade, and naturally one should

select the k positive seed nodes such that the number of rumor-

activated users is minimized, which is referred as the least cost

rumor blocking problem.

The recent study of inﬂuence diffusion process in social

networks can be tracked back to D. Kempe [2] where the

well-known inﬂuence maximization problem is formulated. In

that seminal work, two fundamental probabilistic operational

models, independent cascade (IC) model and linear threshold

(LT) model are developed. Based on such models, many

inﬂuence related problems are then proposed and studied.

The problem of rumor blocking is also considered in such

models or in their variants. Most existing approaches utilize

the submodularity of the objective function. That is, the

number of non-rumor-activated users is a monotone increasing

submodular function and therefore the classic hill-climbing al-

gorithm provides a (1 − 1/e)-approximation [3]. For example,

X. He et al. [4] formulate the inﬂuence blocking maximization

problem and show a (1−1/e)-approximation algorithm for the

competitive linear threshold model, Budak et al. [5] propose

several competitive models and show a greedy algorithm with

the same approximation ratio under the campaign-oblivious

independent cascade model, and, Fan et al. [6] provide a

(1 − 1/e)-approximation algorithm for the rumor blocking

problem under the opportunistic one-active-one model.

Assuming that the objective function can be efﬁciently

calculated for any input, the greedy algorithm is simple and

effective for most of the submodular maximization problems.

Unfortunately, for the inﬂuence related optimization problems,

Usually this is referred to the polynomial-time computability.

IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

the objective functions are often very complicated to compute

due to the randomness of the probabilistic diffusion model.

Such a scenario is ﬁrst observed by W. Chen [7] where

it is shown that given a seed set computing the expected

inﬂuence is #P-hard. In order to circumvent such difﬁculty, the

prior works employ the Monte-Carlo simulation to calculate

the expected number of non-rumor-activated nodes. However,

such a method is computationally expensive. It turns out

that the greedy algorithm with Monte-Carlo simulation has

the Ω(k · m · n · poly(δ

−1

)) time complexity to achieve a

(1−1/e−δ) approximation ratio, and it takes several days even

for small networks. With the recently analysis of inﬂuence

diffusion [8]–[10], the difﬁculty in solving such problems has

shifted from the nodes selection strategy to the calculation

of the objective function. Fundamentally, it asks for a better

sampling method to estimate the expected inﬂuence given the

seed sets. To the best of our knowledge, there is no rumor

blocking algorithm that can meet practical efﬁciency without

sacriﬁcing performance guarantee.

In this paper, we will show an efﬁcient randomized al-

gorithm for the rumor blocking problem, which is termed

as the reverse-tuple based randomized (RBR) algorithm. The

RBR algorithm runs in O(

k·m·ln n

) in expect and returns a

(1 − 1/e − δ) approximation with a high probability. The

proposed algorithm utilizes the reverse-tuple based sampling

method which is more effective than the Monte-Carlo simula-

tion used in the prior works. The reverse sampling technique is

ﬁrst designed by C. Borgs [8] for the inﬂuence maximization

problem. In this paper, we develop a new type of sampling

based on the concept of reverse-tuple (R-tuple) and show

how such sampling method can be applied to the rumor

blocking problem. Although both the sampling methods give

the unbiased estimate, one set of Monte-Carlo simulations

can only provide an estimation for a speciﬁed seed set while

the samples produced by the reverse-tuple based sampling

can be applied to any seed sets. The RBR algorithm can

be implemented with tunable parameters and it is ﬂexible

for balancing the running time and the error probability. We

experimentally evaluate the proposed algorithm on both the

real-world social network and synthetic power-law networks.

The experimental results show that the RBR algorithm not

only produces high quality positive seed set but also takes

much less time than the greedy algorithm with the Monte-

Carlo simulation does. In particular, when δ = 0.1 and the

error probability is set as less than 1/n where n is the number

of users, the running time of the RBR algorithm is 10 times

less than that of the sate-of-the-art approach. The contribution

of this paper is summarized as follows:

• We design the reverse-tuple based sampling method

which can be used to obtain a unbiased estimate for the

objective function of the rumor blocking problem.

• Based on the new sampling technique, we present the

RBR approximation algorithm which is effective and

efﬁcient for blocking rumors in the IC model.

• We evaluate the proposed algorithm via experiments done

on real-world social networks and synthetic power-law

networks, and show that the RBR algorithm outperforms

the existing methods by a signiﬁcant magnitude in terms

of the running time.

The rest of the paper is organized as follows. Sec. II is

devoted to the related work. The preliminaries are provided

in Sec. III. The new sampling method together with the RBR

algorithm is shown in Sec. IV. The experiments are presented

in Sec. V. In Sec. VI we discuss the future work and conclude.

II. RELATED WORK

In this section we will brieﬂy survey the prior works

regarding rumor controlling.

C. Budak et al. [5] are among the ﬁrst who study the mis-

information containment problem. In particular, they consider

the multi-campaign independent cascade model and investigate

the problem of identifying a subset of individuals that need to

be convinced to adopt the “good” campaign so as to minimize

the number of people that adopt the rumor. X. He et al. [4]

and L. Fan et la. [6] further study this problem under the

competitive linear threshold model and the OPOAO model,

respectively. S. Li et al. [17] later formulate the γ − k rumor

restriction problem and shown a (1 − 1/e)-approximation.

As mentioned earlier, the existing approaches are very time

consuming and thus cannot handle large social networks.

Recently, several heuristic methods have been proposed by

different works, such as [18], [19], while they cannot provide

any performance guarantee. In this paper, we aim to design

the rumor blocking algorithm which is provably effective and

also efﬁcient.

Rumor source detection is another important problem for

rumor controlling. The prior works primarily focus on the

classic susceptible-infected-recovered (SIR) model where the

nodes can be infected by rumor and may recover later. Shah

et al. [15] provide a systematic study and design a rumor

source estimator based upon the concept of rumor centrality. Z.

Wang et al. [16] propose a uniﬁed inference framework based

on the union rumor centrality, and provide explicit detection

performance for degree-regular tree networks.

III. SYSTEM MODEL

In this section, we provide the preliminaries of this paper.

A. Inﬂuence Models

A social network is represented by a directed graph G =

(V, E) where the users are denoted by nodes and edges in

E show the social relationships. For a network G, let E(G)

and V (G) be the edge-set and node-set of G, respectively. In

order to spread an idea or to advertise a new product in a social

network, some seed nodes are chosen to be activated to trigger

the spread of inﬂuence. The diffusion process terminates when

there is no user can be further activated. The two basic

diffusion models are shown as follows.

Linear Threshold (LT) model. Associated with each edge

(u, v) there is an weight w

(u,v)

∈ [0, 1] and each node u

has a threshold θ

, where

(v,u)

≤ 1. For a node u

IEEE INFOCOM 2017 - IEEE Conference on Computer Communications

剩余8页未读，继续阅读

评论收藏

内容反馈

weixin_38609089

粉丝: 5
资源: 924

An Efficient Randomized Algorithm for Rumor Blocking in Online S...

最新资源

An Efficient Randomized Algorithm for Rumor Blocking in Online S...

随机算法 randomized algorithm

An Efficient Privacy-Preserving Algorithm based on Randomized Re

Efficient Coupling Diffusion of Positive and Negative Information in Online Social Networks

Randomized Algorithms for Analysis and Control of Uncertain Systems

Online windowed subsequence matching over probabilistic sequences

PatchMatch: A Randomized Correspondence Algorithm for Structural

A Reliable Randomized Algorithm for the Closest-Pair Problem - 1997 (CP-11.4.1997)-计算机科学

Survey_of_Randomized_Algorithms_for_Training_Neural_Networks.pdf

Social Media Integration and E-commerce Platform Performance

np难问题近似算法(绝版好书)

Random Walk Using Monte-Carlo Randomized Algorithm:Self-Avoiding Random Walk Using Monte-Carlo Randomized Algorithm-matlab开发

基于ssm+mysql的编程类在线答题系统源码数据库论文.docx

Algorithms in C++, Parts 1-4

A novel ensemble pruning algorithm based on randomized greedy selective strategy and ballot

Randomized gradient-free method for multiagent optimization over time-varying networks

primmatlab代码-Randomized_Prim_Algorithm_Experiment:Randomized_Prim_Algor

An Efficient Reliable Communication Scheme in Wireless Sensor Networks Using Linear Network Coding

随机算法 简介

Lectures on Randomized Numerical Linear Algebra

YangX ANM2021 A geometric probability randomized .pdf

Randomized

Computational Geometry in C

【麻省理工大学】算法导论

Attractor networks for shape recognition

c++数据结构与算法实现

算法导论--Introduction.to.Algorithms

Randomized algorithms

最新资源

随机算法简介