# Analysis on COVID-19 Infection Spread Rate during Relief Schemes Using Graph Theory and Deep Learning

Authors: Ashokkumar Palanivinayagam; Ramesh Kumar Panneerselvam; P. J. Kumar; Hariharan Rajadurai; V. Maheshwari; Shaikh Muhammad Allayear
Journal: Computational and Mathematical Methods in Medicine
 (2022)

---

## Abstract

The novel coronavirus 2019 (COVID-19) disease is a pandemic which affects thousands of people throughout the world. It has rapidly spread throughout India since the first case in India was reported on 30 January 2020. The official report says that totally 4, 11,773 cases are positive, 2, 28,307 recovered, and the country reported 12,948 deaths as of 21 June 2020. Vaccination is the only way to prevent the spreading of COVID-19 disease. Due to various reasons, there is vaccine hesitancy across many people. Hence, the Indian government has the solution to avoid the spread of the disease by instructing their citizens to maintain social distancing, wearing masks, avoiding crowds, and cleaning your hands. Moreover, lots of poverty cases are reported due to social distancing, and hence, both the center government and the respective state governments decide to issue relief funds to all its citizens. The government is unable to maintain social distancing during the relief schemes as the population is huge and available support staffs are less. In this paper, the proposed algorithm makes use of graph theory to schedule the timing of the relief funds so that with the available support staff, the government would able to implement its relief scheme while maintaining social distancing. Furthermore, we have used LSTM deep learning model to predict the spread rate and analyze the daily positive COVID cases.


---

## Body

## 1. Introduction

Novel coronavirus 2019 emerged in China in Wuhan—the capital of Hubei province in December 2019. The virus is thought to have a zoonotic origin (the spread from animal to human) as most of the initial cases are linked to Huanan Seafood Wholesale Market [1] [2]. COVID-19 is soon identified as pandemic [3]; the image at Figure 1 shows how the exponent spread of the virus at various countries over short duration of time [4]. The virus spreads from people to people who have close contact [5], the spreading is done by small droplets (which are produced by coughing and sneezing by an infected person). Infected people suffer from symptoms like fever, dry cough, and shortness of breath. Sometimes, people spread the disease without the symptoms as few of the infections may be asymptomatic. As of 10 April 2020, approximately 1.6 million cases of COVID-19 have been found positive across 209 countries, and the death from the disease is estimated at around 95,700, and the number of patients recovered is approximately 354,000 shown in Figure 2 [6]. It is also found that most of the people with COVID-19 recover fully, while the death rate is around 14.8% for ages 80+, while for other ages, it is less than 8%. Day to day, much research is done for analyzing the COVID-19 rate through various methods like the usage of EHR [7], blockchain [8], and augmented intelligence [9].Figure 1
A sample subgraph construction from three districts.Figure 2
The spread of coronavirus (globally).Social distancing is a nonmedical measure to prevent the spread of the coronavirus making the people stay away from each other by minimum a distance of 2 meters. The main purpose of social distancing is to avoid the number of times that people come close to each other, thus ultimately reducing the chances of an uninfected person to have contact with an infected person to break the chain and reducing the spread of this epidemic. The image in Figure3 shows how social distancing helps to control the spread of the infection by breaking the chain. There are few artificial intelligence (AI) based study on social distancing [10].Figure 3
Number of cities affected in uniform dataset.India, despite being the second-most populous country in the world, is one of the few countries across the world which is controlling the infection as the infection rate is 1.7, which is lower than the worst affected countries [11]. On 22 March 2020, the entire nation observed Janata curfew—all the citizens were asked to stay at home and from 24 March 2020, and the entire nation went into a 21-day lockdown to prevent the spread of the infection. Figures 4 and 5 show the infection spread as of 20 June 2020 at India [12]. Early and strict lockdown made India fight against corona. It is also found that the coronavirus can stay alive outside the human body up to a maximum of 72 hours; hence, lockdown avoids people’s interaction and eventually killing the coronavirus. Moreover, lockdown causes the economy of the country to be disturbed on a large scale because of lack of employee attendance. Many sectors such as micro and small scale industries, farming, and other self-employed firms needs more man power, which might cause loss of life when no proper care is taken. Lockdown is justified as a preemptive measure to avoid large losses of life. To help the citizens financially, both the center government and the respective state governments decided to give relief funds.Figure 4
Coronavirus outbreak at India.Figure 5
The end result of graph coloring. The image shows how the division is made using graph coloring.To avail the relief fund, the citizens should visit a few places like banks and ATMs to avail their financial support from the government. Support staff, including police and volunteers, are allotted at these places to prevent the citizens from violating the social distancing. Because of the huge population and fewer support staff, it is difficult for support staff to organize the crowd and maintain social distancing between them which is shown in Figure6. In this research paper, the proposed algorithm makes use of graph theory to schedule the open-close timings of banks and ATMs to help the support staff to maintain social distancing between citizens. The coloring algorithm can easily visualize when the banks or ATMs should be opened or closed; the proposed coloring is based on subgraph coloring [13].Figure 6
The control of infection through social distancing.A treatment for COVID-19 is not yet found, but few researches [14] aim to find drug targeting relationships. In Feb. 2020, few health systems like UW Medicine found few drugs to cure COVID-19 [3], and these drugs need to be tested across large scale before releasing to the public. The sliding value is set as 1 to predict the daily cases; however, this is not a limitation, and the number can be increased to any positive value. The sliding value is useful in many cases; suppose if the positive case for one week needs to be found, then, the value can be set as 7.To control the spread of the disease, the government should take measures to reduce the growth rate. Table1 shows the growth rate for 10 days from June 11 2020 to June 20 2020 [15]. Table 2 describes synthetic dataset. The growth rate is calculated using the formula in Equation (2). The data of daily positive cases are collected from the Indian Health Department daily circular; the future values and for the days where values are not officially released are predicted using linear regression model.
(1)GrowthRatedayi=Casedayi‐Casedayi‐1Casedayi∗100.Table 1
Growth rate of COVID-19 at India.
Date+ve casesGrowth rateJune 20411, 7504.02June 19395, 8383.87June 18381, 0983.77June 17367, 2693.7June 16354, 1613.23June 15343, 0753.01June 14333, 0433.55June 13321, 6383.89Table 2
Synthetic dataset description.
DatasetNumber of citiesAverage populationUniform1, 00053, 029.45Skewed1, 00052, 333.725


