Containment of rumor spread by selecting immune nodes in social networks

1.   Introduction

With the popularity of online social networks, such as Facebook, Twitter and Wechat, more and more people are being involved. According to the statics, there have been 2.603 billion and 1.203 billion monthly active users on WeChat and Facebook, respectively ^[1,2]. All kinds of information disseminate through these social networks platforms. This information includes a large number of correct information and positive information, and this kind of information has great value to our life. For example, during the early state of the outbreak of 2019 novel coronavirus disease (COVID-19), the media reported that frequent hand washing, wearing masks and even quarantining themselves at home to avoid contacting with and being infected by others, and these information change people's behavior and mitigate the spread of COVID-19 ^[3]. Besides this correct and useful information, these platforms also spread misinformation even rumors. For example, "two explosions in the White House and Brack Obama is injured", and the news was confirmed to be fake by Associated Press. However, the fake news leads the temporary loss of market cap in S & B 500 to be reached $136.5 billion ^[4]. Therefore, it is a crucial research issue to adopt effective strategies to contain the rumor spread in social networks.

Several recent approaches have studied the problem of containing the rumor spread from different perspectives. These mainly focus on extending the influence diffusion model to include rumor spread and contain the rumor spread under these diffusion models. Specifically, some studies proposed that adopt a positive cascade against the negative influence or rumor ^[5,6]. Another studies showed that blocking links could contain rumor spread ^[7,8]. Other studies showed that removing nodes was an effective strategy for blocking rumor spread ^[9]. (Refer to Section 2 for more details). These studies mainly employed a greedy strategy to select nodes or links to contain rumor spread.

However, it is time consuming to use a greedy strategy to select nodes or links to contain rumor spread even if in a small network. For example, He et al. have verified that the greedy algorithm takes more than 8 hours to finish for a network with 6.4k nodes under the competitive linear threshold model ^[5]. However, we need to swiftly contain rumor spread to avoid its harm before it spreads too far. For example, there is a common rumor that a traditional medicine can act against COVID-19, and so some people start to rush to purchase the medicine, however, this actually has no effect to COVID-19 ^[10]. If we can effectively contain the spread of this rumor, then the public can avoid buying invalid medicine. Therefore, in this paper, we mainly concentrate on efficiently containing the rumor spread in social networks.

Specifically, in this paper, we mainly focus on effectively selecting immune nodes to contain rumor spread under a spread model. Here, the immune nodes include two kinds: those nodes that are influenced by correct information; and those infected nodes which lose interest in a rumor with a certain probability over time. In reality, the susceptible people may be influenced by a rumor, and cheated by this rumor, then become the infective people. However, the infective people may be interested in other things and ignore this rumor with time going on, thus become immune people for this rumor. First, we propose the Extended Independent Cascade (EIC) model to reflect the characteristics, where the EIC model extended from the classic independent cascade (IC) model ^[11]. In the IC model, the node has two states: inactive and active, and each active node u tries to activate its inactive neighbor v with probability p_uv. In our EIC model, the node in the social network has three states: susceptible, infective and immune, where a susceptible node can transform its state into infective, and an infective node can transform the state into being immune. The description of the EIC model's state is similar to the Susceptible-Infected-Susceptible (SIS) model and the Susceptible-Infected-Recovered (SIR) model. However, the SIS model and SIR model assume that every individual directly contacts every other individual and spread the influence in a time unit. These two models are treated as continuous time modes. In our EIC model, the individual transfer its influence with a discrete time step. Further, to effectively select immune nodes, we employ the ENHANCED-(k, η)-CORES (abbreviated to E-(k, η)-CORES) algorithm proposed by Bonchi et al. ^[12] to decompose the social network into dense subetaaphs, where k is the core number of node v, η is a threshold and $(k, \eta )$-CORES is a subetaaph $G'$. In $(k, \eta )$-CORES, the probability of the degree of node v that is greater or equal to k is no less than η. The subetaaphs obtained by this algorithm can reflect well the characteristics of the degree of nodes and the influence spread probabilities among edges. Following this, we compute the number of immune nodes in each (k, η)-CORE based on the number of rumor spreaders and the value of k in each (k, η)-CORE, where the number of immune nodes is positively correlated with these two factors. Finally, we select the set of immune nodes S_k in each (k, η)-CORE based on its number of immune nodes. Evaluating the immune effectiveness in a subetaaph of nodes is # p-hard under the EIC model even when this set is a singleton node ^[13]. Thus, it is necessary to employ a heuristic algorithm to approximately select immune nodes. In this paper, we propose the method of Marginal Covering Neighbors Set to approximately evaluate the immune effectiveness of susceptible nodes, and employ a greedy strategy that iteratively adds nodes based on the number of Maximum Marginal Covering Neighbors Set to the immune set, until $|{S_k}|$ nodes of each (k, η)-CORE are selected.

