Dynamic selection of clarification channels in rumor propagation containment

1.   Introduction

Rumors refer to spontaneously formed false stories ^[1]. Benefiting from the wide audience coverage and fast information circulation of social media, rumors can quickly propagate over a social network and compromise a large number of individuals in a short time ^[2]. If rumor spreading is out of control, severe consequences would occur ^[3,4]. Hence, it is of significance to curb rumor propagation ^[5].

Rumor clarification, which means revealing the erroneous aspects of rumors with facts, is one of the most commonly used ways to curb rumor propagation ^[6]. Generally, the process of rumor clarification consists of the following three steps. First, after rumors have emerged and spread over a social network, the victim of rumors may have a group of righteous journalists (or its public relations department) collect evidence about the facts and write rebuttal reports against the rumors. Second, the victim needs to select a set of media channels (including but not limited to online social media, television programs, short messages and offline face-to-face campaigns) to publish the rebuttal reports. Third, after a certain period of time, the victim may need to re-select the media channels to achieve better results—namely, if most of the audiences of an in-used media channel have acquired the truth, the victim may deactivate this channel and activate other unused channels to make more individuals know the truth. This step can be iteratively performed until everyone on the social network knows the truth. A diagram illustrating the above three steps is shown in Figure 1.

1.1.   Motivations and problem statement

In this paper, we focus on the last two steps of rumor clarification, in which the victim needs to periodically determine which media channels to activate or deactivate so as to expand the ultimate influence of rumor clarification. The victim's decision can be affected by two essential factors: efficiency and cost. On the one hand, the victim has to estimate the efficiency of different combinations of media channels. Research shows that media channels may have different information diffusion efficiency due to the differences in user types, audience ratings and other aspects ^[7,8,9,10]. Thus, releasing the same rebuttal report through different media channels may result in different effects. On the other hand, the victim needs to consider the costs of different combinations of media channels. As media channels can have different pricing manners for their information exposure services ^[11], the monetary expenditure of publishing the same rebuttal report can vary from media channel to media channel. Hence, provided that the total budget for rumor clarification is limited and fixed, the victim must consider the costs of different channels.

Considering the above two aspects, we formulate the following issue:

Dynamic Channel Selection (DCS) problem: Consider a process of multiple periods. Under a fixed total budget, how should the victim select proper media channels at each period to publish rebuttal reports, so as to maximize the efficiency (i.e., make as many individuals as possible know the truth) with the lowest actual expenditure?

For writing simplicity, we refer to any solution to the DCS problem as a DCS strategy.

Next, let us analyze the challenges in addressing the DCS problem. In order to find the optimal DCS strategy, the victim must carefully calculate the overall trade-offs of different combinations of media channels in terms of their efficiency and costs. Normally, pricing manners of media channels are open and transparent, so the cost of using any media channel can be calculated easily. However, estimating the collaborative efficiency of multiple media channels is not a low-hanging fruit but the key challenge. Two reasons are as follows. First, because there exists the Word-of-Mouth phenomenon ^[12] in the process of information diffusion, it is indispensable to microscopically understand how multiple media channels will interact with each other during rumor clarification, which is very complex. Second, as we are considering a multi-period process, we must meticulously determine the timing of choosing a media channel, which is also complicated. In fact, choosing a certain media channel too early or too late may reduce the ultimate efficiency of rumor clarification, and more importantly, the choices in the previous periods may affect the subsequent periods. Therefore, it will take much effort to address the DCS problem. Unfortunately, as far as we know, there is no research on solving the DCS problem. So, our work is of novelty.

1.2.   Contributions

Recall that this paper is devoted to addressing the DCS problem. The contributions are as follows.

● We reduce the DCS problem to a mathematical optimization model. First, we propose a rumor propagation model to estimate the effects of different DCS strategies on controlling rumor propagation. Second, with the proposed rumor propagation model, we quantify the trade-offs of different DCS strategies in terms of their efficiency and costs. Third, we formulate an optimization model called the DCS model to describe the DCS problem from a mathematical perspective, with the trade-off model as the objective function and the propagation model as a constraint condition.

● Based on the genetic algorithm framework ^[13], we develop a numerical method called the DCS algorithm to solve the DCS model. Specifically, we first discuss the designs of the initialization, fitness evaluation, crossover, mutation and repair operators of the genetic algorithm framework, and then provide a pseudo code and an overall flow chart for the DCS algorithm.