## 2. Contributions

The paper proposes a graph coloring algorithm that can schedule the open-close timings of the banks/ATMs to help the support staff to maintain social distancing between the citizens. Our contributions are as follows:(i)
Partition the graph representation of the country geography into subgraphs so that each subgraph represents a district(ii)
Implement the graph coloring based on the population and the availability of support staff(iii)
Recommend the colored graph to the government so that they can schedule the relief fund execution plan(iv)
Predict how much reduction of COVID-19 spread rate caused by the proposed methodThis paper contains six sections. Few works related to graph theory are presented in Section2. Section 3 contains the proposed methodology and the implementation details. We evaluate our work with some set of experiments which are discussed in Section 4. Section 5 contains the discussion part, and finally conclusion and the future work are provided at the Section 6.


## 3. Related Works

Graph coloring is one of the active research algorithms in graph theory where a given graph G and a set of k colors [16], the objective is to color all vertices of G with any one of the colors in k, where no two adjacent vertices share the same color. The application of graph coloring is at all-disciplinary research. [17] proposes a coloring algorithm game that starts from a connected graph, and after each turn, the smallest integer k is found. The subgraph that is generated during the process is also connected. They prove that for the number of colors k≥3, bob wins the game, and with k=2, Alice wins the game. Few other researches works [18] on when Bob starts first. In other research [19], they provide proofs for dynamic coloring, in which at least one vertex of degree 2 consists of independent color. [20] proposes b-coloring algorithm in which each color has at least one vertex which is adjacent to each other. There are other research activities [21] which use the graph coloring for entropy compression methods. The graph coloring problem can be generalized to any power graph as proposed by [22].The coloring of grid-like graphs has been investigated by [23], and they have improved the range of chromatic number usage at grid-based graphs. There are several researches in the field of network [24, 25, 26] in which they use graph coloring algorithms for increasing the efficiency of the communications. The graph coloring is done mostly in the acyclic graph, when there is a cycle; then, it requires a minimum of three colors for a cycle [27], and in most of the network-oriented applications, it is common that there is a cycle [28].While the majority of the research is based on the acyclic graph, there are few researches on specialized graph such as edge coloring [29] and plane graph [30, 31]. One of the specialized edge coloring is rainbow coloring [32] that is when the triangular graph has three unique edge colors, and few researches provide proof for rainbow coloring [33].


