# COVID-19 Infection Structure Analysis Based on Minimum Spanning Tree Visualization in the Kingdom of Saudi Arabia Regions

Authors: Samirah H. Alsulami; Jalal H. Bayati
Journal: Journal of Chemistry
 (2022)

---

## Abstract

This work aims to study the extent of the association between the numbers of COVID-19 infections among the regions of Saudi Arabia using a graph theory, especially the calculation of the minimum spanning tree. The research also aims mainly to classify the central regions of Saudi Arabia, whose number of COVID-19 virus infections is centrally linked to other provinces, i.e., when the number of infections in these central regions increases, the number of infections in the associated regions increases and when infections decrease in these central regions, infections decrease in the associated regions.


---

## Body

## 1. Introduction

The study of the topological properties of networks has recently received a lot of attention. In particular, it has been shown that many natural systems display an unexpected amount of correlation with respect to concerning models. Spanning trees are a particular type of graphs. They connect all the vertices in a graph without forming any loop. Therefore, if the number of vertices isn, one has n−1 arcs to connect them [1]. There are several examples of spanning trees in nature. The minimum spanning tree is obtained at different times by computing correlation among time series over a time window of fixed length T [2, 3].The graph theory and the correlation matrix were used to analyze this network and then convert the correlation matrix into a distance matrix, and then create a graph to represent the values ​​of the distance matrix using the Kruskal algorithm [4] and the Pajek program [5] to obtain the MST within the network and then use the Pajek program to image and picture the MST. This research is the first of its kind to use MST (minimum spanning tree) in the study of the COVID-19 virus.


## 2. Methodology and Data

The research was conducted on 13 regions in King Saudi Arabia covering two months from 1st of July, 2021 to 31st of August, 2021. The main 13 regions of the kingdom of Saudi Arabia are Riyadh, Makkah, Eastern Province, Jazan, Madinah, Asir, Al Qassim, Najran, Tabuk, Northern Borders, Al Jouf, Hail, and Al Bahah. All the data are collected from the daily report from the Saudi Ministry of Health for 62 days.Following the methodology developed by RN. Mantegna [6] in this study the coronavirus propagation is formulated as a network problem, where each region is represented as a node and the relationship between each pair of regions is represented as a link.On the first stage, distances between the regions of new cases inhabitants are calculated to construct complete adjacency matrices. Pearson’s correlation is the select measure of distance, which summarizes the grade of similarity of newly registered cases of inhabitants between regions at each considered time window. Given that Pearson’s correlation is invariant to scale measure [7], countries that had similar shapes at their trajectories of propagation but differ in the proportion of the affected population will be considered similar and are likely to cluster. Following RN. Mantegna and H.E. Stanley [8], Pearson’s correlations between the x×yn pairs of chosen regions are computed (see equation (1)) as follows:(1)Rxy=n∑xy−∑x∑yn∑x2−∑x2n∑y2−∑y2,where x and y are the number of new daily cases in two regions and n is the total number of days which is 62. Then, the correlation matrix is built with the correlation coefficient Rxy. By definition Rxy takes values in the interval (−1,1), where −1 means complete anticorrelation, 1 means complete correlation, and 0 means that the two variables are uncorrelated. This matrix is symmetrical, with Rxy=1 in this main diagonal. As it is well known, the Pearson correlation coefficient (1) does not fulfill the three axioms that define a Euclidean metric. For this reason, the correlation matrix is transformed into the correlation distance matrix according to equation (2).(2)dxy=21−Rxy.Subsequently, R.C. Prim’s algorithm [9] is applied to the adjacency matrix to obtain minimal spanning trees (MSTs). Being introduced to graph theory by J. B. Kruskal [10] and R. C. Prim [9], MST has been a widely used tool by M. Limas [11], A. Górski et al. [12], J. Kwapień et al. [13], M. Rešovský et al. [14], and G. J. Wang et at. [15] mainly because it simplifies network analysis by selecting the most relevant bounds. Indeed, MSTs are characterized for representing the core information of a complete network with n nodes by selecting the n-1 links that minimize the overall distance.Prim’s algorithm establishes a procedure in successive stages for the selection of MST links. Taking the information from a complete adjacency matrix, at each step, a node is selected and incorporated into the network. The criteria are to choose, from the not connected nodes, the one that has the shortest distance to a connected one. At the end of the process, all nodes (n) are connected by n-1 links in a network that has the smallest possible total length [4].Subsequently, the single linkage method is applied to obtain a subordinate ultrametric distance matrix from the constructed MST. This graph method is a particular agglomerative hierarchical clustering algorithm. It starts by considering all the nodes of the network as subgroups. In successive stages, the less distant subgroups are joined, the distance between the new subgroup and the rest is determined based on the nearest neighbor criteria.Additionally, every subordinate ultrametric distance matrix can be represented by a hierarchical tree (HT) or dendrogram. Finally, the pseudoT2 and CH cutting criteria are considered to determine the optimal number of groups; the highest number of suggested groups with a maximum of 30 is the one chosen. The described procedure is repeated for each considered time window.