● We conduct a series of numerical experiments to verify the performance of the DCS algorithm. First, with a rumor dataset, we estimate the parameter values involved in the proposed rumor propagation model to reconstruct a historical rumor event. Second, we investigate the optimal setting of the DCS algorithm and then explore the contribution degree of each operator of the DCS algorithm. Third, by comparing the DCS algorithm with the Monte Carlo method ^[14], we validate the effectiveness of the DCS algorithm. Finally, we examine how the obtained optimal strategy can restrain rumor propagation. Results show that the DCS algorithm can efficiently yield a satisfactory DCS strategy.

The remainder of this paper is organized by the following manner. Section 2 reviews the related work and highlights our novelty. Section 3 discusses the mathematical modeling of the DCS problem. Section 4 shows the solution. Section 5 performs massive numerical experiments. Section 6 closes this paper.

2.   Related works

In this section, we review the related work and highlight the novelty of our work. First, we briefly introduce the recent research on rumor propagation models. Second, we discuss the existing research on developing rumor clarification strategies.

2.1.   Rumor propagation models

Rumors refer to spontaneously formed false stories. In order to develop effective anti-rumor countermeasures, it is necessary to first understand the spread process of rumors at a micro level. Normally, mathematical models used to characterize rumor spreading are referred to as rumor propagation models.

Because there are essential similarities between rumors and biological viruses in their infective behaviors, rumor propagation models are generally developed based on the epidemic theory ^[15], which is primarily used to comprehend the spread process of contagion. Epidemic-based rumor propagation models can be population-level or individual-level. Population-level models (e.g., ^[16,17]) first classify individuals into several groups according to their stances toward rumors, and then capture the population evolution of each group with a dynamic system. In this type of model, there is a basic assumption that individuals on a social network can be considered completely consistent. However, as social networks are assumed to be homogeneously mixed, population-level models cannot well characterize the interactions between individuals and thus are not accurate enough.

To enhance the accuracy, individual-level models (e.g., ^[18,19]) take into account the topological structures of social networks and regard every individual as an independent entity. Based on this characteristic, researchers can perform fine-grained simulations on social networks to predict the trend of rumor propagation. Particularly, there are some outstanding individual-level models developed based on machine learning and game theory. In ^[20], a rumor propagation model is proposed based on data enhancement and evolutionary game. In ^[21], a game-based rumor diffusion model is designed inspired by image restoration. ^[22] proposes an information dissemination model to predict the influences of rumors, anti-rumors, and stimulate-rumors by considering their interactions. Because individual-level models can characterize any type of social networks, individual-level models are generally considered more accurate and universal than population-level models.

Unfortunately, as far as we know, there exists no individual-level model on characterizing the interactions between multiple media channels. In this paper, we fill this research gap.

2.2.   Rumor clarification strategies

Clarifying the truth to the public has been considered one of the most efficient approaches to rumor propagation containment. In recent years, how to develop cost-effective clarification strategies has attracted much attention from academic communities. In terms of the number of media channels exploited for releasing anti-rumor messages, existing clarification strategies can be classified into two categories: single-channel clarification strategies and multi-channel clarification strategies.

Single-channel clarification strategies are those with which the truth is released through only one (or one type of) social media channel, which is generally represented by Twitter or Facebook. Research of single-channel clarification strategies has not considered the impact of exploiting multiple media channels, or believe that all types of media channels (including but not limited to online social platforms, television programs and face-to-face interactions) can be abstractedly combined to be a sole "global" entity, through which all individuals in society can be directly affected by anti-rumor messages. Accordingly, instead of characterizing the differentiation of various media channels, studies on single-channel clarification strategies focus more on optimizing the rate at which anti-rumor messages are published through the only channel. See ^{[23,24,25,26,27,28]} for some typical works.

However, single-channel models cannot well characterize the real-world process of rumor clarification. The primary reason is that in reality there does not exist such a perfect global media channel which can completely cover all individuals worldwide. Even the most popular media channel at present, i.e., online social platforms, just has a usage ratio of no more than 57% ^[29]. Hence, single-channel clarification strategies are relatively not comprehensive.

In order to make up for the deficiency of single-channel models in depicting the real world, research of multi-channel strategies is devoted to consider the influences of various media channels. In multi-channel rumor propagation models, each channel has its own attributes of information diffusion, such as the forwarding rate of messages, the coverage range of audience and so on ^[30]. In this context, research on multi-channel clarification focuses more on addressing the so-called rumor influence minimization problem, that is, to select proper clarification channels to accelerate and expand the spreading of anti-rumor information in competition with rumors. See ^{[31,32,33,34,35,36]} for typical literature.