## 4. The Relief Scheduling Graph Coloring Algorithm

The paper proposes a modified graph coloring algorithm in which colors are given based on the availability of support staff rather than considering neighbors alone. Before implementing the proposed model, the proposed algorithm first considers partitioning the graph representation of the country into disjoint subgraphs where each subgraph represents a district. This is because the availability of support staff can be easily measured and can be easily transported from one city to another. Figure7 shows how the division is made. In the figure, the vertex denotes cities, and the edge between the vertexes denotes the route between one city towards another.Figure 7
Number of cities affected in skew dataset.Once the division is made, a dummy node has been created, and all the nodes are connected towards it in a different graph. The connection is made as per star topology [34, 35]; that is, in this new graph, all the cities are connected only with the dummy node. The edge value represents the population count of each city. The nodes in the district are the same as the number of cities in that respective area. The equation of this graph is shown in Equation (3). The procedure for constructing the star topology is shown at Algorithm 1(2)Edgedummynode,city=Populationi.The purpose of constructing star topology is because connecting and managing the people population over cities becomes easy [36, 37]. Let the available support staff in a subgraph (entire district) be Ns and the total population in a city i is Nci. Let the constant value Mdenotes the maximum number of citizens that single support staff can manage at a time to maintain social distancing. The goal of the paper is to divide the existing population less than or equal to M, so that it becomes easy for the support team to organize the public. If the population is greater than M, then it will be overcrowded, and the support team cannot manage the population, and it becomes difficult to maintain social distancing. The maximum nodes in each city depends on the population and the number of nodes can be Population/Ns∗M. For example, say M=20, that is, a single support staff can manage up to 20 public citizens at a time and prevent them from avoiding social distancing. Suppose if there are 1000 support staff in a district, then they can manage up to 20,000 people and help them to maintain social distancing. So the proposed graph coloring algorithm should color the cities of not more than 20,000 populations with one color. Hence, there are two different cases arise.


### 4.1. Case 1: IfNci<M∗Ns

In case a single city has less population thanM∗Ns (the maximum population that the support team can manage), then, the next city is added towards the count. The process of adding next city continues until there are no more cities left in the particular subgraph or the cumulative population reaches M∗Ns. If the distance of neighboring cities is more than 10 KM, then a new dummy node is created.


### 4.2. Case 2: IfNci>M∗Ns

For large cities, it is common that the support team cannot handle the entire population of the city, even if all the support team has involved in it. So in that case, the proposed algorithm is used to partition the city into distinct areas. The division is performed by calculating the total area of the city divided by the population. Then, either each division or combination of multiple divisions is considered based on the value ofM. The cities in the topology are sorted based on their population in ascending order before consideration of inclusion. The Algorithm 2 shows the working model of the proposed algorithm. The Figure 5 shows the final output of the proposed algorithm. The main judgment criteria are the population of the city. If the population is less than the dummy node size, then more than one city is present in the dummy node; otherwise, one city is placed across many dummy nodes. In majority of the cases, each city is spanned across multiple dummy nodes.Algorithm 1: Construction of Star Topology.
1:procedure CONSTRUCTSTARTOPOLOGY2:G ← The sub Graph3:M ← Control Ratio4:Ns ← Number of support staffs5:begin:6:foreach City i in Gdo7:ifPopulation of i < M∗Nsthen8:create i node in star topology9:connect with dummy node, edge value is the population of i10:else11:T = Total Area of i12:partition[] = T/Population of i13:Recursively divide the partition if the partition population > M∗Ns14:Create node for each partition15connect with dummy node, edgeAlgorithm 2: Graph Coloring
1:procedure GRAPH COLORING 2:M ← Control Ratio3:G ← The Star Topology4:Ns ← Number of support staff5:N ← Population of each city6:begin:7:Sort the nodes in G based on the edge value - topological sort8:Choose a color C9:cummulative population =010:foreach City i in sorted star topologydo11:ifcummulative Population can be controlled by M∗Nsthen12:Color the node with C13:add current population to cummulative14:else15:cummulative population = current population16:Change the color C to new unused color17:Color the node with C


