key: cord-0552353-qev9sryo
authors: Wu, Zhijun
title: Social Distancing as a Network Population Game in a Socially Connected World
date: 2020-05-26
journal: nan
DOI: nan
sha: d1b055ebd5bb47e69754907011176c73cfd5835b
doc_id: 552353
cord_uid: qev9sryo

While social living is considered to be an indispensable part of human life in today's ever-connected world, social distancing has recently received much public attention on its importance since the outbreak of the coronavirus pandemic. In fact, social distancing has long been practiced in nature among solitary species, and been taken by human as an effective way of stopping or slowing down the spread of infectious diseases. Here we consider a social distancing problem for how a population, when in a world with a network of social sites, such as schools, restaurants, shopping centers, residential areas, etc., decides to visit or stay at some sites while avoiding or closing down others so that the social contacts across the network can be minimized. We model this problem as a network population game, where every individual tries to find some network sites to visit or stay so that he/she can minimize all his/her contacts. In the end, an optimal strategy can be found for every one, when the resulting distribution of the population over the network reaches an equilibrium. We show that a large class of equilibrium strategies can be obtained by selecting a set of network sites that forms a so-called maximal r-regular subnetwork. The latter includes many well studied network types, such as the maximal independent set (r=0), the maximal strong matching (r=1), the maximal set of independent cycles (r=2), etc. They are easy to identify or construct, and can be completely disconnected (with r = 0) for the most strict isolation, or allow certain degree of connectivities (with r>0) for more flexible distancing. We derive the equilibrium conditions of these strategies, and analyze their rigidity and flexibility on different types of r-regular subnetworks. We provide an overview on algorithms that can be used for computing maximal r-regular subnetworks and their associated distancing strategies.

Humans participate in all sorts of social activities, especially in modern societies. We go to school, go to work, attend meetings, go shopping, go to restaurants, watch shows, movies, or sports, etc. The world is formed by a huge number of social sites that host these activities. These sites are closely connected for people to contact, meet, and socialize. The world is a well-connected network. People's daily life is simply a busy agenda of events at different event sites in this network, with different visiting frequencies for different sites. As such, the world can be modeled as a social network, with the nodes representing the social sites and the links the contacts across the social sites. The social life of an individual can be described by the frequencies of the individual to visit 1/22 arXiv:2005.12506v1 [cs.SI] 26 May 2020 these social sites, and the social behavior of the population can be described by these frequencies averaged over the whole population.

Mathematically, we can represent a social network with a graph G = (V, E), where V = {1, . . . , n} is a set of nodes corresponding to the social sites of the network, and E = {(i, j) : i and j connected} a set of links between the nodes representing social contacts that can be made between different social sites. Let x ∈ R n , x ≥ 0, Σ i x i = 1, be a vector describing the social behavior of an individual on G, with x i being the frequency of the individual to visit or stay at node i of G. Then, we can define a vector y ∈ R n , y ≥ 0, Σ i y i = 1, for the social behavior of the whole population, with y i being the average frequency of the population to visit or stay at node i of G. Let A be the adjacency matrix of G, A i,j = 1 if (i, j) ∈ E, A i,j = 0 if (i, j) ∈ E, and A i,i = α ∈ [0, 1] for all i = 1, . . . , n. Then, in a y-population, the amount of social contacts an x-individual can make on node i must be x i Σ j A i,j y j , and across the network be Σ i x i Σ j A i,j y j = x T Ay.

Consider x as the social strategy of an individual, and y the social strategy of the population. Consider π(x, y) = x T Ay as a payoff function. We can then define a network population game where each individual of the population tries to maximize his/her social payoff. The latter can be achieved when an optimal strategy x * is found for every individual. The strategy for the population then becomes x * as well, and a Nash equilibrium is reached. A Nash equilibrium of this game is thus a strategy x * such that

where S = {x ∈ R n : Σ i x i = 1, x i ≥ 0, i = 1, . . . , n} is the set of all possible social strategies. We call this game a social networking game on network G. For social networking, we encourage interactions across different social sites and do not count the contacts among individuals in the same sites, and therefore, set A i,i = 0 for all i = 1, . . . , n. Different from social networking, social distancing is to reduce social contacts instead. Therefore, for a given social network, social distancing can be considered as a problem to find a set of social sites in the network where interactions within and between these sites can be minimized. It can therefore be modeled as a network population game where each individual tries to minimize his/her social contacts π(x, y) = x T Ay. A Nash equilibrium of this game is then a strategy x * such that π(x * , x * ) ≤ π(x, x * ), ∀x ∈ S.

(2)

We call this game a social distancing game on network G. For social distancing, we also count the contacts among individuals in the same sites, and therefore, set A i,i = 1 for all i = 1, . . . , n. LetḠ = (V ,Ē) be the complement of G, withV = V and E = {(i, j) : (i, j) ∈ E}. Then, it is easy to see that a social distancing game on network G is equivalent to a social networking game onḠ, and vice versa (See Fig.1 ). Social distancing is not necessarily a common social norm in human societies, but it recently gains much public attention on its importance since the outbreak of the coronavirus pandemic [1, 2] . In nature, social distancing has long been practiced among solitary animals, who always try to distance themselves from others, sometimes for more efficient foraging, sometimes for self-protection from infightings, and sometimes for avoiding disease infections as well [3, 4] . In human societies, social distancing has been recommended by health experts as a special yet effective measure for mitigating the spread of diseases during epidemic or pandemic [5] [6] [7] . It can be as simple as just to keep distances from each other, or be more cooperative to follow certain rules such as avoiding large gatherings, canceling events, and closing schools, or to shut down places such as movie theaters, shopping centers, and commercial areas [8, 9] .