We compare our algorithms with other popular algorithms using two real-world social networks in the experimentation. Experimental results show that our algorithm is feasible and effective.

The remainder of this paper is organized as follows. In Section 2, we briefly survey the related work. In Section 3, we review the IC model and define the EIC model. In Section 4, we employ the E-(k, η)-CORES decomposition algorithm to obtain subetaaphs and estimate the number of immune nodes in each (k, η)-CORE. In Section 5, we propose an improved greedy algorithm based on Maximum Marginal Covering Neighbors Set to select the immune set in each (k, η)-CORE. In Section 6, we verify the performance of the proposed algorithm via experimentation. In Section 7, we conclude and discuss the future work.

2.   Related work

Kempe et al. first proposed the Linear Threshold (LT) model and IC model to describe the influence diffusion process and formulate the influence maximization problem under these two diffusion models as an optimization problem ^[11]. Then, a greedy algorithm was used to select seeds, where the greedy algorithm can achieve a (1-1/e) approximation guarantee. The LT model and IC model only reflect one idea or opinion spread, and many variants of influence maximization have been proposed ^[7,14,15,16]. In this paper, we mainly focus on efficiently containing rumor spread in a social network. In the following, we summarize the related work of containing rumor spread as three categories.

2.1.   Adopting a positive cascade against negative influences or rumors strategy

In this category, researchers have mainly focused on using positive influences to contain negative influences or rumors. He et al. ^[5] proposed a competitive linear threshold model to describe the process of competitive influence spread, and developed an efficient heuristic competitive local directed acyclic graph algorithm based on the Competitive linear threshold model for the influence blocking maximization problem. Liu et al. ^[6] considered that a participant uses their influence to contain an opponent's influence via the diffusion-containment model. Yang et al. ^[14] proposed a linear threshold model with one direction state transition for modeling competitive influence spread, and proved that the problem of minimizing rumor spread in this model is NP-hard. They further presented three different approximation algorithms to solve the problem of minimizing rumor spreading and highlighted the proximity effect with the proposed algorithm. Guo et al. ^[16] focused on studying the Multi-Feature Rumor Blocking problem, and proposed the Revised-IMM (Influence Maximization via Martingales) algorithm to select a positive seed set to compete with the rumor spread under the Multi-Feature diffusion model. Zhu et al. studies the robust rumor blocking (RRB) problem while the exact positions of rumormongers are unknown. The Reverse Reachable Set was present to estimate the objective function of RRB, and a randomized greedy algorithm for RRB was designed to select k nodes as positive information spreader (called protector) to minimize rumor spread ^[17]. Compared with the following direct methods (Sections 2.2 and 2.3), this category is an indirect method, but it is also an effective method.

2.2.   Removing links to block rumor spread

In this category, researchers have mainly focused on the removal or blockage of an edge set to minimize spread. Specifically, Kimura et al. ^[18] proposed a novel method, on the basis of a greedy algorithm and bond percolation, to minimize contamination by blocking links. Yao et al. proposed a greedy algorithm to select edges as blocking links to minimize the spread of negative influences ^[8]. Yan et al. ^[7] studied the problem of rumor spread minimization by removing an edge set from the network, i.e., finding an edge set $\varepsilon = |k|$ from the candidate edge set $E'$ and removing this from the original graph G. They further proved that the objective function of Rumor Spread Minimization is not submodular, and a heuristic algorithm was used to select edges. Guo et al. presented the targeted protection maximization problem, which blocks the least edges to make the expected ration of nodes in the target set influenced by a rumor at most β. They employed the General-TIM algorithm based on Reverse Shortest Path and the Greedy algorithm were proposed to select edges ^[19].

2.3.   Blocking nodes for minimizing negative influence spread

Some related research has been conducted on blocking nodes to minimize the influence of negative information. Newman et al. ^[9] experimentally verified that removing nodes in decreasing order of the out-degree about the 10% can immune to an epidemic of nodes in a social network. Wang et al. ^[20] employed a greedy algorithm to efficiently find k uninfected users in order to minimize negative information spread.