## 4.1. Case 1: IfNci<M∗Ns

In case a single city has less population thanM∗Ns (the maximum population that the support team can manage), then, the next city is added towards the count. The process of adding next city continues until there are no more cities left in the particular subgraph or the cumulative population reaches M∗Ns. If the distance of neighboring cities is more than 10 KM, then a new dummy node is created.


## 4.2. Case 2: IfNci>M∗Ns

For large cities, it is common that the support team cannot handle the entire population of the city, even if all the support team has involved in it. So in that case, the proposed algorithm is used to partition the city into distinct areas. The division is performed by calculating the total area of the city divided by the population. Then, either each division or combination of multiple divisions is considered based on the value ofM. The cities in the topology are sorted based on their population in ascending order before consideration of inclusion. The Algorithm 2 shows the working model of the proposed algorithm. The Figure 5 shows the final output of the proposed algorithm. The main judgment criteria are the population of the city. If the population is less than the dummy node size, then more than one city is present in the dummy node; otherwise, one city is placed across many dummy nodes. In majority of the cases, each city is spanned across multiple dummy nodes.Algorithm 1: Construction of Star Topology.
1:procedure CONSTRUCTSTARTOPOLOGY2:G ← The sub Graph3:M ← Control Ratio4:Ns ← Number of support staffs5:begin:6:foreach City i in Gdo7:ifPopulation of i < M∗Nsthen8:create i node in star topology9:connect with dummy node, edge value is the population of i10:else11:T = Total Area of i12:partition[] = T/Population of i13:Recursively divide the partition if the partition population > M∗Ns14:Create node for each partition15connect with dummy node, edgeAlgorithm 2: Graph Coloring
1:procedure GRAPH COLORING 2:M ← Control Ratio3:G ← The Star Topology4:Ns ← Number of support staff5:N ← Population of each city6:begin:7:Sort the nodes in G based on the edge value - topological sort8:Choose a color C9:cummulative population =010:foreach City i in sorted star topologydo11:ifcummulative Population can be controlled by M∗Nsthen12:Color the node with C13:add current population to cummulative14:else15:cummulative population = current population16:Change the color C to new unused color17:Color the node with C


## 5. Results and Discussion

In this section, we present the evaluation result of our experiment such as number of cities affected/minimum number of k (colors) required to maintain proper social distancing. We have considered the following assumptions before starting the experiment(1)
The support staffs are not affected from COVID and fully vaccinated(2)
The number of support staff is not changed throughout the experiment(3)
There is no more than 10KM distance from each neighboring city


### 5.1. Dataset Description

In our experiment, we have used both real and synthetic datasets. In the real dataset, we consider two Indian cities. The details of real dataset are given at Table3. Two synthetic datasets (uniform and skewed) are constructed which contains 1000 cities. The dataset description is given in Table 2. In uniform dataset, the population of the cities is randomized between 2,000 and 1, 00,000. In the skewed dataset, the population of the cities is in increasing order by a random number between 2,000 and 1, 00,000. The distribution of the population across the cities is shown in Table 4. In the experiment, only one district has been considered and as the result can be replicated to any number of districts without any restrictions. There are four different values of the number of support staff 500, 1000, 1500, and 2000 that were considered as shown in Table 3. The skewed dataset is calculated as follows: The population is randomly generated for each city, and then, the random values are sorted and assigned one by one to the cities from left to right until there are no more cities.Table 3
City population details in each dataset.
RangeCity count (uniform)City count (skewed)2000 – 500025235001 – 10000555010001-5000037040650001-7000022719170001-9000021821090001-100000105120Table 4
Indian city description.
CityNumber of policePopulationGreater Chennai98, 8628, 653, 521Delhi77, 96519, 298, 507


### 5.2. Analysis on Value ofk