Unfortunately, in the existing works on solving the rumor influence minimization problem, strategies are generally assumed to be static over time. That is, in their mathematical models, the selection of clarification channels is considered a one-off act which happens only at the initial stage. However, this assumption makes the obtained clarification strategies not flexible enough in reality, because clarification channels cannot be re-selected dynamically over time according to the latest situation of rumor propagation. Therefore, it is valuable to consider multi-stage channel selection problems and develop corresponding dynamic strategies.

In this paper, we are devoted to filling the above-mentioned research gap by studying the dynamic selection strategies for clarification channels. As far as we know, this is the first time to make such an attempt.

3.   Problem formulation

This section discusses the mathematical modeling of the DCS problem. First, we introduce a set of terms and notations to formalize DCS strategies with a mathematical expression. Second, we propose a rumor propagation model to describe the influences of DCS strategies on rumor containment. Third, with the propagation model, we establish a trade-off model to evaluate different DCS strategies and, on this basis, formulate a mathematical optimization problem to describe the DCS problem, with DCS strategies as the decision variable, the trade-off model as the objective function and the rumor propagation model as a constraint condition.

3.1.   Terms and notations

Let us begin by the formalization of DCS strategies. Consider a social network of $N$ individuals. Denote the set of them by $V^I = \{v^I_1, \dots, v^I_N\}$. For a pair of individuals $v^I_i$ and $v^I_j$, let $a_{ji} = 1$ if and only if $v^I_i$ is a social follower of $v^I_j$; otherwise, $a_{ji} = 0$. Particularly, let $a_{ii} = 0$ for all $i$. Let ${\bf a} = [a_{ij}]_{N\times N}$. Suppose there are $M$ media channels on the network. Let $V^C = \{v^C_1, \dots, v^C_M\}$ denote the set of them. If the individual $v^I_i$ can be directly affected by the channel $v^C_j$, denote $b_{ij} = 1$; otherwise, $b_{ij} = 0$. Let ${\bf b} = [b_{ij}]_{N\times M}$ denote the relationship matrix between individuals and media channels.

Suppose when refuting rumors, media channels can be periodically activated or deactivated to publish anti-rumor information on the social network. Let $\tau$ be the time interval between any two times of channel selection. Each time interval $t_k = [(k-1)\tau, k\tau)$ is called a stage, where $k = 1, \dots, K$ and $K$ is the maximum number of stages. Denote a binary matrix ${\bf x} = [x_{kj}]_{K\times M}$ such that $x_{kj} = 1$ if and only if the channel $v^C_j$ is activated at the stage $t_k$; otherwise, $x_{kj} = 0$. In this paper, the matrix ${\bf x}$ is referred to as the DCS strategy.

Any available DCS strategy should be limited within a pair of upper and lower bounds. In practice, we must take into account the total expenditure of using media channels to clarify the truth. Denote $c_j$ as the average cost of using the channel $v^C_j$ at one stage. Let ${\bf c} = (c_1, \dots, c_M)$. Denote $B$ as the total budget. Because the total expenditure must be lower than the total budget, it holds that $\sum_{k = 1}^{K}\sum_{j = 1}^{M} c_j x_{kj} \le B$. Hence, the feasible set of DCS strategies is

3.2.   Rumor propagation model

Having defined the feasible set $X$ in (3.1) for DCS strategies, we now need to establish a quantitative model to evaluate the influences of different DCS strategies so that we can have a criterion to select the best DCS strategy from the feasible set $X$.

Intuitively, the performance of a rumor-containment strategy can be represented by the evolution of individuals' stances toward rumors—the better the strategy, the more people oppose rumors. Hence, if we intend to evaluate the influence of a strategy, we may need first to predict how individuals' stances will evolve under that strategy. In the following, we use a rumor propagation model to capture the effect of a DCS strategy on the changes in individuals' stances.

Establishing a rumor propagation model requires the following three steps ^[37]: (a) specifying all possible individual stances to rumors; (b) introducing assumptions for all possible stance transitions; (c) formulating a differential dynamic system that characterizes the evolution of individuals' stances. Below, we discuss these three steps.