Much work has been done on modeling social distancing in the past [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] and especially in recent months since the outbreak of the coronavirus pandemic [21] [22] [23] [24] [25] [26] , most focusing on epidemiological models and predictions, with social distancing as a behavioral factor affecting the spread of the diseases. The impacts of distancing behaviors on contact rates, transmission rates, and hence the infectious rates have been investigated through statistical estimate, dynamic simulation, and model prediction. Our work focus more on planning of social distancing for a population on how to separate, what to avoid, and where to stay to minimize social contacts and mitigate the spread of the diseases. More specifically, we consider a social distancing problem for how the individuals of a given population, when in a world with a network of social sites, find some sites of the network to visit or stay while avoiding or closing down others so that the social contacts among the individuals across the network can be minimized. This can be critical as a personal decision to make, and perhaps more so as a public health policy to implement. This problem can be modeled as a network population game as conditioned in (2), where every individual tries to find some network sites to visit or stay so that he/she can minimize all his/her contacts. In the end, an optimal strategy can be found for every one, when the resulting distribution of the population over the network reaches an equilibrium. The network sites on which the population is distributed at equilibrium form a subnetwork. We show that a large class of equilibrium strategies can be obtained by distancing on a maximal r-regular subnetwork. A regular subnetwork is a subnetwork of all nodes of equal degree. A r-regular subnetwork is a subnetwork of all nodes of degree r [27, 28] (see Fig. 2 ). The latter includes many well studied network types, such as the maximal independent set (r = 0), the maximal strong matching (r = 1), the maximal set of independent cycles (r = 2), etc. They are easy to identify or construct, and can be completely disconnected (with r = 0) for the most strict isolation, or allow certain degree of connectivities (with r > 0) for more flexible distancing. We derive the equilibrium conditions of these strategies, and analyze their rigidity and flexibility on different types of r-regular subnetworks. We provide an overview on algorithms that can be used for computing maximal r-regular subnetworks and their associated distancing strategies. Our work do share some important features with other previous studies. For example, Reluga and co-workers [17, 20, 29, 30] have also applied a game dynamic approach to the study of social distancing. Their game involves the investment on social distancing and its effect on the dynamics of SIR populations. Our game is instead for choosing locations for social distancing in a given network of social sites. Eubank et al. [10, [31] [32] [33] [34] have started investigating network based models in early 2000, and analyzed and simulated large social networks and their impacts on epidemics. Meyers et al. [13, [35] [36] [37] [38] have led multiple efforts on contact network based epidemic modeling, mostly concerning networks of person-to-person contacts. The networks studied in our work can be considered as a special type of contact networks, where the nodes are locations, and the contacts are made through access to the connected locations. 

For social distancing on a network, every individual wants to find a network site to distance himself/herself from others. In an attempt, a site with a small number of connections may be a good choice. However, if everyone chooses this site, no one will benefit. Therefore, a strategy is needed to select a set of sites to visit or stay with only certain frequency at each. Let x * ∈ S be a strategy with x * j being the frequency of visiting or staying at site j. In effect, the population will distribute on the network also as x * , with x * j being the probable fraction on site j. With the population distributed as such, the social contact an individual at site i can make with the population at site j will be A i,j x * j . If there is a link between i and j, i.e.,

In total, the social contact this individual can make, if at site i, will be

The competition among all the sites is then balanced if p i (x * ) are the same, say equal to λ * , for all i such that x * i > 0, i.e., for all the sites selected to visit or stay. In addition, λ * must be smaller than or equal to p i (x * ) for all i such that x * i = 0, i.e., for all the sites not selected, for otherwise, by selecting such a site i such that p i (x * ) < λ * , the individual will be able to reduce the social contact further. When all these conditions are satisfied, every individual with a strategy x * minimizes all his/her social contacts to Σ i x * i p i (x * ) = λ * , no more, no less, and an equilibrium is reached.

Based on evolutionary game theory [39, 40] , we can prove that the above conditions are in fact necessary and sufficient for a strategy x * to be a Nash equilibrium of the social distancing game on a network. We state this property in the following theorem. Theorem 1. Let A be the adjacency matrix of network G. Then, a strategy x * ∈ S is a Nash equilibrium of the social distancing game on G if and only if there is a scalar λ * such that p i (x * ) = λ * for all i such that x * i > 0 and p i (x * ) ≥ λ * for all i such that

Therefore, x * is a Nash equilibrium.

(⇒): Assume that x * is a Nash equilibrium. Then, π(x, x * ) ≥ π(x * , x * ) for all x ∈ S. Let λ * = π(x * , x * ). Then, π(e i , x * ) ≥ λ * for all i, i.e., p i (x * ) ≥ λ * for all i. It follows

Let V * be the set of nodes in G selected by a strategy x * , i.e., V * = {i ∈ V : x * i > 0}. Let E * be the set of links between the nodes in V * , i.e., E * = {(i, j) ∈ E : i, j ∈ V * }. We call G * = (V * , E * ) the subnetwork of G supporting x * . For an individual, an equilibrium strategy x * on G * then means to visit or stay only at the nodes of G * , with a nonzero frequency x * i at node i of G * , while for the population, it implies to spread only on the nodes of G * , with a nonzero probable fraction x * i on node i of G * . In either view, strategy x * with a choice of nodes in G * maximizes the social distances and minimizes the social contacts among all the individuals of the population, if a link between two nodes is counted as a contact while no link as a distance.

The equilibrium strategy for the social distancing game on a network is not necessarily unique. Different equilibrium strategies may have different minimal social contacts. In general, the fewer connections in supporting subnetwork G * , the smaller amount of social contacts at equilibrium. Therefore, an equilibrium strategy without connections in G * can be a first choice for distancing. Such a G * is called an independent set of G. It is easy to verify that the larger the independent set, the better the corresponding strategy, when a larger amount of social contacts is minimized. The largest possible independent set that is not contained in another independent set is called a maximal independent set. In fact, a distancing strategy on an independent set of G is not necessarily a Nash equilibrium, but it always is if it is on a maximal independent set of G.

Theorem 2. Let x * ∈ S be a strategy for the social distancing game on a network G = (V, E). Let G * = (V * , E * ) be the supporting subnetwork for x * . Then, if G * is a maximal independent set of G, x * is a Nash equilibrium for the game, with x * i = 1/k for all i ∈ V * and x * i = 0 for all i ∈ V \V * , where k is the size of V * . Proof. Assume without loss of generality that G * = (V * , E * ) with V * = {1, . . . , k}. Then, A i,j = 0 for all i, j = 1, . . . , k, i = j and A i,i = 1 for all i = 1, . . . , k. Since

Since G * is a maximal independent set, for any i ∈ V \V * , there must be l ∈ V * such that i and l are connected, i.e., (i, l) ∈ E and A i,l = 1. Therefore, for any i ∈ V \V * , p i (x * ) = Σ j A i,j x * j ≥ x * l = λ * . By Theorem 1, x * is a Nash equilibrium.

Note that if G * is an independent set of G but not a maximal one, there will be i ∈ V \V * not connected with any j ∈ V * and p i (

Then, x * cannot be a Nash equilibrium. Theorem 2 suggests that if there is a maximal 5/22 independent set of nodes in the network, an optimal distancing strategy for an individual will be to choose only this set of nodes to visit or stay with an equal frequency 1/k for each node, where k is the size of the set. As a result, the population will then be distributed only on this set of nodes with an equally probable fraction 1/k on each node. At equilibrium, every individual minimizes his/her total amount of social contacts to λ * = 1/k. Therefore, the larger the maximal independent set, the better for minimizing the social contacts, and the strategy on a maximum independent set will be the best among all those supported by a maximal independent set. Figure 3 shows an example network, representing a world of 10 connected social sites. The inside 5 sites, {1, 2, 3, 4, 5}, may be town centers, well connected. The outside 5 sites, {6, 7, 8, 9, 10}, may be residential areas, each having access to some of the town centers. In this network, the sites {3, 5, 9} form a maximal independent set. An equilibrium strategy x * can be reached on this set of sites, with x * 3 = x * 5 = x * 9 = 1/3 and all other elements x * j = 0, and a minimal social contact λ * = 1/3. However, the sites {6, 7, 8, 9, 10} form another maximal independent set. An equilibrium strategy x * can be reached on this set of sites, with x * 6 = x * 7 = x * 8 = x * 9 = x * 10 = 1/5 and all other elements x * j = 0, and a minimal social contact λ * = 1/5. The latter is an even better strategy than the former. An equilibrium strategy x * can be reached on this set of sites, with x * 3 = x * 5 = x * 9 = 1/3 and all other elements x * j = 0, and a minimal social contact λ * = 1/3. However, the sites {6, 7, 8, 9, 10} form another maximal independent set. An equilibrium strategy x * can be reached on this set of sites, with x * 6 = x * 7 = x * 8 = x * 9 = x * 10 = 1/5 and all other elements x * j = 0, and a minimal social contact λ * = 1/5. The latter is an even better strategy than the former.

An equilibrium strategy may as well be supported by a subnetwork where there are some connections among the nodes. A general class of subnetworks that may be selected by an equilibrium strategy is the regular networks. In a regular network, all nodes have the same number of connections with other nodes. In other words, all the nodes of a regular network have the same degree. If the degree is r, the network is called a r-regular network. Thus, a maximal independent set of a given network is a 0-regular network. A 1-regular network is where each node is connected only to another one; a 2-regular network is where each node is connected to two other nodes; and so on and so forth (see Fig. 2 ).

A regular network can be connected or disconnected. In the latter case, it consists 6/22 of a number of disconnected components, each being a regular network itself. For a r-regular subnetwork of G, the larger the subnetwork, the sparser the connectivity, and the better for social distancing. The largest possible r-regular subnetwork that is not a disconnected part of another r-regular subnetwork is called a maximal r-regular subnetwork. A distancing strategy on an r-regular subnetwork may not necessarily be an equilibrium strategy, but it always is if it is on a maximal r-regular subnetwork and if there is no less than r + 1 connections to the subnetwork from an outside node.

Theorem 3. Let x * ∈ S be a strategy for the social distancing game on a network G = (V, E). Let G * = (V * , E * ) be the supporting subnetwork for x * . Then, if G * is a maximal r-regular subnetwork and if there is no less than r + 1 links to G * from a node i ∈ V \V * , x * is a Nash equilibrium for the game, with

. . , k} is the adjacency matrix of G * , and each of its rows and columns has exactly r + 1 elements equal to 1.

By adding all these equations, we obtain r + 1 = kλ * , and λ * = (r + 1)/k. By solving the equations for x * i , for all i ∈ V * , we also have

Theorem 3 suggests that if there is a maximal r-regular subnetwork in the network, an optimal distancing strategy for an individual will be to choose only this subnetwork to visit or stay with an equal frequency 1/k for each node of the subnetwork, where k is the number of the nodes in the subnetwork. As a result, the population will then be distributed only on this subnetwork with an equally probable fraction 1/k on each node of the subnetwork. At equilibrium, every individual minimizes his/her total amount of social contacts to λ * = (r + 1)/k. Therefore, the larger the regular subnetwork or the smaller the r value, the better for minimizing the social contacts.

Of particular interest among maximal regular subnetworks are those with a large number of disconnected components. For example, a maximal 1-regular subnetwork is just a set of disconnected 1-regular subnetworks of size 2; a maximal 2-regular subnetwork can be a large number of disconnected 2-regular subnetworks of size 3; etc. An equilibrium strategy on such a subnetwork means that the population can spread on a large number of independent locations, where at each location, there is a group of social sites with a low degree of connectivity. Such a strategy allows certain degree of local contacts yet keeps maximal possible distances among individuals, and can therefore be considered as a more flexible strategy for social distancing than those on maximal independent sets. Figure 4 shows a network similar to the one in Fig. 3 except for some changes in contact connections. In this network, the sites {1, 2, 3, 4, 5} form a 2-regular subnetwork. However, a strategy on this subnetwork cannot be an equilibrium strategy because there are nodes outside the subnetwork, say node 6, with less than 3 connections to the nodes in the subnetwork. For the same reason, a strategy on the 2-regular subnetwork formed by the sites {6, 7, 8, 9, 10} cannot be an equilibrium strategy, either. On the other hand, the whole network itself is a 3-regular network. An equilibrium strategy x * can be reached on the whole network with x * i = 1/10 for all i = 1, . . . , 10, and a minimal social contact λ * = 2/5.

In the network in Fig. 4 , there are also equilibrium strategies supported by other regular subnetworks. For example, the sites {1, 2, 4, 8, 9, 10} form a 1-regular subnetwork of size 6. An equilibrium strategy x * can be reached on this subnetwork with x * 1 = x * 2 = x * 4 = x * 8 = x * 9 = x * 10 = 1/6 and all other elements x * j = 0, and a minimal social contact 7/22 λ * = 1/3. There are total 5 such equilibrium strategies on this network. Furthermore, the sites {3, 5, 6, 7} form a maximal independent set of sites or in other words, a 0regular subnetwork. An equilibrium strategy x * can be reached on this set of sites with x * 3 = x * 5 = x * 6 = x * 7 = 1/4 and all other elements x * j = 0, and a minimal social contact λ * = 1/4. There are total 4 such equilibrium strategies on this network. In terms of minimal social contact, among these strategies, the one on the maximal independent set, i.e., on a 0-regular subnetwork, is the best, because its social contact is the lowest. However, it is also the most strict strategy, for it does not allow any contacts across different sites. The strategy on the whole network, i.e., on a 3-regular network, has the highest social contact, but it is the most flexible strategy, allowing certain degree of contacts across different sites. In general, a network may have a collection of disconnected r 1 , r 2 , . . . , r m -regular subnetworks, where r 1 > r 2 > · · · > r m . A maximal collection of regular subnetworks is a collection that is not contained in a larger one of the same types of regular subnetworks. A distancing strategy on a maximal collection of regular subnetworks can be an equilibrium strategy if there is no less than r 1 + 1 connections to the nodes in the collection from an outside node. Such a strategy again means that the population can spread on a large number of independent locations, where at different locations, there can be different types of r-regular subnetworks. Such strategies provide even more flexibilities for local contacts than those on a single type of regular subnetworks.

Theorem 4. Let x * ∈ S be a strategy for the social distancing game on a network G = (V, E). Let G * = (V * , E * ) be a maximal collection of r 1 , r 2 , . . . , r m -regular subnetworks of G, where r 1 > r 2 > · · · > r m . Let G * i = (V * i , E * i ) be the r i -regular subnetwork in G * . Then, if x * is supported by G * and if there is no less than r 1 + 1 links to G * from a node i ∈ V \V * , x * is a Nash equilibrium for the game, with x * j = λ * /(r i + 1) for all j ∈ V * i , i = 1, . . . , m, and x * i = 0 for all i ∈ V \V * , where λ * = 1/(k 1 /(r 1 + 1) + k 2 /(r 2 + 1) +

· · · + k m /(r m + 1)) with k i being the size of V * i .

Proof. Assume without loss of generality that V * = {1, . . . , k}, and V * 1 = {1, . . . , k 1 }, V * 2 = {k 1 + 1, . . . , k 1 + k 2 }, and so on and so forth. Let A (i) be the adjacency matrix of G * i . Then, in each row and column of A (i) , there are exactly r i + 1 elements equal to 1. Let p j (x * ) = Σ l A j,l x * l = λ * for all j ∈ V * i . Then, Σ l∈V * i A j,l x * l = λ * for all j ∈ V * i . By adding these equations for all j ∈ V * i , we obtain (r i + 1)Σ j∈V * i x * j = k i λ * or equivalently, Σ j∈V * i x * j = λ * k i /(r i + 1) for all i = 1, . . . m. By adding the latter equations, we obtain λ * = 1/(k 1 /(r 1 + 1) + · · · + k m /(r m + 1)). By solving these equations for all x * j , we also have x * j = λ * /(r i + 1) for all j ∈ V * i . Since there is no less than r 1 + 1 links to G * from a node l ∈ V \V * ,

i.e., p l (x * ) ≥ λ * for all l ∈ V \V * . By Theorem 1, x * is a Nash equilibrium.

The equilibrium strategies supported by regular subnetworks are easy to identify or construct, and represent a large class of distancing strategies on subnetworks of zero to certain degree of connectivities, which can be adopted for different levels of distancing practice. However, in principle, an equilibrium strategy can be supported by a general subnetwork as long as the necessary and sufficient conditions in Theorem 1 are satisfied. A so-called Snow-Shapley algorithm can then be applied to compute the equilibrium strategy [43, 44] : Let x * be the strategy on G * = (V * , E * ). Assume that V * = {1, . . . , k}. Let Then, by solving this system of equations, we can obtain x * + . If in addition, A * − x * + ≥ λ * e − , where e − is a vector of all 1's of size n − k + 1, then by Theorem 1, x * is a Nash equilibrium. Since the subnetworks supporting general equilibrium strategies may not have special structures and the strategies are also more complicated to compute, in this paper, we focus only on equilibrium strategies on regular subnetworks.

Once an equilibrium is reached, i.e., a distancing rule is established, can we make some small changes or adjustments on the strategy? This is a question of legitimate concern in practice, for we may not be able to commit to a rule all the time. The answer to the question is that it depends on whether the social contact is changed: if the contact is increased with small changes in the strategy, the rule needs to be enforced, and we say the strategy is rigid; if the contact is not changed, the rule is not strict, and we say the strategy is flexible; if the contact is decreased, the rule is broken, and we say the strategy is fragile. In order to further address this issue, we give a formal definition for rigidity, flexibility, and fragility for a distancing strategy in the following. We then analyze the strategies on r-regular subnetworks with these properties.

Let x * ∈ S be an equilibrium strategy for the social distancing game on network G. Let G * be the subnetwork supporting x * . Let S * = {x ∈ S : x i > 0 for all i such that x * i > 0}. Then, S * is the set of strategies all supported by G * . We define rigidity, flexibility, and fragility of x * only for small changes of x * in S * . Let P * = {p ∈ R n : p =

x − x * , x ∈ S * , x = x * }. Then, p ∈ P * is a direction such that x * + p, a small change of x * along p, remains in S * for all > 0 sufficiently small. Definition 1. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G supported by subnetwork G * . Then, x * is said to be strongly rigid on G * if for any p ∈ P * , π(x * + p, x * + p) > π(x * , x * ) for all > 0 sufficiently small. Definition 2. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G supported by subnetwork G * . Then, x * is said to be weakly rigid on G * if for any p ∈ P * , π(x * + p, x * + p) ≥ π(x * , x * ) for all > 0 sufficiently small. Definition 3. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G supported by subnetwork G * . Then, x * is said to be flexible on G * if there is p ∈ P * such that π(x * + p, x * + p) = π(x * , x * ) for all > 0 sufficiently small. Definition 4. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G supported by subnetwork G * . Then, x * is said to be fragile on G * if there is p ∈ P * such that π(x * + p, x * + p) < π(x * , x * ) for all > 0 sufficiently small.

Recall that π(x, x) is the social contact of the population of strategy x. Therefore, the definition of rigidity basically implies that an equilibrium strategy x * is strongly (or weakly) rigid if it is a strict (or non-strict) local minimizer of the social contact π(x, x) in S * . In this sense, the strong (or weak) rigidity can be considered as a weaker version of strong (or weak) evolutionary stability for general evolutionary games [39, 40] . Nonetheless, we define this property as rigidity instead of stability because the corresponding strategy is considered as a rigid distancing rule in the context of social distancing. Note that based on the above definitions, if an equilibrium strategy is weakly rigid, it must be flexible; however, if it is flexible, it may not necessarily be weakly rigid; It could be fragile.

We now investigate these properties for strategies on regular subnetworks. First, it is easy to justify that the equilibrium strategies on a maximal independent set are all strongly rigid: Small changes on such strategies always increase the social contacts. In other words, there will be penalties for any changes on such strategies. On the other hand, the equilibrium strategies on any r-regular subnetworks with r > 0 are always flexible: In this case, we can find some connected nodes in the subnetworks. By increasing the frequencies on some of these nodes while decreasing on others, we can make some small changes on the strategy without changing the original amount of social contacts. Of these flexible strategies, some may be weakly rigid, but others may be fragile.

Theorem 5. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G = (V, E). If x * is supported by a maximal independent set G * = (V * , E * ), then x * is strongly rigid on G * .

Proof. Let x * + p be a change from x * for any p ∈ P * and > 0 sufficiently small. Then,

Note that p = x − x * for some x ∈ S * , x = x * . Therefore, p = 0, but p i = 0 for i ∈ V \V * , and Σ i∈V * p i = 0. Note also that (Ax * ) i = λ * for all i ∈ V * and therefore, p T Ax * = Σ i∈V * p i (Ax * ) i = 0. In addition, since G * is a maximal independent set, {A i,j , i, j ∈ V * }, the adjacency matrix of G * , is an identity matrix. Therefore, p T Ap = Σ i,j∈V * p i A i,j p j = Σ i∈V * p 2 i > 0. It follows that π(x * + p, x * + p) = x * T Ax * + 2 p T Ap > x * T Ax * = π(x * , x * ). By Definition 1, x * is strongly rigid on G * . Theorem 6. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G = (V, E). If x * is supported by a maximal r-regular subnetwork G * = (V * , E * ) with r > 0, then x * is flexible on G * .

Proof. Since G * is a r-regular subnetwork with r > 0, there must be i, j ∈ V * such that (i, j) ∈ E * and A i,j = 1. Let p be a vector such that p i = −p j = δ with 0 < δ < min{1 − x * i , x * j } and p l = 0 for all l = i, j. Then, p ∈ P * . Let x * + p be a change from x * along p for > 0 sufficiently small. Then,

By Definition 3, x * is flexible on G * .

Based on Theorem 5 and 6, for the example distancing problem shown in Fig. 4 , the equilibrium strategy on a maximal independent set such as {3, 5, 6, 7} is strongly rigid, and the one on a maximal 1-regular subnetwork such as {1, 2, 4, 8, 9, 10} is flexible. The equilibrium strategy on the whole network, which is a 3-regular network, is also flexible. Therefore, as described in the proof for Theorem 6, for this strategy, the frequencies can be exchanged between any two connected nodes, say node 1 and 2, by moving a small amount from one node to another. For example, by moving 1/20 from node 1 to node 2, the frequency on node 1 decreases to 1/20 from 1/10 while on node 2 increases to 3/20 from 1/10, yet the minimal social contact for every individual remains to be 2/5.

Note that an r-regular network must have at least r + 1 nodes. We call an r-regular network of size r + 1 a minimal r-regular network. A minimal r-regular network must be a complete network, i.e., each node is connected with all others in the network. It turns out that an equilibrium strategy for the social distancing game on a network is always weakly rigid if it is supported by a maximal r-regular subnetworks whose components are all minimal r-regular subnetworks with r > 0: Theorem 7. Let x * ∈ S be an equilibrium strategy for the social distancing game on network G = (V, E). Then, x * is weakly rigid if it is supported by a maximal r-regular subnetwork G * = (V * , E * ) whose components are all minimal r-regular subnetworks with r > 0.

be the ith r-regular subnetwork in G * and A (i) the adjacency matrix of G * i , i = 1, . . . , m. Then, A (i) is a matrix of all 1's. Let x * + p be a change from x * for any p ∈ P * and > 0 sufficiently small.

Note that p = x − x * for some x ∈ S * , x = x * . Therefore, p = 0, but p i = 0 for i ∈ V \V * , and Σ i∈V * p i = 0. Note also that (Ax * ) i = λ * for all i ∈ V * and therefore,

It follows that

By Definition 2, x * is weakly rigid on G * .

From the above proof, we see that if we update x * with a vector p such that Σ j∈V * i p j = 0 for all i = 1, . . . , m, we will have p T Ap = 0, and hence (x * + p) T A(x * + p) = x * T Ax * , i.e., the minimal social contacts will remain to be the same. This means that we can make such small changes in frequencies on the subnetwork components independently without changing the original amount of social contacts across the network. In fact, we can make such changes on any group of supporting components as long as they are minimal regular subnetworks. Figure 5 shows an example network with 16 social sites. It is structured like a small town, with 4 connected town centers in the middle and 4 separated residential areas outside around. Each residential area consists of 3 well-connected activity sites, each having access to one of the town centers. The social distancing game on this network has at least three equilibrium strategies: one on the maximal 0-regular subnetwork or in other words, the maximal independent set {5, 6, 7, 8} with the minimal social contact equal to 1/4; one on the maximal 1-regular subnetwork {9, 10, 11, 12, 13, 14, 15 , 16} with the minimal social contact equal to 1/4; and one on the maximal 2-regular subnetwork {5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 , 16} with the minimal social contact equal to 1/4. The minimal social contacts of the three strategies are all the same. However, based on Theorem 5, 6, and 7, the first one is strictly rigid; the second and third are flexible and only weakly rigid. In addition, the supporting subnetworks for the second and third strategies consist of disconnected minimal regular subnetworks. The frequencies on those minimal subnetworks can be adjusted independently without affecting the social contacts of the individuals. For example, for the third strategy, for each minimal 2-regular subnetwork component, say the subnetwork {5, 9, 10}, a small fraction 1/24 can be moved from each of the outer most two sites, say the sites 9 and 10, to the inner site, say the site 5. The fractions on the outer sites are then decreased from 1/12 to 1/24 while on the inner site is increased from 1/12 to 4/24. However, such changes will not affect the original minimized social contact of the population.

Finally, if an r-regular subnetwork is connected but not minimal, or disconnected but at least one of the components is not minimal, then an equilibrium strategy supported by such a subnetwork will not be weakly rigid though still flexible. It will in fact be fragile, i.e., there will be a certain way to update the strategy on the subnetwork to decrease the social contacts among the individuals. Such changes will make the population to break away from the current equilibrium state. An example fragile strategy is the one on the whole network for the game shown in Fig. 4 . The whole network is a 3-regular network, but it is not minimal.

Theorem 8. Let x * ∈ S be an equilibrium strategy for the social distancing game on a network G = (V, E) supported by an r-regular subnetwork G * = (V * , E * ), r > 0. If G * is connected but not minimal, or disconnected but at least one of its components is not minimal, then x * is fragile on G * .

Proof. Without loss of generality, we consider only the case where G * is connected. If G * is not a minimal r-regular subnetwork, there must be three nodes i, j, l such that (i, l), (j, l) ∈ E * , but (i, j) ∈ E * . Let p be a vector such that p k = 0 for all k = i, j, l, p i = p j = δ, with 0 < δ < min{1 − x * i , 1 − x * j , x * l /2}, and p i + p j + p l = 0. Then, p ∈ P * . Let x * + p be a change from x * along p ∈ P * for > 0 sufficiently small. Then,

Note that (Ax * ) i = λ * for all i ∈ V * , and therefore,

Note also,

By Definition 4, x * is fragile on G * .

The above results can be extended to analyzing the rigidity, flexibility, and fragility of distancing strategies supported by a more general type of subnetwork such as a maximal collection of mixed regular subnetworks. However, we will not further expand our discussions on these topics.

Computation of optimal distancing strategies is straightforward if the supporting subnetworks are determined, especially for r-regular subnetworks. However, to find a r-regular 13/22 subnetwork is not always trivial. It is well known that the problem to find the maximum 0-regular subgraph, i.e., the maximum independent set of a given graph is NP-hard [45] . The problem to find the maximum 1-regular subgraph of a given graph, known as the maximum strong matching problem, is also NP-hard [46, 47] . In fact, Cardoso et al proved that the problem to find the maximum r-regular subgraph of a given graph is NP-hard for any r ≥ 0 [48] . Fortunately, for our purpose, we do not have to find the maximum r-regular subnetwork. A maximal r-regular subnetwork would be sufficient to support an equilibrium distancing strategy, which is relatively easier to find than the maximum one. Here we provide an overview on algorithms that can be used for computing maximal r-regular subnetworks and their associated distancing strategies. They are not necessarily optimized, but do contain the essential steps, and are easy to understand and follow.

We consider the maximal r-regular subnetworks with r = 0, r = 1, r = 2, and r ≥ 3 separately, for each case has some special features. At the beginning of each algorithm, the nodes of the network are assumed to be ordered according to certain priority. The nodes with higher priority will then have a higher probability to be selected as distancing sites. Once a maximal r-regular subnetwork is found, a strategy can be defined on it, which satisfies a condition, we call the equality condition, that the social contacts at the nodes of the subnetwork are all equal. However, an additional condition, we call the inequality condition, also needs to be satisfied, i.e., the social contacts at the nodes outside the subnetwork must all be greater than or equal to those at the nodes of the subnetwork. The latter condition is equivalent to that the nodes not in the subnetwork have greater than or equal to r + 1 connections with the nodes in the subnetwork. Therefore, in each algorithm, there are two major steps: first to find a maximal r-regular subnetwork, and second to make sure that each node not in the subnetwork has greater than or equal to r + 1 connections with the nodes in the subnetwork.

Let the network be given by G = (V, E). Assume that a maximal r-regular subnetwork is to be found and be stored in G * = (V * , E * ). The algorithm in Frame 1 is for computing the distancing strategy on a maximal 0-regular subnetwork. It is equivalent to find a maximal independent set of nodes in the given network. The algorithm is based on the classical greedy algorithm for finding a single maximal independent set of a given graph [49, 50] . It starts from selecting a node from the network and removing all the nodes connected to it. The algorithm then repeats the same procedure for the rest of the network until no more nodes left. The selected nodes form a maximal independent set or in other words, a maximal 0-regular subnetwork G * . Let k be the number of nodes in the subnetwork, i.e., k = |V * |. Then, x * i = 1/k for all i ∈ V * and x * i = 0 for all i ∈ V \V * . Note that in each iteration, the algorithm needs to examine the links and remove the connected nodes. The total number of operations is proportional to the number of links in the network, which is in the order of m = |E|. Note that in every iteration, if a different node is selected, a different maximal independent set may be found in the end. This is why it would be much more costly if a maximum independent set is to be found, which in principle requires to find all the maximal independent sets and choose the largest one among them. Finally, in this algorithm, once the maximal independent set is found, the equilibrium strategy can be defined. It does not need to check the inequality condition, because any node not in the maximal independent set must have at least one connection to the nodes in the set.

The algorithm in Frame 2 is for computing the distancing strategy on a maximal 1-regular subnetwork. This is equivalent to finding a maximal strong matching in the given network, i.e., a maximal set of pairs of connected nodes, with no direct connection between any two pairs of nodes [46] . The algorithm is again a greedy type for we do not need to find the maximum strong matching. It starts from selecting a pair of connected nodes in the network and removing all the nodes connected to them. It then Select i ∈ U . 3.

Remove all j from U , (i, j) ∈ E.

Move i from U to U * . 5. End 6. V * = U * repeats the same procedure for the rest of the network until no pairs of connected nodes left. The selected pairs of nodes form a maximal strong matching or in other words, a maximal 1-regular subnetwork G * . Let k be the number of nodes in the subnetwork, i.e., k = |V * |. Then, x * i = 1/k for all i ∈ V * and x * i = 0 for all i ∈ V \V * . Note that in each iteration, the algorithm again needs to examine the links to the selected pair of nodes and remove the connected nodes. The total number of operations is proportional to the number of links in the network, which is also in the order of m = |E|. Note also that in every iteration, if a different pairs of nodes is selected, a different maximal strong matching may be found in the end. Different from the algorithm for computing a maximal 0-regular subnetwork, in this algorithm, after a maximal 1-regular subnetwork is found, the inequality condition still needs to be tested to make sure that no nodes outside the subnetwork have fewer than 2 connections with the nodes in the subnetwork. If the test fails, the algorithm needs to be repeated until a subnetwork is found that passes the test. Select i, j ∈ U , (i, j) ∈ E; 3.

Remove all k from U , (i, k) or (j, k) ∈ E.

Move i, j from U to U * . 5. End

The algorithm in Frame 3 is for computing the distancing strategy on a maximal 2-regular subnetwork. This is equivalent to finding a maximal set of independent cycles in the network. The idea behind the algorithm is to start from an arbitrary node to find a cycle from it, which can be done in a standard cycle detection procedure [49, 50] : Branch the node to its children nodes, and continue to branch the children nodes, and so on and so forth, until a cycle occurs, i.e., a previously branched node is found to be branched into again. If a cycle is found, then remove the cycle and all its connected nodes from the network. Otherwise, remove the expanded tree from the network. The algorithm then continues for the rest of the network until all remaining cycles are found. The collected cycles form a maximal 2-regular subnetwork G * . Let k be the number of nodes in the subnetwork, i.e., k = |V * |. Then, x * i = 1/k for all i ∈ V * and x * i = 0 for all i ∈ V \V * . Note that in each iteration, the algorithm needs to expand a tree, which requires no more than n branches, and in total, no more than n 2 such operations, where n = |V |. In the end of each iteration, some links need to be examined and removed. All 15/22 these actions add to order of m = |E| additional operations. Thus the whole algorithm requires no more than n 2 + m operations. Note also that in every iteration, if a different node is selected for expanding a tree, a different set of cycles may be found in the end. Also, after a maximal 2-regular subnetwork is found, the inequality condition still needs to be tested to make sure that no nodes outside the subnetwork have fewer than 3 connections with the nodes in the subnetwork. If the test fails, the algorithm needs to be repeated until a subnetwork is found that passes the test. Select i ∈ U . 3.

Expand i to a tree until a cycle C * is found. 4.

If no cycle, remove the tree from U , go to 1.

Remove all i, j from U , i ∈ C * , (i, j) ∈ E. 6.

Add

Determining a maximal r-regular subnetwork for r ≥ 3 is more complicated than the above cases. Typically, when tracing such a subnetwork, there are more than one choices for possible branches, and in the worst case, the algorithm may run into exponentially many steps [51] . As given in Frame 4, the algorithm starts by selecting a node from the network and expands it to include r nodes that are connected to it. Let C * be the set of expanded nodes. The algorithm continues to examine each of the nodes in C * . If the degree of a node is less than r, it is expanded to include additional r − d C * connected nodes in V \C * , where d C * is the degree of this node in C * . In the end, if all the nodes in C * have degree r in C * , then C * becomes a r-regular subnetwork. Then, the algorithm removes C * and all its connected nodes from the network and continues the same procedure for the rest of the network until all other r-regular subnetworks are found. Upon finishing, a collection of r-regular subnetworks is found as a maximal r-regular subnetwork G * . Let k be the number of nodes in the subnetwork, i.e., k = |V * |.

Then, x * i = 1/k for all i ∈ V * and x * i = 0 for all i ∈ V \V * . Note that in each branching iteration (step 6 in the algorithm), a set of r − d connected nodes will be selected from the whole set of nodes connected to the current node. There can be many possible choices. Therefore, this iteration may be repeated many times until a proper set of nodes is found. Because this may happen at every branching node, in the worst case, exponentially many steps may be spent to finish the whole algorithm. Finally, as in other algorithms, after a maximal r-regular subnetwork is found, the inequality condition still needs to be tested to make sure that no nodes outside the subnetwork have fewer than r + 1 connections with the nodes in the subnetwork. If the test fails, the algorithm needs to be repeated until a subnetwork is found that passes the test.

This work is motivated by the pressing concern of the current global pandemic and the urgent need for public health measures such as social distancing to contain the disease. Much work has been done in the past on social distancing as a behavioral factor affecting the development of an infectious disease, but research on how to effectively practice and Select i ∈ U ; C * = {i}; C = U \C * .

Do while C * = φ 4.

Select j ∈ C * , d C * (j) < r.

If no such j ∈ C * , break. 6.

Select r − d C * (j) neighbors of j in C. 7.

If fails, remove j from C * , skip. 8.

Move these nodes from C to C * . 9. End 10.

Add C * to U * . 11.

Remove i, k, l from U , k ∈ C * , (k, l) ∈ E. 12. End

manage social distancing is lacking. The latter can in fact be an even more important research subject, for the effectiveness of social distancing would be greatly undermined if without effective practicing. We have considered a social distancing problem for how a population, when in a world with a network of social sites, chooses some sites to visit or stay while avoiding or closing down others so that the social contacts of the population across the network can be minimized. We have modeled this problem as a network population game with the Nash equilibrium of the game corresponding to an optimal distancing strategy. The social sites that are selected at equilibrium form a subnetwork, which we have recognized as a structural support for the equilibrium strategy.

We have shown that a large class of equilibrium strategies can be supported by a maximal r-regular subnetwork. The latter includes many well studied network types, which are easy to identify or construct, and can be completely disconnected for the most strict isolation (with r = 0) or allow certain degree of connectivities for more flexible distancing (with r > 0). We have derived the equilibrium strategies on 3 different types of r-regular subnetworks: (i) maximal 0-regular subnetworks known as maximal independent sets; (ii) maximal r-regular subnetworks for r > 0. (iii) maximal collections of mixed r-regular subnetworks.

We have introduced the concept of rigidity, flexibility, and fragility of a social distancing strategy, and analyzed these properties for strategies on different types of r-regular subnetworks. We have shown that (i) strategies on maximal 0-regular subnetworks are strictly rigid; (ii) strategies on maximal r-regular subnetworks are flexible for all r > 0; (iii) strategies on maximal r-regular subnetworks whose components are minimal r-regular subnetworks are weakly rigid for all r > 0; and (iv) strategies on maximal r-regular subnetworks with at least one non-minimal r-regular component are fragile for all r > 0.

We have also provided an overview on algorithms that can be used for computing maximal r-regular subnetworks and their associated distancing strategies. They are not necessarily optimized, but do contain the essential steps, and are easy to understand and follow. They include algorithms for computing strategies on (i) maximal 0-regular subnetworks, i.e., maximal independent sets; (ii) maximal 1-regular subnetworks known as maximal strong matchings; (iii) maximal 2-regular subnetworks known as maximal sets of independent cycles; and (iv) general maximal r-regular subnetworks with r ≥ 3.

Our work is a step towards developing a general theoretical and computational framework for the study of social distancing in networked social environments. It is however open for many further research efforts. First, new dynamic epidemic models can be built for populations distributed over social networks as determined by the equilibrium strategies for the social distancing game. Different from those for well mixed populations, such models may provide more realistic estimates on various epidemic properties such as contact rates, transmission rates, and hence the infectious rates, etc. Dynamic models on structured populations are always preferred because populations are always heterogeneous in terms of physical or social proximities [52] .

Second, the network types we have discussed are r-regular networks because they are easy to identify or construct, yet cover a broad range of networks with varying degrees of connectivities. However, in reality, the networks may not always be so "regular". The population may prefer other types of network structures such as spanning trees, extended stars, or small-world networks, all with low degrees of connectivities [53] . In addition, the structures may also change dynamically. It would be interesting to find the equilibrium conditions of the distancing strategies on such networks, including related distancing properties such as rigidity, flexibility, and fragility of the strategies.

Third, social distancing always brings economic costs or social sacrifices. Different distancing strategies may have different social or economic consequences [54] . Reducing social contacts is a main goal as far as fighting a pandemic is concerned, but keeping certain levels of social or economic activities can be important as well especially during a possibly long period of recovery from the pandemic [55] . Therefore, there must be a tradeoff between choosing rigid and flexible distancing strategies. In addition, the social or economic values of different social sites can be different, which may affect the decisions on choosing or closing them for distancing. We have not included these considerations in our current model yet, but they can be important to incorporate in future models using for example social distancing games with weighted networks.

Finally, we would like to point out that the social networking game as given in (1) has been studied recently as a network population game in [56] . It becomes relevant when social distancing comes into play, for the latter is exactly a complementary game to the former. The social networking game has been formulated in different forms and for different purposes in the past. It has been used for the solution of the maximum clique problem, since the maximum clique of a given network corresponds to the Nash equilibrium of the social networking game on this network with the largest number of positive frequencies [57] . It has also been used for modeling the evolution of allele selection in genetic research as an evolutionary game on genetic selection graphs [58] . The work on the social distancing game on a network in this paper benefits from many ideas and results coming out from these previous studies.

To fight coronavirus spread, the U.S. may extend 'social distancing' measures

Social distancing prevents infections, but it can have unintended consequences

Animal Behavior: An Evolutionary Approach

These wild animals also practice social distancing to avoid getting sick

Public health interventions and epidemic intensity during the 1918 influenza pandemic

Social distancing as a pandemic influenza prevention measure, National Collaborating Center for Infectious Diseases

Effectiveness of workplace social distancing measures in reducing influenza transmission: A systematic review

School and prepareness officials' perspectives on social distancing practices to reduce influenza transmission during a pandemic: Considerations to guide future work

Isolation, quarantine, social distancing and community containment: pivotal role for old-style public heath measures in the novel coronavirus (2019-nCoV) outbreak

Modeling desease outbreaks in realistic urban social networks

Effects of behavioral changes in a smallpox attack model

Targeted social distancing design for pandemic influenza

Contact network epidemiology: bond percolation applied to infectious disease prediction and control

Quantifying social distancing arising from pandemic influenza

Simulation suggests that rapid activation of social distancing can arrest epidemic development due to a novel strain of influenza

Modeling the influence of human behavior on the spread of infectious diseases: a review

Game theory of social distancing in response to an epidemic

Public avoidance and epidemics: insights from an economic model

Intermittent social distancing strategies for epidemic control

Game dynamic model of social distancing while cost of infection varies with epidemic burden

Impact on non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand

Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand, Imperial College COVID-19 Response Team

Feasibility of controlling COVID-19 outbreaks by isolation of cases and contacts

The effect of controlling strategies to reduce social mixing on outcomes of the COVID-19 epidemic in Wuhan, China: a modeling study

A model-based evaluation of the efficacy of COVID-19 social distancing, testing and hospital triage policies

The Novel coronavirus, 2019-nCoV, is highly contagious and more infectious than initially estimated

Graph Theory

A general approach for population games with applications to vaccination

Equilibria of an epidemic game with piecewise linear social distancing cost

Understanding largescale social and infrastructure Networks: A simulation-based approach

Network based models of infectious disease spread

Structure of social networks and their impact on epidemics

EpiSimdemics: An efficient algorithm for simulating the spread of infectious diseaseover large realistic social networks

Predicting epidemics on direct contact networks

Susceptible-infected-recovered epidemics in dynamic contact networks

Epidemic thresholds in dynamic contact networks

The dynamic nature of contact networks in infectious disease epidemiology

Evolutionary Game Theory

Evolutionary Games and Population Dynamics

Practical Optimization

Basic solutions of discrete games

Game Theory: Decisions, Interaction and Evolution

Computers and Intractability: A Guide to the Theory of NP-Completeness

NP-completeness of some generalizations of the maximum matching problem

Induced matchings

Maximum k-regular induced subgraphs

Introduction to Algorithms, Third Edition

Fast exponential algorithms for maximum r-regular induced subgraph problems

Economic considerations of social distancing and behavioral based policies during an epidemic

From social distancing to social containment: reimagining sociality for the coronavirus pandemic

Equilibrium distributions of populations of biological species on networks of social sites

Evolution towards the maximum clique

On the number of stable equilibria in a one-locus, multi-allelic system

The author would like to thank Claus Kadelka, Audrey McCombs, and Rana Parshad to share their work with the author, and provide valuable suggestions on this work. The author would also like to acknowledge the support from the Simons Foundation through the Mathematics and Physical Sciences Collaboration Grants for Mathematicians.