Figure8 shows the minimum value of k (the colors required to color the graph) for different values of support staff and different populations. It can be noted that the required number of colors purely depends on the population, and the number of colors can be decreased when the number of support staff is increased. Since the available support staff is fixed, the government can call for additional volunteers who can help the support staffs to control the public and maintain social distancing between them.Figure 8
The minimumk value needed to color the graph.The value ofk denotes the number of days required to complete the relief scheme. The government goal should aim to reduce the value of k. As you can see in the graph coloring as per the value of k, the venues like ATMs and banks can remain open on specific days. That is, if two nodes are having the same color, that means that either they are present at two different districts (two separate subgraphs) or at the same subgraph. If the color is present in two different districts, that means there are two different independent support teams so they can manage to control the public parallelly at two different places. In case they are on the same subgraph, that means there is enough support team to control the public at two different places. The relief schemes should be made within the allocated short duration as it will timely help the poor, so Figure 9 shows how many support staff should be made available to complete the relief scheme. To increase the support staff, the government may call for additional volunteers.Figure 9
The minimum number of support staff needed.The growth rate is the most important aspect to be considered as far as any pandemic is concerned. If the growth rate is under control, then the government is easily able to get rid of the pandemic. As discussed earlier, social distancing is the current best solution taken by all countries across the world to keep the growth rate under control. We have made a study on our proposed method and how it affects the growth rate. At few situations which include fewer support staff, then, the spread cannot be controlled. The proposed method aims to utilize the available support staff most optimally, hence maintaining social distance as much as possible. Figure10 shows how much the growth rate is reduced by the implementation of the proposed algorithm. Uniform dataset is used to construct the graph.Figure 10
The graph shows the reduction in growth rate of covid-19 when the proposed method is implemented.When the number of support staff and the number of additional volunteers are known, it is easy to calculate the required number of days for completing the relief schemes by the government. The formula for calculating the required number of days is given in Equation (3). Using the formula, it is found that in the two datasets, 54 and 55 days are required to complete the relief funds, respectively. Figures 3 and 7 show the number of cities which are affected without maintaining social distancing when the number of days is fixed for the uniform and skewed datasets, respectively. The data used in the experiment was m=20 and Ns=50000. When the proposed algorithm is not used, then the Ns is considered as an uniform distribution across all the cities.


### 5.3. Analysis on Spread Rate

In this subsection, we will present how the proposed graph coloring algorithm helps to reduce the spread of the coronavirus. In this analysis, we consider a few assumptions for the experiment as shown in Table3. We assume that 25,000 is the total positive case in both the setup. As per the assumption, the relief funds should be completed within 15 days. We assume that the entire population visits the relief fund issuing location (such as ATMs and banks) once on a random day between 1 and 15. If the number of support staff is sufficient to complete the relief funds in 15 days in block, then the entire block is considered in calculating the infections. If the support staff is less, then the blocks are divided into batches, and each batch is considered at once for calculating the infections.In the experiment, a maximum of 5,000 (in setup 1) and 10,000 (in setup 2) people can be controlled by support staff and help to maintain social distancing; since the arrival rate of the customers to the relief fund issue location is randomized, the maximum citizens saved from infection are not more than 3,284 (with the assumption parameters). The graph in Figures11 and 12 shows how much infection is possible with and without the graph coloring algorithm. In those graphs, it can be observed that maintaining social distancing helps to reduce the infections as the proposed system helps the government to maintain the social distancing among its citizens; the graph in Figure 13 shows the how many citizens are saved from the spreading of the infection. The values present in the graph also indicate the number of citizens that were controlled by the support staff.
(3)RequiredDays=TotalPopulationM∗Ns.Figure 11
The comparison of number of infection (setup 1).Figure 12
The comparison of number of infection (setup 2).Figure 13
The figure visualizes the number of infections prevented from using the proposed graph coloring method.


### 5.4. Analysis on Reduction of Spread Rate