First, we specify all possible individual stances to rumors. Suppose each individual can have three possible stances to rumors: supportive, opposed and judgment-reserved, which indicate the individual agrees, disagrees and neither agrees nor disagrees with existing rumors, respectively. In this paper, we assume that individual stances are time-varying stochastic variables. Denote $S_i(t)$, $O_i(t)$ and $J_i(t)$ as the probabilities with which the individual $v^I_i$ holds the supportive, opposed and judgment-reserved stances at time $t$, respectively. Then, the function $P_i(t) = (S_i(t), O_i(t), J_i(t))$ defined on time $t\ge 0$ is called the stance probability distribution function of the individual $v^I_i$.

Second, we introduce the following notations to estimate the evolution of stance probability distribution functions:

● $\alpha$: the average rate at which a judgment-reserved individual becomes rumor-opposed due to the persuasion of a rumor-opposed social friend.

● $\beta$: the average rate at which a judgment-reserved individual becomes rumor-supportive due to the persuasion of a rumor-supportive social friend.

● $\gamma$: the average rate at which a rumor-supportive individual becomes rumor-opposed due to the persuasion of a rumor-opposed social friend.

● $\delta_i$: the average rate at which a judgment-reserved or rumor-supportive individual becomes rumor-opposed due to the rumor clarification from the channel $v^C_i$. Let $\boldsymbol{\delta} = (\delta_1, \dots, \delta_M)$.

Besides, we introduce the following three assumptions, which have been widely adopted in other individual-level rumor propagation models (e.g., ^{[34,38,39,40,41]}).

● The overall influence of the persuasion from multiple social friends on a person's stance can be linearly accumulated by the influence of each friend.

● The overall influence of the clarification from multiple media channels on a person's stance can be linearly accumulated by the influence of each channel.

● The overall influence of the persuasion from social friends and clarification from media channels on a person's stance can be linearly accumulative.

Then, combining the above notations and assumptions, we formulate a differential dynamic system, which is given in Theorem 1, to capture the influence of a DCS strategy on stance probability distribution functions $P_i(t)$, $i = 1, \dots, N$. This result is obtained by directly applying the epidemic theory (see ^[37] for an introduction to the epidemic theory).

Theorem 1. Given the initial values $P_i(0) = P^0_i$, $i = 1, \dots, N$, stance probability distribution functions $P_i(t)$, $i = 1, \dots, N$, $t\ge 0$, can be characterized by the dynamic system (3.2).

where

Proof. According to the individual-level epidemic theory (see ^[37] for a basic introduction and ^[34,38,39] for some representative applications), the evolution of stance probability distribution can be modeled as a continuous-time Markov process. Hence, we derive the dynamic system (3.2) from the perspective of constructing a Markov process.

First, we calculate the transition rates among all individual stances. Based on the assumptions introduced earlier, the following three transition rates can be obtained: (a) at any time $t$, the total transition rate at which a judgment-reserved individual $v^I_i$ becomes rumor-opposed is $\lambda^{JO}_i(t) = \alpha \sum_{j = 1}^{N} a_{ij} O_j(t) + \sum_{j = 1}^{M} b_{ij}\delta_j u_j(t)$; (b) at any time $t$, the total transition rate at which a judgment-reserved individual $v^I_i$ becomes rumor-supportive is $\lambda_i^{JS}(t) = \beta \sum_{j = 1}^{N} a_{ij} S_j(t)$; (c) at any time $t$, the total transition rate at which a rumor-supportive individual $v^I_i$ becomes rumor-opposed is $\lambda_i^{SO}(t) = \gamma \sum_{j = 1}^{N} a_{ij} O_j(t) + \sum_{j = 1}^{M} b_{ij} \delta_j u_j(t)$.

Second, given a very small time interval $\Delta t$, we calculate the stance probability distribution at time $t+\Delta t$ for any time $t$ and for any individual $i$. Let $R_i(t) = R_J$, $R_i(t) = R_S$ and $R_i(t) = R_O$ denote the events that the individual $v^I_i$ holds the judgment-reserved, rumor-supportive and rumor-opposed stances at time $t$, respectively. Then, according to the definition of conditional probabilities, the three total transition rates obtained from the first step can yield the following transition probabilities

According to Total Probability Formula, for all $i = 1, \dots, N$ and $t\ge 0$, the following results can be derived:

Third, based on the first two steps, we derive a dynamic system for stance probability distribution functions. By the definition of differential equations, there are

for all $i = 1, \dots, N$ and $t\ge 0$. By direct calculation, the dynamic system (3.2) is obtained. The proof is completed. □

