Coronavirus Pandemic Analysis Through Tripartite Graph Clustering in Online Social Networks

We evaluate the performance of TGC-PDA with real Twitter dataset about “Covid-19” collected between Feb. 15th, 2020 and Sep. 30th 2020. To get the tweet data, we wrote a python program to crawl the tweets and the users who liked them. Multiple hashtag keywords, such as #COVID19, #coronavirus, #covid, covid pandemic, and #COVID20 are used to ensure we can get a large dataset. Since the free Twitter API we use has rate limits and it restricts the number of retrieved tweets during each login access, we have to crawl the data for several months. After removing the duplicate and non-English posts, we obtain 18 327 tweets, with 752 649 users who interacted with the tweets. Some users only interacted with one tweet in our dataset, which are identified as “less interactive” users and excluded. After the data cleanup, we have 301 982 users left.

As all the clustering methods (i.e., Kmeans, NMF, SNMF, ONMTF, and our NMFRU) have one or more parameters to be tuned, to make the comparison fair, we run these methods under different parameters and choose the best result for each algorithm. In addition, we set the number of clusters as the true number of classes for all clustering algorithms on the dataset. In specific, for Kmeans and NMF algorithms, the hyperparameter is $k_{\text{cluster}}$ (number of clusters). If $k_{\text{cluster}}$ is given, no other parameters would be needed. In NMFR, we have two hyperparameters: $\alpha$ and $\beta$ . To find a proper value for these parameters, we plot a loss-value curve, with value ranging from 0.1 to 1000. Then, the $\alpha$ and $\beta$ values can be found by scanning the plot. Since our data size is relatively large and cannot be completely labeled manually, we randomly choose 5% of the data to label and use the result tested by sample data as the framework result.

To evaluate the clustering result, we use the widely used standard metrics, including the clustering accuracy, cluster purity, and Normalized Mutual Information (NMI).

For the clustering accuracy, we compare the outputted clusters $c\in C_{\text{out}}$ with the ground truth labelled data $g\in C_{\text{ground}}$ . The accuracy is defined as follows:

(9) $$\text{Accuracy(}{C}_{\text{out}},C_{\text{ground}})=\frac{1}{k_{\text{sample}}}\sum \delta (g_i,\text{map}(c_i))$$

where $k_{\text{sample}}$ is total number of data samples, $\delta (a,b)$ is the delta function, in which the value equals one if $a=b$ , and equals zero otherwise. The $\text{map}(c_i)$ is a mapping function that maps each cluster label $c_i$ to the same label in the ground truth data. We can use Kuhn-Munkres algorithm to find the best mappings^{[ 45 ]}.

For the cluster purity, we compare the cluster output $c\in C_{\text{out}}$ with the ground truth labelled data $g\in C_{\text{ground}}$ . The purity of the cluster result is calculated,

(10) $$\text{Purity(}{C}_{\text{out}},C_{\text{ground}})=\frac{1}{k_{\text{sample}}}{\displaystyle \underset{c\in C_{\text{out}}}{\sum }\underset{g\in C_{\text{ground}}}{\max }}(c\cap g)$$

where $k_{\text{sample}}$ is the number of data samples. A perfect clustering result has a purity of one, and a bad one has the purity value close to zero.

For the NMI, we compare the cluster output $c\in C_{\text{out}}$ with the ground truth labelled data $g\in C_{\text{ground}}$ . The NMI is defined as

(11) $$\text{NMI(}{C}_{\text{out}},C_{\text{ground}})=\frac{2\times I(C_{\text{out}},C_{\text{ground}})}{[H(C_{\text{out}})+H(C_{\text{ground}})]}$$

where $H()$ represents the entropy, and $I(C_{\text{out}},C_{\text{ground}})$ denotes the mutual information between $C_{\text{out}}$ and $C_{\text{ground}}$ . A higher NMI value means the better clustering result.

To obtain a less biased estimation of the framework, we run NMFRU algorithms twenty times and take the average result for each model.

Table 2 shows the comparison between NMFRU and several baseline models, such as Kmeans, NMF, SNMF, and ONMTF. When applying these baseline models to our data, we do not embed the topic nodes to user nodes. Instead, we use the user and tweet bipartite graph to calculate the clustering result. The matrix form of the bipartite graph is that the columns and rows correspond to the two sets of vertices, with each entry corresponding to an edge between a column and a row. From Table 2 , we can see that NMFRU achieves the best performance in terms of accuracy, purity, and NMI. This is because our bipartite graph is created based on our tripartite graph model, and it embedded more information than the plain bipartite graph. We also utilize the tri-factorization and locality preserved schemes, which can further improve the performance.

We study the average convergence time of our framework in Fig. 6 . When the number of iterations is around 23, our framework tends to converge with a total loss of 2, which shows that the calculation of NMFRU is fast. Meanwhile, when comparing the convergence time by the different baseline methods in Fig. 7 , we can see that NMFRU is slower than Kmeans but faster than other baseline clustering methods. It is because we do fewer matrix multiplication operations in NMFRU, hence saving some running time. Therefore, TGC-PDA that utilizes NMFRU as the core clustering algorithm can be used for a large dataset.

10.26599/BDMA.2021.9020010.F006 Fig. 6Total loss with different numbers of iterations.

10.26599/BDMA.2021.9020010.F007 Fig. 7Convergence time of methods.

As for the polarity of the communities, Table 3 shows the largest ten communities with its polarity ratio. From Table 3 , we find that the neutral ratio is quite high among all topics. In order to figure out the rationale here, we manually examined 1000 posts and found that there are lots of media or government agencies (e.g., CNN and CDC) that use Twitter to publish real-time news and the latest policy. These tweets tend to be retweeted many times. Obviously, such tweets are more likely to be considered neutral.