## 3. Results and Discussion

After collecting the data, which are the number of COVID-19 infections among the main 13 regions of Saudi Arabia, and applying the Pearson’s correlations, we obtain Table1. This research attempts to analyze the coronavirus infections (COVID-19) in 13 governorates of the Kingdom of Saudi Arabia during 62 days (July 1, 2021—August 31, 2021) and to find out the extent of the correlation between infections in the selected cities.Table 1
Descriptive statistics of coronavirus infections during the specified period.
CityNMinimumMaximumMeanStd. deviationVarianceRiyadh6254344207,3489,3727987,310Makkah6234377175,1383,0446896,311Eastern Province6220337151,4087,2677615,589Jazan621411864,5328,050786,810Madinah621210947,9420,817433,340Asir621227394,3254,1622933,566Al Qassim62617054,8430,589935,678Najran6298833,6614,794218,851Tabuk6245617,539,09682,745Northern Borders6215016,0610,146102,947Al Jouf622307,444,19117,561Hail6247330,2918,447340,308Al Bahah6215017,5810,830117,297From Table1, it can be noted that(i)
The city of Riyadh recorded the highest rate of cases, with an average of 207 cases per day. While, the AlJouf city had the lowest rate of cases, with an average of about 7 cases per day.(ii)
The largest number of cases in one day was 377, recorded in the city of Makkah.(iii)
The lowest number of cases was 1 per day, and it was recorded in both Northern Borders and Al Bahah. Figure1 represents a graphical view of coronavirus infections during the specific period.Figure 1
Graphical view of coronavirus infections during the specified period.The Pearson’s correlation coefficient was used by calculating the correlation coefficient between coronavirus cases in the 13 cities. Table2 illustrates the types of correlation and the direction of the relationship.Table 2
Types of correlation.
Correlation coefficient valueRelationship+1Perfect direct correlation (or inverse correlation if there is a negative sign)From 0.70 to 0.99Strong direct correlation (or inverse correlation if there is a negative sign)From 0.50 to 0.69Medium positive correlation (or inverse correlation if there is a negative sign)From 0.01 to 0.49Weak direct correlation (or inverse correlation if there is a negative sign)0No correlationFrom the correlation table above, we find that there are statistically significant relationships as follows:(i)
The results showed a strong positive correlation between infection cases in Makkah and cases in Riyadh at 84.1%.(ii)
On the other hand, the cases of infection in the Eastern Province are positively and strongly correlated with 80.5% of the cases in Riyadh and with a rate of 87.2% with cases of infection in Makkah.(iii)
It is noted that the cases of infection in Jazan city are weakly positively correlated by 44.4% with the cases of infection in the city of Riyadh. while there is a moderate direct correlation with the cases of infection in the cities of Makkah and the Eastern Province by 61% and 56.1%, respectively.(iv)
The results also showed a strong positive correlation between infection cases in Madinah and cases in Makkah at 77.6% and 80.6% with cases of infection in the Eastern Province, while there is a medium positive correlation with infection cases in the cities of Riyadh and Jazan, with a percentage of 67.2% and 59.5%, respectively.(v)
Infection cases in the city of Asir were positively and strongly correlated with infection cases in Riyadh by 72.5%, in Makkah by 79.6%, and in the Eastern Province by 78.2%, while a moderate direct correlation was associated with cases in Jazan by 55.5% and in Madinah by 64.4%.(vi)
It is also noted from the correlation matrix table that the cases of infection in the city of Al Qassim have a weak direct correlation with the cases of infection in the cities of Riyadh (40.8%), Makkah (42%), Eastern Province (38%), Jazan (38.7%) and Asir (27.4%), while the relationship between Al Qassim infection cases and the cases of infection in Madinah was a medium positive correlation by 66.4%.(vii)
Cases of infection in the city of Najran were positively and moderately correlated with cases of infection in the cities of Riyadh, Makkah, Eastern Province, Jazan, and Asir by 68.8%, 61.4%, 57.1%, 55.2%, and 58.1%, respectively. While the cases of infection in Najran were positively and weakly correlated with the cases of infection in Madinah by 42.4% and Al Qassim by 35.1%.(viii)
Cases of infection in the city of Tabuk were weakly correlated with infection cases in four cities, namely, Riyadh (46.2%), Asir (44%), Al Qassim (43.8%), and Najran (34.4%), while it was strongly correlated with infection cases in four cities as well, namely, Makkah (58.5%), Eastern Province (56.6%), Jazan (68%), and Madinah (57%).(ix)
Cases of infection in Northern Borders were weakly correlated with infection cases in four cities, namely, Riyadh (47.3%), Makkah (48.7%), Jazan (44.2%), and Asir (33.6%), while it was strongly correlated with infection cases in five cities as well, namely, Eastern Province (59%), Madinah (58.3%), Al Qassim (52.3%), Najran (53.6%), and Tabuk (58.5%).(x)
The results of the correlation analysis showed that the correlation coefficients between cases of infection in Al Jouf governorate and the other (Riyadh, Makkah, Eastern, Jazan, Madinah, Asir, Al Qassim, Najran, Tabuk, and Northern Borders) cities are not statistically significant, as the value of the statistical significance for all coefficients was not significant (all greater than 0.05 or 0.01).(xi)
It is also noted from the correlation matrix table that the cases of infection in Hail have a weak direct correlation with the cases of infection in the Eastern Province (43.1%), Asir (47.5%), and Northern Borders (39%), while the relationship between Hail infection cases and the cases of infection in (Riyadh, Makkah, Jazan, Madinah, Al Qassim, Najran, and Tabuk) cities were a medium positive correlation by 53.7%, 62.6%, 59.8%, 57%, 61%, 53.8%, and 59.9%, respectively. However, the results of the correlation analysis showed that the correlation coefficient between cases of infection in Hail and Al Jouf is not statistically significant, as the value of the statistical significance for the correlation coefficient was not significant (greater than 0.05 or 0.01).(xii)
The cases of infection in Al Bahah have a weak direct correlation with the cases of infection in Jazan (49.4%), Al Qassim (49%), Najran (45.6%), and Tabuk (49%), while the relationship between Al Bahah infection cases and the cases of infection in (Riyadh, Eastern Province, Madinah, Asir, Northern Borders, and Hail) cities were a medium positive correlation by 64.4%, 68.2%, 68.9%, 69.2%, 54.4%, and 53.9%, respectively. On the other hand, the cases of infection in Al Bahah are positively and strongly correlated with 70.7% of the cases in Makkah. However, the results of the correlation analysis showed that the correlation coefficient between cases of infection in Al Bahah and Al Jouf is not statistically significant, as the value of the statistical significance for the correlation coefficient was not significant (greater than 0.05 or 0.01).By analysing the results above, we note that the largest correlation was 87.2%, which is the correlation between cases of infection between Makkah and the Eastern Province, while the lowest correlation rate was 27.4%, which is the correlation between cases of infection in the city of Al Qassim and the city of Asir.Based on the above analyses, we can say that the correlation between cases of infections in the thirteen cities is due to several factors, the most important of which may be the population density and the rate of travel between cities, as cities with a high population density can witness more and more cases of infection compared to cities with a small population density. Also, the travel between cities has an effect on the cases increasing, which has been proven by many studies.Accordingly, we recommend including the population density factors, as well as the rate of travel between the thirteen cities during the specified period to see the extent of the impact of these factors on the rate of correlation between cases of coronavirus infections in the thirteen cities of the kingdom of Saudi Arabia. Correlation matrix table is given in Table3.Table 3
Correlation matrix table.
RiyadhMakkahEastern ProvinceJazanMadinahAsirAiqassimNajranTabukNorthern BordersAl JoufHailAl BahahRiyadh10.841∗∗0.805∗∗0.444∗∗0.672∗∗0.725∗∗0.408∗∗0.688∗∗0.462∗∗0.473∗∗−0.10.537∗∗0.644∗∗Makkah0.841∗∗10.872∗∗0.610∗∗0.776∗∗0.796∗∗0.420∗∗0.614∗∗0.585∗∗0.487∗∗−0.0230.626∗∗0.707∗∗Eastern Province0.805∗∗0.872∗∗10.561∗∗0.806∗∗0.782∗∗0.380∗∗0.571∗∗0.566∗∗0.590∗∗0.0310.431∗∗0.682∗∗Jazan0.444∗∗0.610∗∗0.561∗∗10.595∗∗0.555∗∗0.387∗∗0.552∗∗0.680∗∗0.442∗∗0.298∗0.598∗∗0.494∗∗Madinah0.672∗∗0.776∗∗0.806∗∗0.595∗∗10.644∗∗0.664∗∗0.424∗∗0.570∗∗0.583∗∗−0.0140.570∗∗0.689∗∗Asir0.725∗∗0.796∗∗0.782∗∗0.555∗∗0.644∗∗10.274∗0.581∗∗0.440∗∗0.336∗∗−0.120.475∗∗0.692∗∗Al Qassim0.408∗∗0.420∗∗0.380∗∗0.387∗∗0.664∗∗0.274∗10.351∗∗0.438∗∗0.523∗∗−0.1250.610∗∗0.490∗∗Najran0.688∗∗0.614∗∗0.571∗∗0.552∗∗0.424∗∗0.581∗∗0.351∗∗10.344∗∗0.536∗∗0.0670.538∗∗0.456∗∗Tabuk0.462∗∗0.585∗∗0.566∗∗0.680∗∗0.570∗∗0.440∗∗0.438∗∗0.344∗∗10.585∗∗0.1940.595∗∗0.490∗∗Northern Borders0.473∗∗0.487∗∗0.590∗∗0.442∗∗0.583∗∗0.336∗∗0.523∗∗0.536∗∗0.585∗∗10.1260.390∗∗0.544∗∗Al Jouf−0.1−0.0230.0310.298∗−0.014−0.12−0.1250.0670.1940.1261−0.1480.01Hail0.537∗∗0.626∗∗0.431∗∗0.598∗∗0.570∗∗0.475∗∗0.610∗∗0.538∗∗0.595∗∗0.390∗∗−0.14810.539∗∗Al Bahah0.644∗∗0.707∗∗0.682∗∗0.494∗∗0.689∗∗0.692∗∗0.490∗∗0.456∗∗0.490∗∗0.544∗∗0.010.539∗∗1By putting the values of correlation matrix in the distinct function(equation(3)):(3)dxy=21−Rxy.Now, we give in Table4 the distance between different cities based on equation (3).Table 4
Distance between different cities based on equation (3).
RiyadhMakkahEastern ProvinceJazanMadinahAsirAl QassimNajranTabukNorthern BordersAl JoufHailAl BahahRiyadh00.5640.6241.0550.80990.7421.0880.78991.0371.0271.4830.9620.844Makkah0.56400.5060.8830.6690.6391.0770.8790.9111.0131.430.8650.766Eastern Province0.6240.50600.9370.6230.661.1140.9269320.9060.0311.0670.797Jazan1.0550.8830.93700.90.9431.1070.9470.81.0561.1850.8971.006Madinah0.80990.6690.6230.900.8440.81971.0730.9270.9131.4240.9270.789Asir0.7420.6390.660.9430.84401.2050.9151.0581.1521.4971.0250.785Al Qassim1.0881.0771.1141.1070.81971.20501.1391.060.9771.50.8831.0099Najran0.78990.8790.9260.9471.0730.9151.13901.1450.9630.0670.9611.043Tabuk1.0370.9110.9320.80.9271.0581.061.14500.9110.1940.91.0099Northern Borders1.0271.0130.9061.0560.9131.1520.9770.9630.91100.1261.1050.955Al Jouf1.4831.430.0311.1851.4241.4971.50.0670.1940.12601.5151.407Hail0.9620.8651.0670.8970.9271.0250.8830.9610.91.1051.51500.96Al Bahah0.8440.7660.7971.0060.7890.7851.00991.0431.00990.9551.4070.960By comparing the results obtained from Tables1 and 5, we notice the change of results from the period (−1.1) to the period (2.0). It was found that the MST for the COVID-19 infection network using the Kruskal algorithm, which was programmed in the Pajek language. In Table 6, the MST output format according to Pajek’s requirements is given.Table 5
Correlation matrix table.
RiyadhMakkahEastern ProvinceJazanMadinahAsirAl QassimNajranTabukNorth BordersAl JoufHailAl BahahRiyadhPearson Correlation1Sig.MakkahPearson Correlation0.841∗∗1Sig.0.000Eastern ProvincePearson Correlation0.805∗∗0.872∗∗1Sig.0.0000.000JazanPearson Correlation0.444∗∗0.610∗∗0.561∗∗1Sig.0.0000.0000.000MadinahPearson Correlation0.672∗∗0.776∗∗0.806∗∗0.595∗∗1Sig.0.0000.0000.0000.000AsirPearson Correlation0.725∗∗0.796∗∗0.782∗∗0.555∗∗0.644∗∗1Sig.0.0000.0000.0000.0000.000Al QassimPearson Correlation0.408∗∗0.420∗∗0.380∗∗0.387∗∗0.664∗∗0.274∗1Sig.0.0010.0010.0020.0020.0000.031NajranPearson Correlation0.688∗∗0.614∗∗0.571∗∗0.552∗∗0.424∗∗0.581∗∗0.351∗∗1Sig.0.0000.0000.0000.0000.0010.0000.005TabukPearson Correlation0.462∗∗0.585∗∗0.566∗∗0.680∗∗0.570∗∗0.440∗∗0.438∗∗0.344∗∗1Sig.0.0000.0000.0000.0000.0000.0000.0000.006North BordersPearson Correlation0.473∗∗0.487∗∗0.590∗∗0.442∗∗0.583∗∗0.336∗∗0.523∗∗0.536∗∗0.585∗∗1Sig.0.0000.0000.0000.0000.0000.0080.0000.0000.000Al JoufPearson Correlation−0.100−0.0230.0310.298∗−0.014−0.120−0.1250.0670.1940.1261Sig.0.4380.8570.8080.0190.9120.3520.3320.6040.1300.330HailPearson Correlation0.537∗∗0.626∗∗0.431∗∗0.598∗∗0.570∗∗0.475∗∗0.610∗∗0.538∗∗0.595∗∗0.390∗∗−0.1481Sig.0.0000.0000.0000.0000.0000.0000.0000.0000.0000.0020.251Al BahahPearson Correlation0.644∗∗0.707∗∗0.682∗∗0.494∗∗0.689∗∗0.692∗∗0.490∗∗0.456∗∗0.490∗∗0.544∗∗0.0100.539∗∗Sig.0.0000.0000.0000.0000.0000.0000.0000.0000.0000.0000.9370.000∗∗Correlation is significant at the 0.01 level (2-tailed). ∗Correlation is significant at the 0.05 level (2-tailed). N = 62.Table 6
MST output format according to Pajek's requirements.
Column 1FromToDistanceusedUsed length1Eastern ProvinceAl Jouf0.03110.0312NajranAl Jouf0.06710.0673Northern BordersAl Jouf0.12610.1264TabukAl Jouf0.19410.1945MakkahEastern Province0.50610.5066RiyadhMakkah0.56410.5647Eastern ProvinceMadinah0.62310.6238RiyadhEastern Province0.624009MakkahAsir0.63910.63910Eastern ProvinceAsir0.660011MakkahMadinah0.6690012RiyadhAsir0.7420013MakkahAl Bahah0.76610.76614AsirAl Bahah0.7850016MadinahAl Bahah0.7890017RiyadhNajran0.78990018Eastern ProvinceAl Bahah0.7970019JazanTabuk0.810.820RiyadhMadinah0.80990021MadinahAl Qassim0.819710.819722RiyadhAl Bahah0.8440023MadinahAsir0.8440024MakkahHail0.86510.86525MakkahNajran0.8790026MakkahJazan0.8830027Al QassimHail0.8830028JazanHail0.8970029JazanMadinah0.90030TabukHail0.90031Eastern ProvinceNorthern Borders0.9060032MakkahTabuk0.9110034TabukNorthern Borders0.9110035MadinahNorthern Borders0.9130036AsirNajran0.9150037Eastern ProvinceNajran0.9260038MadinahTabuk0.9270039MadinahHail0.9270040Eastern ProvinceTabuk0.9320041Eastern ProvinceJazan0.9370042JazanAsir0.9430043JazanNajran0.9470044Northern BordersAl Bahah0.9550045HailAl Bahah0.960046NajranHail0.9610047RiyadhHail0.9620048NajranNorthern Borders0.9630049Al QassimNorthern Borders0.9770050JazanAl Bahah1.0060051Al QassimAl Bahah1.00990052TabukAl Bahah1.00990053MakkahNorthern Borders1.0130054AsirHail1.0250055RiyadhNorthern Borders1.0270056RiyadhTabuk1.0370057NajranAl Bahah1.0430058RiyadhJazan1.0550059JazanNorthern Borders1.0560060AsirTabuk1.0580061Al QassimTabuk1.060062Eastern ProvinceHail1.0670063MadinahNajran1.0730064MakkahAl Qassim1.0770065RiyadhAl Qassim1.0880066Northern BordersHail1.1050067JazanAl Qassim1.1070068Eastern ProvinceAl Qassim1.1140069Al QassimNajran1.1390070NajranTabuk1.1450071AsirNorthern Borders1.1520072JazanAl Jouf1.1850073AsirAl Qassim1.2050074Al JoufAl Bahah1.4070075MadinahAl Jouf1.4240076MakkahAl Jouf1.430077RiyadhAl Jouf1.4830078AsirAl Jouf1.4970079Al QassimAl Jouf1.50080Al JoufHail1.51500After applying the Pajek program to the data, we will get the following drawing. Figure2 represents the minimum spanning tree visualization of 13 regions.Figure 2
Minimum spanning tree visualization of 13 Regions.


## 4. Conclusions

The regions of Saudi Arabia were divided into two main parts:The first part is centered on Makkah and the second part is centered on Al Jouf, and the two parts are connected through the Eastern Province. Makkah is a center of four regions that made it play an influential role, linking Al Bahah, Riyadh, Asir, and Hail. Makkah is located in the western of the country and is Islam’s holiest city. It is linked with a region from the north part, which is Hail and two regions from the south part, Al Bahah and Asir. Also linked is the Riyadh region in the middle of the country that makes it the center of a vector and a source for the spread of the virus. On the other hand, Al Jouf is located in the center of 4 regions and has a very important role, but it is less dangerous than the first part, because this part links the least affected regions, as Al Jouf controls the Northern Borders, Najran, and Tabuk and then Jazan. The association of regions with each other is not necessarily due to their geographical location, but it may rather be due to social or religious customs, and it is recommended to apply methods in this research in studying COVID-19.



---

*Source: 1726286-2022-07-26.xml*