IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING TABLE 1 Data Sets Description Data Sets Facebook Twitter Sina weibo Number of nodes 4036 81306 1364548 Number of edges 88234 1768149 31261651 Average degree 21.85 21.74 22.91 Number of connected components 36 278 4631 Average clustering coefficient 0.5731 0.5653 0.5974 strategies start working.All the parameters are selected up to 10%,the infection ratios are lowered by approximately based on empirical results that approximate the realistic 10%,20%and 30%for the classic greedy,proposed greedy scenario.In the experiment,three algorithms are presented and dynamic blocking algorithm respectively. for comparison which are listed as follows: One phenomenon needs to be noticed that at the very Classic Greedy Algorithm:Greedy algorithm based beginning point of blocking strategies,the proposed maxi- on descendant order of nodes degree and is used as mum likelihood greedy algorithm (i.e.the blue curve)per- forms slightly better than the dynamic blocking algorithm the baseline algorithm. (i.e.the red curve).Then after a certain amount of iterations Proposed Greedy Algorithm:the order is deter- mined by the maximum likelihood function.By the red curve surpasses the blue curve and stays better than blocking a node,we can generate a new propagation it ever since.The underlying reason is that in the dynamic blocking algorithm,the dynamic property is revealed from matrix and reach a new maximum survival likeli- hood value. the early stage of rumor blocking.In detail,during the Dynamic Blocking Algorithm:This algorithm ad- initial period of rumor blocking(approximately from 15th justs to each propagation status,and gradually in- to 25th iteration),the blue curve lies under the red one, cludes new targeted nodes as long as the cost is which indicates the slower propagation rate for the static within the scope of tolerable user experience. schema.This can be explained by the fact that the dynamic algorithm does block fewer nodes than the static greedy In Figure 4,we present the simulation results on the algorithm at the initial stage of first several iterations.How- Facebook,Twitter and Sina Weibo datasets respectively. ever,after a certain amount of time (about 25 iterations), Specifically,for each algorithm in each dataset,we repeat the dynamic blocking algorithm dominates the proposed the propagation process for 1000 times and take the average greedy algorithm because the dynamic strategy considers value as the general feature.The black curve stands for clas- the dynamic variation of the topology of the social network sic greedy algorithm,blue one for our proposed maximum in every iteration and constantly introduce new seeds for likelihood greedy algorithm,which blocks all candidates at blocking.In that case,the dynamic blocking algorithm can once and use a metric different from traditional approach, be regarded as an iterative greedy algorithm. and finally red one for the dynamic blocking algorithm.Ob- In the Twitter and Sina Weibo datasets simulation results viously,from all the figures,we can see that for all the social shown in Figure 4,we can see the similar results to those in network datasets,the rumor infection ratio is decreased to the Facebook dataset.The slight difference between them different degrees after the introduction of rumor blockage may be caused by the different topologies of the social strategies.As is shown in the results,according to the final networks.From the dataset description in Table 1,we know infection ratio,the proposed dynamic blocking algorithm that the Sina Weibo network dataset has much more nodes performs the best of all the blocking strategies,since the than the Facebook and Twitter datasets.There are also infection ratio (i.e.,the number of nodes infected by the some differences in average degree,number of connected rumor)is minimized at the end of propagation under this components and average clustering coefficient,which could schema. influence the rumor propagation process and thus the final From all three datasets,we can see that with the blocking infection ratio in the network.For instance,for Sina Weibo percentage of all the nodes increasing from 1%to 10%,the dataset with slightly higher average degree,the network has performances of different blocking strategies vary distinctly. a larger density than the other two.In that case,it is easier In general,for each algorithm,we can see the trend that for rumor to spread through the network and accelerate the the infection ratio tends to be lower with the percentage rumor contagion process.This analysis can be verified by of nodes being blocked becoming higher.However,for the normal rumor propagation curve(i.e.the green curve) different algorithms,the degrees of that trend are different. especially at the very initial stage of rumor propagation. Specifically,the dynamic blocking algorithm has relatively We can see the slope of the green curve in the Sina Weibo the sharpest trend compared to the classic and proposed dataset is slightly higher than the other two,which indicates greedy algorithms.In the Facebook dataset,when the block- the higher average degree and connected components lead ing percentage rises from 1%to 2%,the infection ratio to faster rumor contagion.After the beginning phase,when barely changes for the classic greedy algorithm.In contrast, the infection ratio reaches a certain threshold,the difference the proposed greedy algorithm obtains approximately a between different network topologies becomes minor.On 10%improvement in the infection ratio.For the dynamic the other hand,when it comes to rumor blocking,the higher blocking algorithm,the blocking performance is even better. average degree and connected components enable more In addition,when the blocking percentage becomes higher effective blockage due to its higher density.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 9 TABLE 1 Data Sets Description Data Sets Facebook Twitter Sina Weibo Number of nodes 4036 81306 1364548 Number of edges 88234 1768149 31261651 Average degree 21.85 21.74 22.91 Number of connected components 36 278 4631 Average clustering coefficient 0.5731 0.5653 0.5974 strategies start working. All the parameters are selected based on empirical results that approximate the realistic scenario. In the experiment, three algorithms are presented for comparison which are listed as follows: • Classic Greedy Algorithm: Greedy algorithm based on descendant order of nodes degree and is used as the baseline algorithm. • Proposed Greedy Algorithm: the order is deter￾mined by the maximum likelihood function. By blocking a node, we can generate a new propagation matrix and reach a new maximum survival likeli￾hood value. • Dynamic Blocking Algorithm: This algorithm ad￾justs to each propagation status, and gradually in￾cludes new targeted nodes as long as the cost is within the scope of tolerable user experience. In Figure 4, we present the simulation results on the Facebook, Twitter and Sina Weibo datasets respectively. Specifically, for each algorithm in each dataset, we repeat the propagation process for 1000 times and take the average value as the general feature. The black curve stands for clas￾sic greedy algorithm, blue one for our proposed maximum likelihood greedy algorithm, which blocks all candidates at once and use a metric different from traditional approach, and finally red one for the dynamic blocking algorithm. Ob￾viously, from all the figures, we can see that for all the social network datasets, the rumor infection ratio is decreased to different degrees after the introduction of rumor blockage strategies. As is shown in the results, according to the final infection ratio, the proposed dynamic blocking algorithm performs the best of all the blocking strategies, since the infection ratio (i.e., the number of nodes infected by the rumor) is minimized at the end of propagation under this schema. From all three datasets, we can see that with the blocking percentage of all the nodes increasing from 1% to 10%, the performances of different blocking strategies vary distinctly. In general, for each algorithm, we can see the trend that the infection ratio tends to be lower with the percentage of nodes being blocked becoming higher. However, for different algorithms, the degrees of that trend are different. Specifically, the dynamic blocking algorithm has relatively the sharpest trend compared to the classic and proposed greedy algorithms. In the Facebook dataset, when the block￾ing percentage rises from 1% to 2%, the infection ratio barely changes for the classic greedy algorithm. In contrast, the proposed greedy algorithm obtains approximately a 10% improvement in the infection ratio. For the dynamic blocking algorithm, the blocking performance is even better. In addition, when the blocking percentage becomes higher up to 10%, the infection ratios are lowered by approximately 10%, 20% and 30% for the classic greedy, proposed greedy and dynamic blocking algorithm respectively. One phenomenon needs to be noticed that at the very beginning point of blocking strategies, the proposed maxi￾mum likelihood greedy algorithm (i.e. the blue curve) per￾forms slightly better than the dynamic blocking algorithm (i.e. the red curve). Then after a certain amount of iterations, the red curve surpasses the blue curve and stays better than it ever since. The underlying reason is that in the dynamic blocking algorithm, the dynamic property is revealed from the early stage of rumor blocking. In detail, during the initial period of rumor blocking (approximately from 15th to 25th iteration), the blue curve lies under the red one, which indicates the slower propagation rate for the static schema. This can be explained by the fact that the dynamic algorithm does block fewer nodes than the static greedy algorithm at the initial stage of first several iterations. How￾ever, after a certain amount of time (about 25 iterations), the dynamic blocking algorithm dominates the proposed greedy algorithm because the dynamic strategy considers the dynamic variation of the topology of the social network in every iteration and constantly introduce new seeds for blocking. In that case, the dynamic blocking algorithm can be regarded as an iterative greedy algorithm. In the Twitter and Sina Weibo datasets simulation results shown in Figure 4, we can see the similar results to those in the Facebook dataset. The slight difference between them may be caused by the different topologies of the social networks. From the dataset description in Table 1, we know that the Sina Weibo network dataset has much more nodes than the Facebook and Twitter datasets. There are also some differences in average degree, number of connected components and average clustering coefficient, which could influence the rumor propagation process and thus the final infection ratio in the network. For instance, for Sina Weibo dataset with slightly higher average degree, the network has a larger density than the other two. In that case, it is easier for rumor to spread through the network and accelerate the rumor contagion process. This analysis can be verified by the normal rumor propagation curve (i.e. the green curve) especially at the very initial stage of rumor propagation. We can see the slope of the green curve in the Sina Weibo dataset is slightly higher than the other two, which indicates the higher average degree and connected components lead to faster rumor contagion. After the beginning phase, when the infection ratio reaches a certain threshold, the difference between different network topologies becomes minor. On the other hand, when it comes to rumor blocking, the higher average degree and connected components enable more effective blockage due to its higher density