The dynamic system (3.2) is an individual-level rumor propagation model, based on which we can predict the stance probability distribution for all time and individuals and further quantify the efficiency of different DCS strategies. A diagram of possible stance transitions is shown in Figure 2.

3.3.   Mathematical modeling of the DCS problem

Next, we need to establish a criterion to evaluate different DCS strategies. With respect to a given DCS strategy, a proper criterion must calculate the overall trade-off between the total expenditure of conducting this strategy and the efficiency of this strategy in curbing rumor propagation. Let us discuss these two aspects. First, by definition, the total expenditure of the strategy ${\bf x}$ is calculated as $y_1({\bf x}) = \sum_{k = 1}^{K} \sum_{j = 1}^{M} c_j x_{kj}$. Second, as the goal of rumor clarification is to increase rumor-opposed individuals as many as possible, the effectiveness of the strategy ${\bf x}$ is represented by the expected number of increased rumor-opposed individuals during rumor clarification, that is, $y_2({\bf x}) = \sum_{i = 1}^{N} O_i(K\tau) - \sum_{i = 1}^{N} O_i(0)$. Then, combining the above two aspects, the cost-effectiveness of the strategy ${\bf x}$ is calculated as the trade-off between the effectiveness and monetary expenditure of the strategy, i.e.,

where $\omega$ is a weight coefficient that measures the importance of rumor clarification, which practically represents the financial benefit gained from increasing one rumor-opposed individual.

Combining the above discussions, we formulate an optimization model as shown in (3.8) to describe the DCS problem in a mathematical modeling perspective. For writing convenience, we refer to (3.8) as the DCS model. The DCS model is a $K$-dim optimization problem with the strategy ${\bf x}$ as the decision variable, the trade-off criterion (3.7) as the objective function, and the rumor propagation model (3.2) and (3.3) and feasible set (3.1) as constraint conditions. After solving it, the optimal DCS strategy will be attained.

In addition, to make our mathematical modeling process more clear, we provide a diagram in Figure 3 to illustrate the meanings, derivation and relations of all the equations.

4.   Solution

In the previous section, we reduced the DCS problem to a $K$-dim optimization model (3.8), i.e., the DCS model. In this section, we discuss how to solve it numerically.

Particularly, we apply the genetic algorithm (GA) framework ^[13] to solve the DCS model (3.8). GA is a heuristic framework commonly used to find satisfactory solutions to complex optimization problems by relying on biologically-inspired operators such as crossover and mutation. In regard to our work, instantiating a GA-based method to solve the DCS model requires completing the following primary steps. First, design an initialization scheme to generate random DCS strategies from the feasible set (3.1). Regarding the jargon of the GA framework, each DCS strategy is referred to as a chromosome, and a certain scale of candidate chromosomes together form a population, which needs to iteratively evolve to cover more high-quality chromosomes until a certain number of iteration steps. Second, design a fitness evaluation scheme as a criterion to select high-quality chromosomes from the existing population. Third, design a crossover operator to generate two new chromosomes from a pair of ones in the population. Next, design a mutation operator to generate a new chromosome from an existing one. Finally, design a repair operator to ensure the chromosomes after crossover and mutation will still keep feasible, i.e., satisfying the feasible set (3.1). The details of the above steps are as follows.

4.1.   Initialization

First, let us focus on the initialization scheme of our GA-based method. An initialization scheme generates a random DCS strategy from the feasible set (3.1). As ^[42] reports, the most important thing in population initialization is to maintain good diversity of the yielded chromosomes to prevent premature convergence, and thus a good initialization scheme should make the resulting chromosomes uniformly distributed throughout the whole feasible set. This condition can be well achieved by applying standard random number generators (RNGs) ^[43]. Besides, we need to ensure that every yielded chromosome satisfies the total budget constraint $\sum_{k = 1}^{K} \sum_{j = 1}^{M} c_j x_{kj} \le B$ defined in the feasible set (3.1).

Hence, in the initialization scheme, we repeatedly generate a $(K\times M)$-dimensional uniformly random binary matrix ${\bf x}$ by using standard uniform RNGs, and then accept the matrix as a chromosome if the matrix satisfies the condition $\sum_{k = 1}^{K} \sum_{j = 1}^{M} c_j x_{kj} \le B$. The corresponding pseudocode is shown in Algorithm 1.

4.2.   Fitness evaluation