The aim of this research work is to optimize the work schedule of the support staff to minimize the spread rate. In this subsection, we present the analysis of how many people can be saved from infection using the proposed method. For this purpose, we use long-short-term memory model (LSTM) [29]. The structure of LSTM is illustrated in Figure 14. LSTM is widely used in many time series prediction because of its ability to remember the past value [38] [39]. The working of LSTM is based on three gates called as forget gate, input gate, and output gate. The LSTM model is used to compute the number of affected persons based on the previous inputs. If the affected number is less than Ns∗M, then, the infection is saved completely, and if it is more than the Ns∗M, then, the difference value is considered as affected.Figure 14
The LSTM model used to update the COVID time series data.Forget gate decides what information should be removed from the LSTM model. It uses a sigmoid function to assign a weight between 0 and 1. A 1 represents to keep the information fully, and a 0 represents to get rid of the information completely. Equation (4) illustrates forgot gate.
(4)ft=σWf.ht−1,xt+bf.The second gate is responsible for storing new information in the LSTM model. This gate uses the weighting scheme like the forget gate along with a list of candidate values generated. The equation of input gate and the candidate generation is illustrated in the following equations:(5)it=σWi.ht−1,xt+b1,(6)C=tanhWc.ht−1,xt+bc.Finally, the output gate decides the value that is going to leave the LSTM. This gate uses sigmoid for outputting the filtered information. The output value is multiplied with cell state and a tanh function as described in the following equations:(7)ot=σW0.ht−1,xt+bo,(8)ht=ot∗tanhCt.The parameters used in calculating the spread rate are the support staff count (Ns), the maximum number of people each support staff can monitor (M), the population of the city, and the previous 7 days of impact. We have considered the number of past values to remember as 7 (1 week). The number of hidden layers in the model is 50. We have used the Adam optimizer with batch size as 10. In the experiment, we divided the daily positive cases into two groups; first, controllable- this determines how many cases can be prevented by using the proposed graph coloring method; second, uncontrollable - this represents how many cases cannot be prevented by the proposed method. The number of past days is set to 7 because as per the WHO report, seven days is the minimum time frame for affected persons to show symptoms of COVID. The uncontrollable value is fed into the LSTM to determine the spread rate. The mean square error (MSE) is used to train the LSTM model; the equation for MSE is shown in the following equation:
(9)MSE=1n∑i=1nyi−y¨i2.where Yi denotes the actual value. This can be calculated as the number of people who are infected when the proposed graph coloring algorithm is used. Yi denotes the predicted value by the LSTM model. Figure 15 shows LSTM model to predict the reduction of spread rate.Figure 15
LSTM model to predict the reduction of spread rate.Figure16 shows the prediction of LSTM and the reduction of the growth rate when the proposed graph coloring approach is used. All the data used in this experiment is shown in Table 5.Figure 16
Growth rate comparison.Table 5
Experiment setup.
SetupPopulationNsmMax # of daysSpread ratioSetup1Setup2400000400000250400202515154.013.23


## 5.1. Dataset Description

In our experiment, we have used both real and synthetic datasets. In the real dataset, we consider two Indian cities. The details of real dataset are given at Table3. Two synthetic datasets (uniform and skewed) are constructed which contains 1000 cities. The dataset description is given in Table 2. In uniform dataset, the population of the cities is randomized between 2,000 and 1, 00,000. In the skewed dataset, the population of the cities is in increasing order by a random number between 2,000 and 1, 00,000. The distribution of the population across the cities is shown in Table 4. In the experiment, only one district has been considered and as the result can be replicated to any number of districts without any restrictions. There are four different values of the number of support staff 500, 1000, 1500, and 2000 that were considered as shown in Table 3. The skewed dataset is calculated as follows: The population is randomly generated for each city, and then, the random values are sorted and assigned one by one to the cities from left to right until there are no more cities.Table 3
City population details in each dataset.
RangeCity count (uniform)City count (skewed)2000 – 500025235001 – 10000555010001-5000037040650001-7000022719170001-9000021821090001-100000105120Table 4
Indian city description.
CityNumber of policePopulationGreater Chennai98, 8628, 653, 521Delhi77, 96519, 298, 507


## 5.2. Analysis on Value ofk