Comparing the above existing work with the study in this paper, the following aspects can be considered:

●  Methods for influence maximization, that do not consider competitive situations, use the classic LT or IC model to model influence spread and use a greedy algorithm or other heuristic to select seeds.

●  The models for influence containment only consider nodes influenced by positive and negative information. States are changed from inactive to positive or negative, and do not consider that a negative state can transform into a positive state, i.e., a susceptible node can switch its state to infective with probability p_uv at time t, and the infective node can't switch its state to the immune state at time step t₁.

●  Methods for selecting seeds to contain influence spread are always not feasible for containment, as it will take a long time to select an immune node when confronted with a large number of nodes in a social network.

Therefore, in this paper, we propose the EIC model, which can well reflect the characters of rumor spread. The EIC model includes three states (i.e., susceptible, infective, and immune) and the process of state transformation. In addition, we discuss how to effectively select seeds in each (k, η)-CORE of a social network under the EIC model.

3.   Influence spread model

Given an undirected graph G = (V, E, p), where V denotes the node set, $E \subseteq V \times V$ denotes the edge set in a social network, and p: E→(0, 1) is a probability of existence of each edge, we extend the IC model to include rumor characteristics. First, we briefly review the IC model proposed by Kempe et al. and Chen et al ^[11,21]. An uncertain graph can be defined as G = (V, E, p) with S₀, where S₀denotes the node set. A node in G has two states: active and inactive. Let S_t denote the set of active nodes in step t. For every time step t ≥ 1, each newly activated node $u \in {S_t}\backslash {S_{t - 1}}$ tries to activate its inactive out-neighbor v with probability p(u, v), and this attempt is independent from others. If u is successful, then v will switch its state from inactive to active; if not, then u will not try to activate v in subsequent steps. This diffusion process is repeated until there are no newly activated nodes, i.e., ${S_t} = {S_{t - 1}}$.

Yao et al. addressed the minimization of negative influence via blocking links under the IC model ^[8]. In ^[7], under the same model, Yan et al. studied the Rumor Spread Minimization problem through link deletion. These studies suggest that the IC model can be used to model the spread of rumors. However, the IC model can only model a single opinion or idea. In reality, the correct or mistake information may spread in a social network simultaneously. In this paper, to better describe the characteristics of rumors, we extend the IC model to include three states: susceptible, infective, and immune, and the extended model is abbreviated to EIC.

We show the state transformation process of the EIC model in Figure 1. At step t, each node may infect its susceptible out-neighbors with probability p(u, v), where this denotes the infective set at time step t. At step t₁, the rumor disseminator v loses interest in spreading the rumor with probability α, and switches from being an infective state I_v to an immune state ${I_v}'$.

4.   Decomposition of the social network

Kitsak et al. ^[22] employed a k-shell decomposition method to divide a social network into a series of subetaaphs, and found that the most efficient spreaders are the nodes which located within the core of the network. Moreover, Bonchi et al. proposed the (k, η)-CORES algorithm to decompose an uncertain graph ^[12]. Compared with k-shell decomposition, the (k, η)-CORES algorithm not only considers the degree of nodes but also takes into account the probability of edges. In order to improve the efficiency of decomposing (k, η)-CORES, we employ the E-(k, η)-CORES algorithm (Algorithm 1) to decompose a social network, proposed by Bonchi et al. ^[12].

In Algorithm 1, we employ Eq (1) to compute η-deg(v) for each node v.

In Eq (1), η-deg(v) is equal to the maximum k value in all $Pr[deg(v) \geqslant k]$. To obtain the value of η-deg(v), we next need to consider how to compute Pr[deg(v) ≥ k], which is equal to the sum of the probabilities Pr[deg(v) = i] for all i∈[k, d_v] as shown in Eq (2).

where Pr[deg(v) = i] denotes the probability that the degree of node v is equal to i, that is,

Here, N_v denotes the adjacent edge set of node v and ${N_v}' \subseteq {N_v}$. We respectively set $|{N_v}| = m'$ and $|{N_v}' | = i$. There are $C_{m'}^i$ cases when we select i edges from m' edges, and the computation of $C_{m'}^i$ is shown in Eq (4):