Next, we focus on the fitness evaluation of DCS strategies. A fitness function measures the quality of different DCS strategies. The higher the fitness, the more satisfactory the strategy is. With a proper fitness function, GA can eliminate low-quality strategies and reserve high-quality strategies. Normally, the fitness of a strategy ${\bf x}$ can be directly represented by its cost-effectiveness function $y({\bf x})$, i.e., $F({\bf x}) = y({\bf x})$.

4.3.   Crossover operator

Next, we discuss the crossover operator. The crossover operator of GA is a mechanism to generate new strategies (i.e., children) from a pair of existing ones (i.e., parents) by exchanging their elements. With the crossover operator, GA can find the optimal strategy with a relatively-large probability. In this paper, we adopt the standard uniform crossover operator ^[13]. Specifically, for a pair of strategies ${\bf x}^1$ and ${\bf x}^2$, the crossover operator exchanges each pair of elements of the two matrices, i.e., $x^1_{kj}$ and $x^2_{kj}$, with the same probability. The corresponding pseudocode is shown in Algorithm 2.

4.4.   Mutation operator

Next, we discuss the mutation operator. The mutation operator of GA is a mechanism to generate a new strategy from an existing one such that GA can find the globally-optimal strategy with a certain probability. In this paper, we adopt the standard uniform mutation operator ^[13]. Specifically, for an existing strategy ${\bf x}$, with the same probability, the mutation operator replaces each element of the strategy, i.e., $x_{kj}$, with $0$ or $1$ uniformly. The corresponding pseudocode is shown in Algorithm 3.

4.5.   Repair operator

Finally, we discuss the repair operator. Recall that after crossover and mutation, the population may contain unfeasible chromosomes which do not satisfy the linear inequality constraint $\sum_{k = 1}^{K} \sum_{j = 1}^{M} c_j x_{kj} \le B$ defined in the feasible set (3.1). Therefore, we need to repair these unfeasible chromosomes.

As discussed in ^[44], a proper way to repair an unfeasible chromosome in constrained optimization is to replace the unfeasible chromosome with its nearest feasible one. Denote $\widetilde{{\bf x}}$ as an unfeasible chromosome. Denote $||\cdot||_2$ as the Euclidean distance. Then, searching the nearest feasible chromosome for the unfeasible chromosome $\widetilde{{\bf x}}$ can be reduced to the following optimization problem:

By observing the crossover and mutation operators, we can learn that any chromosomes generated by the initialization scheme will still be 0-1 binary matrices after crossover and mutation no matter they are feasible or unfeasible, because the two operators do not introduce any element value other than 0 and 1. In this context, the optimization problem (4.1) can be easily solved.

Denote $\widetilde{{\bf x}}^{(i)}$ as one of the new chromosomes yielded by changing $i$ elements in $\widetilde{{\bf x}}$ from 1 to 0. For example, if $\widetilde{{\bf x}} = [1, 1, 1]$, then $\widetilde{{\bf x}}^{(1)}$ can be [0, 1, 1], [1, 0, 1], or [1, 1, 0]. Denote $I = \sum_{k = 1}^{K} \sum_{j = 1}^{M} \widetilde{x_{kj}}$ as the number of elements with a value of 1 in $\widetilde{{\bf x}}$. Then, the corresponding pseudocode to solve the optimization model (4.1) is shown in Algorithm 4, followed by a proof of the correctness. In addition, Figure 4 shows a diagram of the repair operator.

Theorem 2. The result of Algorithm 4 is a solution to the optimization model (4.1).

Proof. Recall that any unfeasible chromosome is a 0-1 binary matrix. Then, it is clear that $||\widetilde{{\bf x}}-\widetilde{{\bf x}}^{(i)}||_2 = \sqrt{i}$, and thus

Because Algorithm 4 scans all the possible $\widetilde{{\bf x}}^{(i)}$ with the increment of $i$ to check if $\widetilde{{\bf x}}^{(i)}$ is feasible, the result of Algorithm 4 must have the shortest Euclidean distance to the unfeasible chromosome $\widetilde{{\bf x}}$. The proof is complete. □

4.6.   DCS algorithm

After having designed the above operators, we now are ready to apply GA to solve the DCS model (3.8). Combining the above descriptions, we provide a full view of our GA-based method in Algorithm 5, which we refer to as the DCS algorithm for writing simplicity. By applying the DCS algorithm, we are able to find satisfactory DCS strategies. In addition, we show a diagram of the DCS algorithm in Figure 5.

5.   Performance of the DCS algorithm