Figure8 shows the minimum value of k (the colors required to color the graph) for different values of support staff and different populations. It can be noted that the required number of colors purely depends on the population, and the number of colors can be decreased when the number of support staff is increased. Since the available support staff is fixed, the government can call for additional volunteers who can help the support staffs to control the public and maintain social distancing between them.Figure 8
The minimumk value needed to color the graph.The value ofk denotes the number of days required to complete the relief scheme. The government goal should aim to reduce the value of k. As you can see in the graph coloring as per the value of k, the venues like ATMs and banks can remain open on specific days. That is, if two nodes are having the same color, that means that either they are present at two different districts (two separate subgraphs) or at the same subgraph. If the color is present in two different districts, that means there are two different independent support teams so they can manage to control the public parallelly at two different places. In case they are on the same subgraph, that means there is enough support team to control the public at two different places. The relief schemes should be made within the allocated short duration as it will timely help the poor, so Figure 9 shows how many support staff should be made available to complete the relief scheme. To increase the support staff, the government may call for additional volunteers.Figure 9
The minimum number of support staff needed.The growth rate is the most important aspect to be considered as far as any pandemic is concerned. If the growth rate is under control, then the government is easily able to get rid of the pandemic. As discussed earlier, social distancing is the current best solution taken by all countries across the world to keep the growth rate under control. We have made a study on our proposed method and how it affects the growth rate. At few situations which include fewer support staff, then, the spread cannot be controlled. The proposed method aims to utilize the available support staff most optimally, hence maintaining social distance as much as possible. Figure10 shows how much the growth rate is reduced by the implementation of the proposed algorithm. Uniform dataset is used to construct the graph.Figure 10
The graph shows the reduction in growth rate of covid-19 when the proposed method is implemented.When the number of support staff and the number of additional volunteers are known, it is easy to calculate the required number of days for completing the relief schemes by the government. The formula for calculating the required number of days is given in Equation (3). Using the formula, it is found that in the two datasets, 54 and 55 days are required to complete the relief funds, respectively. Figures 3 and 7 show the number of cities which are affected without maintaining social distancing when the number of days is fixed for the uniform and skewed datasets, respectively. The data used in the experiment was m=20 and Ns=50000. When the proposed algorithm is not used, then the Ns is considered as an uniform distribution across all the cities.


## 5.3. Analysis on Spread Rate

In this subsection, we will present how the proposed graph coloring algorithm helps to reduce the spread of the coronavirus. In this analysis, we consider a few assumptions for the experiment as shown in Table3. We assume that 25,000 is the total positive case in both the setup. As per the assumption, the relief funds should be completed within 15 days. We assume that the entire population visits the relief fund issuing location (such as ATMs and banks) once on a random day between 1 and 15. If the number of support staff is sufficient to complete the relief funds in 15 days in block, then the entire block is considered in calculating the infections. If the support staff is less, then the blocks are divided into batches, and each batch is considered at once for calculating the infections.In the experiment, a maximum of 5,000 (in setup 1) and 10,000 (in setup 2) people can be controlled by support staff and help to maintain social distancing; since the arrival rate of the customers to the relief fund issue location is randomized, the maximum citizens saved from infection are not more than 3,284 (with the assumption parameters). The graph in Figures11 and 12 shows how much infection is possible with and without the graph coloring algorithm. In those graphs, it can be observed that maintaining social distancing helps to reduce the infections as the proposed system helps the government to maintain the social distancing among its citizens; the graph in Figure 13 shows the how many citizens are saved from the spreading of the infection. The values present in the graph also indicate the number of citizens that were controlled by the support staff.
(3)RequiredDays=TotalPopulationM∗Ns.Figure 11
The comparison of number of infection (setup 1).Figure 12
The comparison of number of infection (setup 2).Figure 13
The figure visualizes the number of infections prevented from using the proposed graph coloring method.


## 5.4. Analysis on Reduction of Spread Rate