The computation of η-deg(v) as described in Eq (1) is time consuming. To improve the speed of computation, we employ a lower bound on the η-degree, which is proposed by ^[12] and described as follows.

Weisstein et al. ^[23] defined the regularized beta function I_z(a, b) as the ratio of the incomplete beta function B(z; a, b) and the beta function B(a, b):

Given a node v, the minimum probability among edges incident to v is found, and set ${p_{min}}(v) = mi{n_{e \in {N_v}}}{p_e}$. Based on Eqs (2), (3) and (5), Eq (6) holds, and the detail of the proof can be found in ^[12].

Adding Eq (5) into Eq (6), we obtain

Equation (7) can avoid the combinatorial computation of Eq (4). If the right part of inequality Eq (7) from k to d_v is greater than or equal to the given η then this satisfies $Pr(deg(v) \geqslant k) \geqslant \eta$. Based on Eqs (1) and (7), we can obtain the initial η-degree of all nodes.

In Figure 2 we give an example to illustrate the execution of Algorithm 1. The probabilities on the edges are as follows: p₁₂ = 0.5, p₁₄ = 0.6, p₁₅ = 0.8, p₂₅ = 0.6, p₂₄ = 0.4, p₄₅ = 0.5, p₂₃ = 0.3, p₄₆ = 0.3, p₅₆ = 0.4, p₆₇ = 0.9, p₆₈ = 0.5, and p₇₈ = 0.4, and we suppose η = 0.05.

Take v₂ as an example, the minimum probability value of the edge adjacent to v₂ is p_min(v₁) = 0.3. According to Eq (7), we have:

Thus, we obtain η-deg(v₂) = 3. Similarly, we can compute η-deg(v) of another node v in this simple social network, as shown in Table 1.

Now, we store the node v with η-deg(v) = i in set C[i], i.e., $C[1] = \{ {v_3}\}$, $C[2] = \{ {v_7}, {v_8}\}$, and $C[3] = \{ {v_1}, {v_2}, {v_4}, {v_5}, {v_6}\}$. We further put these sets $C[1]$, C[2] and C[3] into set $C$, i.e., $C = \{ C[1], C[2], C[3]\}$. After initialization, we compute the (k, η)-CORES of each node v in the social network. First, we cyclically select node v from C[i] in order of i from small to large, and assign the (k, η) value of node v as η-deg(v). Then, we compare η-deg(u) with η-deg(v), where u is the adjacent node of v. If η-deg(u) ≤ η-deg(v), then we do not need to recompute $\eta {\rm{ - }}de{g_{G'}}(u)$. Otherwise, we need to further calculate $\eta {\rm{ - }}de{g_{G'}}(u)$ value after removing the edge e(u, v). If Eq (1) holds, then we do not update $\eta {\rm{ - }}de{g_{G'}}(u)$. Otherwise, $\eta {\rm{ - }}de{g_{G'}}(u) = \eta {\rm{ - }}de{g_G}(u) - 1$.