In this section, we verify the performance of the DCS algorithm with numerical experiments. First, with a rumor dataset, we estimate the parameter values of the proposed rumor propagation model to reconstruct a historical rumor event. Second, we investigate the optimal setting of the DCS algorithm and explore the distribution degree of each operator of the DCS algorithm. Third, we validate the effectiveness of the DCS algorithm by comparing it with the Monte Carlo method ^[14]. Finally, we examine how the obtained optimal strategy can restrain rumor propagation.

5.1.   Estimation of model parameters

Let us begin by estimating the three primary parameters of the proposed rumor propagation (3.2): $\alpha$, $\beta$ and $\gamma$. To this end, we introduce a rumor dataset called NERT (Newly Emerged Rumors in Twitter) ^[45], which has been widely used in other rumor-related research. NERT is the result of an empirical study on the spreading process of newly emerged rumors in Twitter. Specifically, it collects rumor-related tweets during a rumor event whose topic is about "A screenshot from MyLife.com confirms that mail bomb suspect Cesar Sayoc was registered as a Democrat". In the dataset, each row represents a tweet associated with the rumor topic, and each column explains an attribute of the tweet, such as the user ID, the date and time when the tweet is published, and the stance of the tweet.

On one hand, by using the method in ^[2], from the dataset we can extract the proportions of different categories of individuals for every time interval during a finite time horizon. Denote each time interval by $T_i$. Denote the proportions of judgment-reserved, rumor-supportive and rumor-opposed individuals at the time interval $T_i$ by $\bar{J}(T_i)$, $\bar{S}(T_i)$ and $\bar{O}(T_i)$, respectively. On the other hand, in our rumor propagation model, the expected proportions of judgment-reserved, rumor-supportive and rumor-opposed individuals at time $t$ are calculated by

respectively. Hence, the optimal estimation of the parameters $\alpha$, $\beta$ and $\gamma$ should make the following conditions hold true as much as possible:

To evaluate the goodness of the three parameters, we define the following Sum-of-Squares-due-to-Error (SSE) equation

Then, the optimal-estimated parameters can be attained by solving

Consider the experiment settings as follows. Let 6 hours be one unit time. Let each time interval $T_i$ be 10 minutes. From the NERT dataset, we extract the proportion curves for a 24-hour time duration from 04:00 on Oct. 27th to 04:00 on Oct. 28th, 2018. After iterating each parameter from the space $\{0.002, \dots, 1\}$, we attain the optimal-estimated parameters $\alpha^* = 0.060$, $\beta^* = 0.088$, $\gamma^* = 0.006$. Figure 6 compares the real and estimated proportion curves, from which it is seen that our rumor propagation model can well approximate the real-world situation.

Besides, let us make the following assumptions for other model parameters:

● The relationship matrix between individuals and channels, ${\bf b}$: In practice, this matrix depends on the actual situation. In our experiments, we set ${\bf b}$ by an arbitrary randomly-generated matrix in which each element is set by 1 with a probability of 0.3.

● The channel-activating costs ${\bf c}$: As reported by ^[46], launching an ads campaign will averagely cost about 2 to 4 dollars per audience. Because the number of connected individuals of the channel $v^C_j$ is $\sum_{i = 1}^{N} b_{ij}$, the cost $c_j$ is therefore calculated by $c_j = r_c \sum_{i = 1}^{N} b_{ij}$, where $2 \le r_c \le 4$ is a random number.

● The spreading rates of clarification channels, $\boldsymbol{\delta}$: In our experiments, we set each $\delta_j$ empirically by a random number such that $\delta_j\in[0.1, 0.3]$.

● The average benefit rates per individual, $\omega$: In our experiments, we set $\omega = 40$ empirically.

5.2.   Optimal setting of the DCS algorithm

Next, we investigate the optimal setting of the DCS algorithm. Because the DCS algorithm is based on the GA framework, there are three crucial parameters that can dramatically affect the effectiveness of the DCS algorithm. They are the population size $N_P$, crossover probability $p_C$ and mutation probability $p_M$. In this subsection, we determine the optimal setting of the DCS algorithm by trying to set these three parameters with different values and observing the results.

Specifically, we consider the case where $\tau = 0.5$, $K = 8$, $M = 3$. Besides, let $N_P \in \{12, 24, 60\}$, $p_C \in \{0.1, 0.2, 0.3, 0.4\}$ and $p_M \in \{0.025, 0.050, 0.075, 0.100\}$. Then, we run the DCS algorithm for every parameter combination with the same iteration steps and observe the performance. Denote $y^*$ as the trade-off of the DCS strategy obtained from the DCS algorithm. Then, Tables 1–3 show the obtained trade-offs under different crossover and mutation probabilities when the population size is set by $N_P = 16$, $N_P = 24$ and $N_P = 60$, respectively.