The aim of this research work is to optimize the work schedule of the support staff to minimize the spread rate. In this subsection, we present the analysis of how many people can be saved from infection using the proposed method. For this purpose, we use long-short-term memory model (LSTM) [29]. The structure of LSTM is illustrated in Figure 14. LSTM is widely used in many time series prediction because of its ability to remember the past value [38] [39]. The working of LSTM is based on three gates called as forget gate, input gate, and output gate. The LSTM model is used to compute the number of affected persons based on the previous inputs. If the affected number is less than Ns∗M, then, the infection is saved completely, and if it is more than the Ns∗M, then, the difference value is considered as affected.Figure 14
The LSTM model used to update the COVID time series data.Forget gate decides what information should be removed from the LSTM model. It uses a sigmoid function to assign a weight between 0 and 1. A 1 represents to keep the information fully, and a 0 represents to get rid of the information completely. Equation (4) illustrates forgot gate.
(4)ft=σWf.ht−1,xt+bf.The second gate is responsible for storing new information in the LSTM model. This gate uses the weighting scheme like the forget gate along with a list of candidate values generated. The equation of input gate and the candidate generation is illustrated in the following equations:(5)it=σWi.ht−1,xt+b1,(6)C=tanhWc.ht−1,xt+bc.Finally, the output gate decides the value that is going to leave the LSTM. This gate uses sigmoid for outputting the filtered information. The output value is multiplied with cell state and a tanh function as described in the following equations:(7)ot=σW0.ht−1,xt+bo,(8)ht=ot∗tanhCt.The parameters used in calculating the spread rate are the support staff count (Ns), the maximum number of people each support staff can monitor (M), the population of the city, and the previous 7 days of impact. We have considered the number of past values to remember as 7 (1 week). The number of hidden layers in the model is 50. We have used the Adam optimizer with batch size as 10. In the experiment, we divided the daily positive cases into two groups; first, controllable- this determines how many cases can be prevented by using the proposed graph coloring method; second, uncontrollable - this represents how many cases cannot be prevented by the proposed method. The number of past days is set to 7 because as per the WHO report, seven days is the minimum time frame for affected persons to show symptoms of COVID. The uncontrollable value is fed into the LSTM to determine the spread rate. The mean square error (MSE) is used to train the LSTM model; the equation for MSE is shown in the following equation:
(9)MSE=1n∑i=1nyi−y¨i2.where Yi denotes the actual value. This can be calculated as the number of people who are infected when the proposed graph coloring algorithm is used. Yi denotes the predicted value by the LSTM model. Figure 15 shows LSTM model to predict the reduction of spread rate.Figure 15
LSTM model to predict the reduction of spread rate.Figure16 shows the prediction of LSTM and the reduction of the growth rate when the proposed graph coloring approach is used. All the data used in this experiment is shown in Table 5.Figure 16
Growth rate comparison.Table 5
Experiment setup.
SetupPopulationNsmMax # of daysSpread ratioSetup1Setup2400000400000250400202515154.013.23


## 6. Discussion

In the corona pandemic time, it is advised to the citizens to avoid crowded places as there are more chances to get infected from the disease. Lockdowns are one of the most followed practices to avoid people gatherings and community events. However, lockdowns cause a massive economical downslide to families across the nation. Moreover, the government is taking steps to provide relief funds to the public to help them from the economic problem. There is a high chance that the social distancing will not be followed during the relief scheme operation. Hence, the government should plan the process of relief scheme properly and direct the support staff about the social distancing instructions. In this paper, we provide a graph coloring approach that helps the government to schedule the timings of the relief funds. Each color in the graph represents unique days or time, so the number of colors in the graph indicates the number of minimum days required for the government to schedule the relief scheme program shown in Figure17. Consider a real-time example of elections where all people need to visit some common places to cast the vote. In that case, the proposed method can be useful in determining how many support staffs are need in each constituency. In this example, each constituency can be considered as one dummy node.Figure 17
The spread of the disease. Blue dots indicate the absence of the COVID-19, and the red dots represent the presence of the disease. (a), (b), (c), and (d) denote the spread at different times when the proposed system is not used. The images at (e), (f), (g), and (h) show how the spread is controlled after the proposed system is implemented.
(a)(b)(c)(d)(e)(f)(g)(h)


## 7. Conclusion

India is the second-largest populous country in the world. The available less number of support staff makes it difficult to maintain social distancing during relief schemes. In this paper, the paper has proposed a graph coloring algorithm that can help the government to open ATMs and banks according to the available support staff efficiently. The proposed algorithm has been tested on synthetic datasets by changing the values of population and availability of support staff, and the possibility of social distancing has been validated. The algorithm also recommends how many support staff are required to conduct relief schemes smoothly. In the end, the ultimate goal of maintaining social distancing is achieved. The merit of the proposed work is as follows: first, the governments can plan in advance before providing any relief scheme; second, the availability of support staff can be organized based on the need; and third, the positive cases can be controlled widely. In future work, we aim to enhance the graph coloring algorithm by migrating the excess staff to neighboring districts.



---

*Source: 8131193-2022-08-12.xml*