In Figure 2, we first select v₃ from C[1] and assign its (k, η)-CORE value as 1. Since η-deg(v₂) = 3 > η-deg(v₃) = 1, we further employ Eq (7) to compute the value of $Pr(de{g_{G'}}({v_2}) \geqslant 3)$ after removing edge e(v₁, v₂), and we have $Pr(de{g_{G'}}({v_2}) \geqslant 3) = 0.064 > 0.05$, therefore, $\eta {\rm{ - }}de{g_{G'}}({v_2}) = 3$. Similarly, we can obtain the (k, η)-CORE values of other nodes in Figure 2 as shown in Table 2.

Based on the (k, η)-CORE value of each node v, we can obtain the (k, η)-CORES decomposition of the graph G, i.e., $(1, \;0.05) = \{ {v_3}\}$, $(2, 0.05) = \{ {v_6}, {v_7}, {v_8}\}$ and $(3, 0.05) = \{ {v_1}, {v_2}, {v_4}, {v_5}\}$. We next study how to select the set of immune nodes in (k, η)-CORE.

5.   Selecting the set of immune nodes for each (k, η)-CORE

Selecting a set of immune nodes in social networks is time consuming. Thus, how to effectively select a set of immune nodes is an important research issue in this domain. In Section 4, the social network was decomposed into a serious of subetaaphs, i.e., (k, η)-CORES, and we will focus on selecting the set of immune nodes of each (k, η)-CORE in this Section. Before selecting the set of immune nodes in each (k, η)-CORE, we first need to compute the number of immune nodes of each (k, η)-CORE. Then, we iteratively select the immune node of each (k, η)-CORE based on the number of immune nodes until |S_k| nodes are selected.

5.1.   Computation of the number of immune nodes in each (k, η)-CORE

The number of immune nodes is influenced by two factors: the number of rumor nodes set and the value of k in each (k, η)-CORE. Obviously, the larger the number of rumor nodes set in (k, η)-CORE, the more the number of immune nodes. Following this, we first give Eq (8) to describe the ratio of rumor nodes set in (k, η)-CORE:

In Eq (8), $N(S_k^B)$, $N({G_k})$, and $\alpha _k^B$ denote the number of rumor nodes set, the number of nodes, and the ratio of rumor nodes in (k, η)-CORE, respectively.

The (k, η)-CORE of a node v can reflect its ability to spread its influence. Therefore, the larger the (k, η)-CORE value, the more easily this node will spread its influence. Accordingly, the larger the (k, η)-CORE value, the more immune nodes will be selected. Following this, we give Eq (9) to compute the ratio of rumor nodes based on the value of (k, η) and the ratio of the rumor node set $\alpha _k^B$.

Finally, we obtain the number of immune nodes in each (k, η)-CORE based on Eq (9), that is

In Eq (10), $|{I_A}|$ and $|I_A^k|$ denote the number of immune nodes of social network G and (k, η)-CORE respectively.

We next study how to select the set of immune nodes of each (k, η)-CORE based on the number of immune nodes.

5.2.   Selection of the set of immune nodes in each (k, η)-CORE

In Section 3, we have described the EIC model for the rumor propagation process. In this Section, we mainly focus on selecting the set of immune nodes of each (k, η)-CORE to maximally contain a rumor under the EIC model.

Kitsak et al. ^[22] found that the most efficient spreaders are located in the larger k-shell, and pointed out that nodes in the same core affect the nodes in the similar areas. Similarly, a node in the same (k, η)-CORE will also produce similar spread areas, i.e., v₁, v₂, v₄, and v₅ of (3, 0.05)-core in Figure 2 have similar spread areas. Cao et al. ^[24] proposed the Core Covering Algorithm based on k-shell decomposition to maximize the influence spread. In contrast to their work, the objective of this paper is to maximally contain rumor spread. Thus, we need to consider the characteristics of rumor spread and cannot directly select the nodes of the larger (k, η)-CORE or employ the Core Covering Algorithm to select the set of immune nodes.

Considering the characteristics of rumor spread, we have proposed an EIC model to describe the rumor spread process previously in this paper. Next, we consider how to select the set of immune nodes in each (k, η)-CORE in the EIC model. With this view, we can make use of the Degree-Discount algorithm proposed by Chen as this algorithm nearly matches the greedy algorithm for the IC model ^[13]. The idea behind the Degree-Discount algorithm is as follows: Let node v be a neighbor of node u. If node u has been selected as a seed, then the degree of v should be discounted. Combining the idea of Cao et al. ^[24] and Chen et al. ^[13], we propose a method that uses Maximum Marginal Covering Neighbors Set as the seed selection rule. Specifically, let S_k and I_B be the set of immune nodes and rumor nodes, respectively; we can describe the marginal gain of v newly added to the set S_k as shown in Figure 3.

In Figure 3, let ${W_1}$, ${W_2}$ and ${W_3}$ be the t-step neighbor set of ${S_k} \cup \{ v\} , {S_k}$ and ${I_B}$. The marginal gain of immune node v is the diagonal part, which can be formally described as in Eq (11).

The set of immune nodes S_k and rumor nodes I_B may influence the same neighbors, thus the influence will counteract. At the same time, the immune node set S_k and S_k ∪{v} will also influence the same neighbors, and thus the influence will overlap. Therefore, we introduce the discount factor p, and let the counteracted part and overlap be multiplied by this discount factor p, that is

Selecting the optimal set of immune nodes is NP-hard. The objective function $\sigma ({S_k}, {I_B})$ is monotone and submodular in the EIC model, and the details of the proof are omitted here. Therefore, we employ a greedy algorithm to approximately select the set of immune nodes based on the theory in ^[25]. We next provide Algorithm 2 to describe how to select the set of immune nodes for each (k, η)-CORE. In this algorithm, we iteratively select the current best immune node u from V − I_B in each (k, η)-CORE based on Maximum Marginal Covering Neighbors Set, which can maximally contain the rumor spread of (k, η)-CORE added into the immune set S_k starting from an empty set, until |S_k| seeds are selected.

According to the conclusion in ^[25], Algorithm 2 can approximate the optimal result with (1-1/e) for the problem of containing rumor spread. Step 2 is a critical step of Algorithm 2, and the time complexity of Algorithm 2 is $O(|{S_k}| \times |{V_k}| \times t)$, where |S_k|, |V_k|, and t are the number of immune nodes, the number of nodes, and the time step, respectively.

5.3.   Evaluating the immune effectiveness of S_k

We have obtained the set of immune nodes S_k in Section 5.2. Following this, we evaluate rumor spread value Q of immune node set S_k in the EIC model in T steps, i.e., we calculate the influence effectiveness of I_B when the set of immune nodes S_k exists. We have:

For this purpose, we need to calculate the value of AP_T(v), i.e., the node v (i.e., $v \in {G_k}\backslash {S_k} \cup {I_B}$ $v \in {G_k}\backslash {S_k} \cup {I_B}$) influenced by I_B in T steps when the immune node set S_k exists. This can be defined as

In Eq (14), ${\eta _t}$ denotes the immune coefficient. In the EIC model, the rumor disseminator will become an immune node with probability α in time step t₁. Therefore, we have:

In Eq (14), ap_t(v) denotes the influence effectiveness of I_B at time step t when the immune node set S_k exists, and can be described as in Eq (16).

6.   Experiments

In this section, we conduct experiments using two real-world datasets to test and evaluate the performance of the algorithms. We first give a description of each dataset and the experimental setup. Then, we analyze and discuss the experimental results.

6.1.   Experimental setup

Gnutella peer-to-peer network: This dataset is a sequence of snapshots of the Gnutella peer-to-peer file sharing network from August 2002. In this network, nodes represent hosts in the Gnutella network topology and edges represent connections between the Gnutella hosts. There are 10,876 nodes and 39,994 edges ^[26].

Arxiv HEP-TH (High Energy Physics-Theory) collaboration network: This dataset is from the e-print arXiv and covers scientific collaborations between authors's papers submitted to the high energy physics theory category. There are 9877 nodes and 25,998 edges. Each node u in the network represents an author, and each edge e(u, v) denotes that an author u coauthored a paper with author v ^[27].

The experiments were conducted on a machine with an Intel Core i7-8550 CPU and 8 GB main memory running the Windows 10 operating system. The code was written in Python.

In all experiments, we adopt the EIC model as the influence propagation model. In addition, since all datasets lack a propagation probability, we uniformly assign the propagation probability of each edge in the range [0.1, 0.9] at random.

6.2.   Experimental results

In the experiments, we compare the value of the rumor spread value Q obtained with the greedy algorithm based on the Maximum Marginal Covering Nerighbors Set (i.e., the greedy algorithm), the Degree Discount algorithm (the degree discount heuristic algorithm), MaxDegree algorithm (selecting seeds with the largest degree) and the Random algorithm (selecting seeds randomly). Next, we show relationships between Algorithm 2 and parameters. Further, we give the running times of the different algorithm. Finally, we compare the rumor spread value with Greedy algorithm (i.e., Algorithm2) under k-core decomposition and (k, η) decomposition methods.

6.2.1.   Rumor spread value vs. four different algorithms

For the Gnutella peer-to-peer network and the Arxiv HEP-TH collaboration network, we first recorded the rumor spread value Q when selecting the set of immune nodes with Greedy (Algorithm2), DegreeDiscount, MaxDegree, and Random, respectively, with the increase of immune seeds, where we assigned η = 0.01, t = 3, t₁ = 2, α = 0.7, and p = 0.5. The number of rumor disseminators |I_B| in Figure 4(a), (b) are 37 and 20, respectively. The results of comparisons are shown in Figure 4. It can be seen that with more immune seeds, the effectiveness improves. The rumor spread value Q for Greedy is better than for the Maxdegree, DegreeDiscount and Random algorithms for most immune seeds. This result means that Greedy algorithm proposed in this paper is effective.

6.2.2.   Rumor spread value with greedy algorithm vs. different parameters

Firstly, we tested the rumor spread value by Algorithm 2 with η = 0.001, η = 0.005, and η = 0.01, respectively. In this experiment, we set t = 3, t₁ = 2, α = 0.7, and p = 0.5, and the number of rumors spread |I_B| in Figure 5(a), 5(b) are 37 and 20, respectively. The results are shown in Figure 5. It can be seen that different η will have a different immune effectiveness Q w.r.t. the same number of immune nodes for the Gnutella peer-to-peer network and the Arxiv HEP-TH collaboration network. This means that the immune effectiveness of Q is related to the value of η. This is because different η will generate different subetaaphs. Accordingly, the set of immune nodes generated by these subetaaphs will be different, and these immune nodes will lead to different values of immune effectiveness Q, which are consistent with intuition and real world situations.

Secondly, we compared the value of rumor spread value Q with the increase of immune seeds for the two networks with α = 0.3, α = 0.5, and α = 0.7, respectively, where we set η = 0.01, t = 3, t₁ = 2, and p = 0.5. In addition, the number of rumor spreaders in the Gnutella peer-to-peer network and the Arxiv HEP-TH collaboration networks are 15 and 20, respectively. The comparisons are shown in Figure 6. It can be seen that the larger the transition probability α, the better the value of the immune effectiveness Q (i.e., the better containment effectiveness) will be. This is because a larger transition probability α will make more nodes change their state from disseminator to immune.

Finally, we test the value of immune effectiveness Q for time steps t = 2, t = 3, and t = 4 with the increase of immune seeds, where we assigned η = 0.005, t₁ = 2, and p = 0.5. In Figure 7(a), we assigned |I_B| = 5 and α = 0.2, and in Figure 7(b), |I_B| = 7 and α = 0.7. Figure 7 shows that the rumor spread value Q will increase as the time steps increase when the number of immune nodes is the same, and the trend of change will be stable. This is because the propagation of rumors will increase with the increase of time steps.

6.2.3.   The running times with greedy algorithm vs. other algorithms

Table 3 shows the running times of the different algorithms for selecting $|{S_k}| = 30$ immune nodes in the Gnutella peer-to-peer network and Arxiv HEP-TH collaboration network. In these two networks, the Greedy algorithm proposed in this paper only takes 61.78 seconds and 4.48 seconds respectively. Compared with the original greedy algorithm, which takes several hours to select seeds in the 6.4k network ^[5], the greedy algorithm proposed in our paper is very effective.

6.2.4.   Rumor spread value with greedy algorithm vs. different methods of decomposition social network

For the Arxiv HEP-TH collaboration network, we compared the rumor spread value Q of Greedy algorithm with k-decomposition and (k, η)-decomposition, respectively, with the increase of immune seeds, where we assigned η = 0.01, t = 3, t₁ = 2, α = 0.7 and $p = 0.5$. In addition, the number of rumor spreads is 15 and 20 respectively. The results of comparisons are shown in Table 4. It can be seen that the rumor spread value Q of with (k, η)-decomposition outperforms k-decomposition. This result means that (k, η)-decomposition employed in this paper is effective.

7.   Conclusions and future work

With the goal of effectively selecting immune nodes to contain the spread of rumors, we employ the E-(k, η)-CORES algorithm to decompose a social network. Moreover, we extend the IC model to establish the EIC model by incorporating the specialties and characteristics of rumor spread. Further, we propose a greedy algorithm based on Maximum Marginal Covering Neighbors Set to select the set of immune nodes for containing rumor spread.

The E-(k, η)-CORE algorithm, EIC model, and the greedy algorithm strategy for containing rumor spread proposed in this paper can provide underlying techniques to handle rumor spread and negative information spread. However, containing rumor spread in large-scale social networks is still time consuming. For future work, we plan to implement these methods on a big data processing platform. Moreover, we still need to further study the relationships among relevant parameters.

Acknowledgments

This work was supported by the Yunnan Province Joint Youth Program Foundation of Local Colleges and Universities (No. 2017FH001-116), the Open Foundation of Key Laboratory for the Structure and Evolution of Celestial Objects, Chinese Academy of Sciences (No. OP201710), the School Level Excellent Course of Qujing Normal University (JPKC 2016005), the Research Foundation of Educational Department of Yunnan Province (No. 2017ZZX133), and the Project on the Humanities and Social Sciences Research of Ministry of Chinese Education (No. 18XJC880012)

Conflicts of interest

The authors declare no conflict of interest.