From the three tables, we can learn that when the population size is small, the mutation probability is the most important factor, which will dramatically affect the performance of the DCS algorithm. Normally, the smaller the mutation probability, the greater the performance. Thus, we should set the mutation probability as small as possible. Besides, it can be understood that the population size is another key factor of the algorithm performance. With the increase of the population size, the trade-off increases no matter what the crossover and mutation probabilities are. So, in practice, the population size should be set as large as possible while ensuring that the runtime is acceptable. Combining the above discussion, we recommend $N_P = 24$, $p_C = 0.3$, $p_M = 0.025$ as the optimal setting with respect to the case we study.

5.3.   Effectiveness of the DCS algorithm

Next, we validate the effectiveness of the DCS algorithm. Although the GA framework has been proven effective in solving most optimization models ^[13], we still need to examine whether the solution obtained from the GA-based DCS algorithm can reach global optimality. To achieve that, we compare the DCS algorithm with the Monte Carlo (MC) method ^[14].

The MC method aims to find the globally optimal solution to an optimization problem by extensively exhausting random feasible solutions. Normally, with the increase of the number of random seed solutions, the maximum performance among all the random seed solutions will gradually approach the globally optimal value. Therefore, if the trade-off obtained by the DCS algorithm can outperform the best trade-off of the MC method, the strategy yielded from the DCS algorithm will probably be the globally optimal one.

Based on the above discussions, we run the MC method with different numbers of random seeds, and compare the MC method with the DCS algorithm in terms of their runtime and trade-offs. Table 4 shows the results. We mention that all the experiments are performed under the same environment. More specifically, all the experiments are conducted by a C++ procedure and the hardware device for computation is a PC machine with 16GB memory and a CPU of AMD 5800x.

From the table, we can learn that the best trade-off as well as the runtime of the MC method increases with the number of random seeds, which exactly satisfies the MC theory. More importantly, the trade-off of the DCS algorithm far exceeds the best trade-off of the MC method. So, we can deduce that the DCS algorithm can probably reach global optimality. Besides, we notice that the runtime of the DCS algorithm is much smaller than that of the MC method. Therefore, the DCS algorithm is more efficient than the MC method.

5.4.   Influences of the optimal DCS strategy

Finally, we examine how the optimal strategy obtained from the DCS algorithm will influence rumor propagation.

Recall that $\widetilde{O}(t)$ and $\widetilde{S}$ denote the expected proportions of rumor-opposed individuals and rumor-supportive individuals at time $t$ without rumor clarification, respectively. Denote $\widetilde{O}^*(t)$ and $\widetilde{S}^*(t)$ as the expected proportions of rumor-opposed individuals and rumor-supportive individuals at time $t$ under the optimal DCS strategy obtained from the DCS algorithm, respectively. Then, Figure 7 compares the proportion curves in terms of the cases with and without the optimal DCS strategy. From the figure, it can be seen that the optimal DCS strategy can dramatically increase rumor-opposed individuals and reduce rumor-supportive individuals. Hence, the optimal DCS strategy is effective in controlling rumor propagation.

6.   Conclusions

In this paper, we have addressed the DCS problem. First, we have proposed a novel rumor propagation model to characterize the influences of different DCS strategies on preventing rumor spreading. On this basis, we have reduced the DCS problem to a mathematical optimization model. Second, we have developed a GA-based numerical method to solve the DCS problem. Third, we have conducted numerical experiments to verify the performances of the developed method.

Still, there are some open problems. First, parameters in our rumor propagation model are assumed as constant coefficients. In fact, because of the trending decay of information topics ^[47], the influence of a rumor can be decreasing over time. Hence, it would be valuable to extend this work by considering a dynamic rumor spreading rate. Second, in our numerical simulations, some model parameters are set empirically. In possible future research, it would be valuable to consider the accurate estimation of these model parameters.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research was funded by Chongqing Education Commission Science and Technology Research Project grant number KJQN202103302, Chongqing Higher Vocational Education Teaching Reform Research Project grant number Z213096, Key Projects of the 13th Five-Year Plan for Chongqing Education Science grant number 2020-GX-163.

Conflict of interest

The authors declare there is no conflict of interest.