Mohamad Badaoui
email: mohamad.badaoui1@gmail.com

Jean-Guy Caputo
email: caputo@insa-rouen.fr

Arnaud Knippel
email: arnaud.knippel@insa-rouen.fr

Vaccination strategy on a geographic network

We considered a simple model describing the propagation of an epidemic on a geographical network. The initial rate of growth of the epidemic is the maximal eigenvalue of a matrix formed by the susceptibles and the graph Laplacian. Assuming the vaccination reduces the susceptibles, we define different vaccination strategies: uniform, local, or following a given vector. Using perturbation theory and the special form of the graph Laplacian, we show that it is most efficient to vaccinate along with the eigenvector corresponding to the largest eigenvalue of the Laplacian. This result is illustrated on a 7 vertex graph, a grid, and a realistic example of the french rail network. KeywordsSIR epidemic model, Graph, Matrix perturbation AMS indices 92D30, 05C50, 47A55

Introduction

The propagation of an epidemic in a country or an ensemble of countries can be modeled using a graph where each vertex has susceptible-infected (SI) variables and where the geographic coupling is realized through a connection matrix. A pioneering study was conducted by Helbling et al [START_REF] Brockmann | The Hidden Geometry of Complex[END_REF] to analyze the propagation of influenza via the airline routes. Such a model is very general and could describe the propagation of an internet virus or how populations mix in a given environment.

In a recent article, we considered a simple SI model on each vertex where the vertices are coupled by a graph Laplacian [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF]. This is a symmetric version of the mobility matrix introduced by Helbling [START_REF] Brockmann | The Hidden Geometry of Complex[END_REF]. Our model was accurate in predicting the arrival of the epidemic in Mexico [START_REF] Cruz-Pacheco | Dispersion of a new coronavirus SARS-CoV-2 by airlines in 2020: Temporal estimates of the outbreak in Mexico[END_REF]. It is also very simple: an SI model coupled to a discrete diffusion. This means it can easily be fitted to real data. Other models suggested for analyzing the propagation of COVID, for example the study done by Gatto et al [START_REF] Gatto | Spread and dynamics of the COVID-19 epidemic in Italy: Effects of emergency containment measures[END_REF], use a more complex model with many parameters and these can be difficult to estimate from data. In addition, the geographic coupling is complicated so that it is difficult to analyze. From a theoretical perspective, Cantin and Silva [START_REF] Cantin | Influence of the topology on the dynamics of a complex network of HIV/AIDS epidemic models[END_REF] studied a more complex model than SIR coupled to a mobility matrix as Helbling [START_REF] Brockmann | The Hidden Geometry of Complex[END_REF]. They proved the existence, unicity, and positivity of the solutions and show the existence of a disease-free fixed point. They also analyzed how this fixed point is affected by the coupling between vertices; however, the results are hard to interpret even for chain graphs with two or three vertices.

In our much simpler study [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF], we defined an epidemic criterion based on the maximum eigenvalue λ of a matrix M obtained from the susceptibles and the graph Laplacian matrix. We simply assume that vaccination reduces the susceptibles. This may not always be correct, like in the case of COVID-19 but we will assume it for simplicity. Our preliminary results indicated that it is more effective to vaccinate high degree vertices and not neighbors. Here, we study more in depth the problem to infirm/confirm these findings. We assume a geographic network where the epidemic propagates. Following the study [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF], we assume all populations are the same. This could be a city with similar neighborhoods. We examine the geometric effect of the graph. Assuming susceptibles are all the same, we can ask the following questions : which vertex if vaccinated, will reduce most λ? Is it better to vaccinate 2 vertices or 3 vertices instead of 1? What role do the eigenvectors of the graph Laplacian play?

To address these questions, we use perturbation theory on the matrix M of the vaccination criterion. We compute the corrections at orders 1 and 2 of the maximal eigenvalue using the special properties of the Laplacian matrix. We find that the corrections are minimal, indicating that λ will be minimal when vaccination is applied along the high-order eigenvector. We illustrate these findings on a seven vertex graph, a grid 4 × 12 ( for this system eigenvectors/values can be calculated explicitly), and give special graphs (complete, stars) for which this argument does not hold. Finally, we study numerically a more realistic situation where the Laplacian has weights corresponding to routes more traveled than others and where again the argument holds. The article is organized as follows, section 2 presents the model and the perturbation method. In section 3, we give our main results. Several graphs are analyzed numerically in section 4 and conclusions are presented in section 5.

The model and the perturbation method

We recall the model introduced in [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF] describing the propagation of an epidemic on a geographical network where the vertices are indexed 1, 2, . . . , n

Ṡ = LS -βS I, İ = LI + βSI -γI. (1)
where S = (S 1 , S 2 , . . . , S n ) T , I = (I 1 , I 2 , . . . , I n ) T are respectively the susceptibles and infected, β, γ are respectively the infection and recovery ratios, L is the graph Laplacian matrix [START_REF] Cvetkovic | An Introduction to the Theory of Graph Spectra[END_REF], and where we denote by SI the vector (S 1 I 1 , S 2 I 2 , . . . , S n I n ) T . This is a simplified model where we assume all populations are the same. We concentrate on the geometric effects due to the graph.

The graph Laplacian L is the real symmetric negative semi-definite matrix, defined as L kl = 1 if k and l are connected, 0 otherwise, and L kk =l =k L kl . This matrix has important properties, see Ref. [START_REF] Cvetkovic | An Introduction to the Theory of Graph Spectra[END_REF], in particular, it is a finite difference approximation of the continuous Laplacian [START_REF] Dahlquist | Numerical Methods[END_REF]. The eigenvalues of L are the n non-positive real numbers ordered and denoted as follows:

0 = -ω 2 1 ≥ -ω 2 2 ≥ ... ≥ -ω 2 n .
The eigenvectors {V 1 , ..., V n } satisfy

LV j = -ω 2 j V j .
and can be chosen to be orthonormal with respect to the standard scalar product in R n , i.e. (V i , V j ) = δ i,j where δ i,j is the Kronecker symbol.

In Ref. [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF], we introduced an epidemic criterion in the following way. For small I, observe that equations (1) imply

İ = M I where M = L + βdiag(S) -γId n . (2)
All eigenvalues of L are real and the additional terms will shift these eigenvalues towards the real axis in the complex plane, keeping the eigenvalues real. The maximum eigenvalue λ of M gives the initial rate of growth of the infected on the network.

A simple description of vaccination or partial isolation of a vertex i is to change its number of susceptibles S i . We assume this change to be small, O(ǫ) so that

S i = 1 -ǫs i . (3)
Then -ǫs i represents the reduction in the number of susceptibles at vertex i due to vaccination. Our main goal in this article is to discover the vaccination policy that minimizes λ.

The matrix M can be written as

M = M 0 + ǫR, M 0 = L + (β -γ)Id, R = -β       s 1 0 . . . 0 0 s 2 . . . . . . . . . . . . . . . 0 0 . . . 0 s n       (4)
The principle of the perturbation theory for eigenvalues and eigenvectors of a matrix [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF] is to write expansions of an eigenvalue of M and its corresponding eigenvector as

λ = λ 0 + ǫλ 1 + ǫ 2 λ 2 + ǫ 3 λ 3 + ..., (5)
v = v 0 + ǫv 1 + ǫ 2 v 2 + ǫ 3 v 3 + ... (6)
and write the different orders in ǫ. These expansions can be shown to converge with ǫ [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF].

We introduce the expansions above in the eigenvalue equation M v = λv, and the first three orders in ǫ yield

(M 0 -λ 0 )v 0 = 0, (7)
(M 0 -λ 0 )v 1 = λ 1 v 0 -Rv 0 , (8)
(M 0 -λ 0 )v 2 = λ 2 v 0 + λ 1 v 1 -Rv 1 . (9)
These linear equations have solutions if their right-hand side is orthogonal to the kernel of (M 0 -λ 0 ) † = (M 0 -λ 0 ). This is the solvability condition. In our special case (M 0 -λ 0 ) = L so the equations above reduce to

Lv 0 = 0, ( 10
)
Lv 1 = (λ 1 -R)v 0 , (11)
Lv 2 = λ 2 v 0 + (λ 1 -R)v 1 . (12)
We have

λ 0 = β -γ. (13)
From the solvability conditions, we obtain λ 1 and λ 2 as

λ 1 = (v 0 , Rv 0 ) (v 0 , v 0 ) , (14)
λ 2 = (v 0 , Rv 1 -λ 1 v 1 ) (v 0 , v 0 ) . ( 15
)
We now consider the linear systems (10,11,12) for the particular case when L is a graph Laplacian. The Laplacian has real eigenvalues and orthogonal eigenvectors

LV i = -ω 2 i V i , (16)
where ω 1 = 0 and V 1 is the constant vector. The other eigenvalues verify

-ω 2 n ≤ • • • ≤ -ω 2 1 = 0. ( 17
)
We assume the graph to be simply connected so that there is only one eigenvalue zero [START_REF] Cvetkovic | An Introduction to the Theory of Graph Spectra[END_REF]. The matrix L is therefore singular and special care must be taken when solving the system. The standard way to solve the system is to use the singular value decomposition of L. Since L is symmetric, this reduces to projecting the solution and the right-hand side on the eigenvectors of L. Therefore, we can choose v 0 = V 1 where V 1 the constant eigenvector is normalized. The formulas (14,15) become

λ 1 = (V 1 , RV 1 ), (18)
λ 2 = V 1 , (R -λ 1 v 1 ). ( 19
)
These equations together with the linear equation

Lv 1 = (λ 1 -R)V 1 , (20)
are the core of our study.

Perturbation results

Our main goal is to study vaccination strategies, i.e. to choose the vector (s 1 , s 2 , . . . , s n ) that minimizes

λ = λ 0 + ǫλ 1 + ǫ 2 λ 2 + O(ǫ 3 )
From equation (4) we can establish three vaccination strategies (i) Reduce S i uniformly on all vertices, then s i ≥ 0, i = 1, . . . , n.

(ii) Reduce S i on some vertices and not others, then s i ≥ 0, for some i = 1, . . . , n.

(iii) Adjust S i globally using an eigenvector V k of the Laplacian L, i.e. S = V 1 -ǫV k . Then s i can be positive or negative.

Approach (i) is to vaccinate uniformly all vertices. This assumes a large quantity of vaccines. It is the simplest of strategies and will be the benchmark by which we will test the other strategies. Approach (ii) assumes there are a limited number of vaccine doses available and a choice needs to be made. Approach (iii) is not practical since we cannot increase s i , we can only decrease it. We can mimick this by using approach (i) and transferring some of the vaccines from one vertex to another.

We can state the following Mathematical program Minimize maximum eigenvalue λ of M such that n i=1 s i is constant For strategy (ii) s i ≥ 0 For strategy (iii) there are no positivity constraints on s i .

The first order λ 1

We have the following result Theorem 3.1. Let G be a graph with n vertices. If we reduce the susceptibility at every vertex v i ∈ V (G) by s i , then we have

λ 1 = - β n n i=1 s i . (21)
Proof. This is a direct consequence of equation ( 14) where we chose v 0 = V 1 the constant eigenvector.

Theorem 3.1. Let G be a graph on n. Suppose that we completely isolate any vertex v ∈ V (G), then we have

λ 1 = - β n
We can make the following remarks.

(i) Note that λ 1 is always negative.

(ii) The quantity λ 1 only depends on the quantity s i and does not depend on the degree of i.

(iii) From Theorem 3.1, λ 1 is minimal when the n i=1 s i is maximal. In other words, we can minimize λ 1 and thus the epidemic criterion λ by increasing the total percentage of the vaccinated population on the network regardless of their location.

(iv) In the special case where we vaccinate only one vertex, λ 1 is independent of this vertex and of the graph. On the contrary, λ i , i ≥ 2 depends on the vaccinated vertex and the graph.

The second-order λ 2

The estimation of λ 2 benefits from using the eigenvectors of the Laplacian matrix L (16). We have

λ 2 = (V 1 , (R -λ 1 )v 1 ),
where

Lv 1 = (λ 1 -R)V 1 .
Writing

v 1 = n k=2 α k V k ,
plugging it into the equation above, and then projecting it onto each eigenvector V k yields α k . We obtain

v 1 = n k=2 1 ω 2 k (RV 1 , V k )V k , (22)
where

RV 1 = - β √ n (s 1 , s 2 , . . . , s n ) T
We can now compute λ 2 , as

λ 2 = (V 1 , (R -λ 1 )v 1 ) = n k=2 1 ω 2 k (RV 1 , V k )(V 1 , (R -λ 1 )V k ) We have (V 1 , (R -λ 1 )V k ) = (V 1 , RV k )
because V 1 and V k are orthogonal. We finally get

λ 2 = n k=2 1 ω 2 k (RV 1 , V k ) 2 . ( 23
)
Note that the correction λ 2 is always positive.

Optimal vaccination strategy

An important theorem follows from the estimate (23).

Theorem 3.2. When RV 1 is proportional to V k , k ≥ 2, λ 1 = 0. The eigen- value correction λ 2 is minimum when RV 1 is proportional to V n . Proof. Choosing RV 1 = (s 1 , s 2 , . . . , s n ) T = V k where V k , k ≥ 2 is an eigenvec- tor of L leads to λ 1 = 0.
In equation (21), we have from the orthogonality of

V k to V 1 n i=1 s i = n i=1 V k i = 0.
Assume RV 1 = βV k . Then

λ 2 = β 1 ω 2 k .
From the order relation (17), this quantity decreases monotonically as k varies from 2 to n.

In other words, as we choose RV 1 = V k for increasing k, the correction λ 2 decreases.

Higher-order corrections

We have

v 1 = n k=2 α k,1 V k = n k=2 1 ω 2 k (RV 1 , V k )V k λ 2 = n k=2 1 ω 2 k (RV 1 , V k ) 2
The equation for v 2 is

Lv 2 = λ 2 V 1 + (λ 1 -R)v 1 . Writing v 2 = n k=2 α k,2 V k we have α k,2 = 1 ω 2 k [(Rv 1 , V k ) -λ 1 α k,1 ]
The equation yielding v i is

Lv i = λ i V 1 + λ i-1 v 1 + . . . + λ 1 v i-1 -Rv i-1
Writing

v i = n k=2 α k,i V k , we have α k,i = 1 ω 2 k [(Rv i , V k ) -λ 1 α k,i-1 -. . . -λ i-1 α k,1 ]
We can compute λ i+1 , as

λ i+1 = (V 1 , (R -λ 1 )v i -λ 2 v i-1 -. . . -λ i v 1 ) = (V 1 , Rv i ) = ... = n k=2 [ 1 ω 2 k ((Rv i-1 , V k ) -λ 1 α k,i-1 -. . . -λ i-1 α k,1 )(RV k , V 1 )]
In particular, we can compute λ 3 ,

λ 3 = (V 1 , (R -λ 1 )v 2 -λ 2 v 1 ) = (V 1 , Rv 2 ) = ... = n k=2 1 ω 2 k [(Rv 1 , V k )(RV k , V 1 ) - λ 1 ω 2 k (RV k , V 1 ) 2 ]

Comparison of the different vaccination strategies

From this analysis, we can discuss how different vaccination policies proposed in the beginning of section 3 affect λ.

(i) Uniform vaccination on the network, i.e. This corresponds to

S = (1 - ǫ)V 1 . Then λ = β(1 -ǫ) -γ. ( 24
) (iii) Vaccination following the eigenvector V k , then S = V 1 -ǫV k . We then have λ 0 = β -γ, λ 1 = 0, λ 2 = β ω 2 k so that λ = β -γ + ǫ 2 β ω 2 k + O(ǫ 3 ). (25)
(ii) Vaccination of j < n vertices of the network, i.e. S k = 1 -ǫ, k = 1, . . . , j. This is the most difficult situation because we cannot control λ 2 . We have

λ 0 = β -γ, λ 1 = - βj n so that λ = β -γ -ǫ βj n + O(ǫ 2 ). (26)
Note that when j = n, λ i = 0, i ≥ 2 and (ii) reduces to (i).

Application: certain graph families

Here, we examine numerically the matrix M and its maximal eigenvalue λ for different graphs to emphasize the role of the graph topology. We choose for simplicity β = γ = 1.

A 7 vertex graph

Consider the seven vertex graph shown in Fig. 1.

= V k .
Note how λ decreases between 2 ≤ k ≤ 7. The optimal vaccination policy is the one that follows V 7 . The eigenvalue λ varies from 0.12 to 0.018 as s follows V 2 or V 7 .

The eigenvectors of the Laplacian are plotted in Fig. 2. As expected, the low-order eigenvectors vary on scales comparable to the size of the graph. The high order eigenvectors, on the contrary, oscillate on smaller scales. It is difficult to relate the results of Table 1 to the practical situation of vaccinating individual vertices. To gain some intuition, we vaccinate two or three vertices and compute the eigenvalues of M . We choose the sum of the S vector to be the same for both situations to describe a limited amount of vaccines to be distributed over a geographic region.

For two vaccinated vertices i, j, we choose s i = 0.5, s j = 0.5. Table 2 gives for i, j, the maximum of the projection on the eigenvectors

p ij = max 1<k≤n |(s, V k )|, ( 27
)
and the eigenvalue λ of the epidemic criterion. As expected, the largest λ corresponds to a projection that is maximal on the low order eigenvectors and vice-versa. This is an average trend and there are some exceptions such as [START_REF] Brockmann | The Hidden Geometry of Complex[END_REF][START_REF] Cruz-Pacheco | Dispersion of a new coronavirus SARS-CoV-2 by airlines in 2020: Temporal estimates of the outbreak in Mexico[END_REF] , [START_REF] Bustamante-Castañeda | Epidemic model on a network: Analysis and applications to COVID-19[END_REF][START_REF] Gatto | Spread and dynamics of the COVID-19 epidemic in Italy: Effects of emergency containment measures[END_REF]. This is because the second-largest projection is on V 2 , see Fig. 2.

For three vaccinated vertices i, j, k, we choose s i = s j = s k = 0.33. We define the projection similarly to (27). The results are presented in Table 3 Table 3: Maximal eigenvalue λ and projection p ijk when vaccinating three vertices i, j, k for the 7 vertex graph of Fig. 2.

Table 3 shows that vaccinating three vertices i, j, k gives eigenvalues that are minimal when the projection |(s, V k )| corresponds to a small k. As for the two vertices, this is expected from the general theory. Of course, the trend is general and there are a few exceptions.

A grid P 4 × P 12

We consider a grid P 4 × P 12 to illustrate our results. For such a graph, one can calculate explicitly the eigenvectors and eigenvalues leading to analytic though complicated expressions for λ 2 .

We computed the largest eigenvalue of the matrix M for ǫRV 1 = 0.3V k and k = 2, . . . n. The results are presented in Table 4 The eigenvalue λ varies from 0.3 to 0.01 as s follows V 2 or V 48 . Again, it is difficult to evaluate which vertices to vaccinate.

For grids, the quantity λ 2 can be calculated precisely using the fact that eigenvalues and eigenvectors are known analytically. For completeness, we recall the formalism, more details can be found in the book [START_REF] Biyikoglu | Laplacian eigenvectors of graphs[END_REF]. A path P n has eigenvalues ω 2 i and eigenvectors V i such that

ω 2 i = 4 sin 2 π(i -1) 2n , i = 1, . . . , n (28)
V i p = 1 N i cos[ π(i -1) n (p - 1 2 )], p = 1, . . . , n (29)
where the normalization factors are N 1 = √ n and N i = n/2 i > 1. A grid is the cartesian product P n × P m of two paths P n and P m . The associated eigenvector is V ij = V i ⊗ V j , the Kronecker product of V i and V j . The eigenvalues ω 2 i,j and corresponding eigenvectors are given by

ω 2 i,j = 4 sin 2 π(i -1) 2n + sin 2 π(j -1) 2m , (30)
V ij pq = V i p V j q = 1 N i N j cos[ π(i -1) n (p - 1 2 )] cos[ π(j -1) m (q - 1 2 )], (31)
where i, p ∈ {1, . . . , n}, j, q ∈ {1, . . . , m} and where the normalization factors N i , N j follow the rules defined after (29).

From the estimate (23), using the expressions (30,31) we can get an expression for λ 2 . It is extremely cumbersome and we chose not to present it.

Using the expressions of the eigenvectors V ij , we can compare the eigenvectors V 1,2 and V 4,12 corresponding respectively to the minimal and maximal eigenvalues in the absolute value of the Laplacian. These eigenvectors correspond to k = 2 and 48 in Table 4. They are plotted in Fig. 3. Notice the small scales associated to V 4,12 (right panel) as opposed to the smoothness of V 1,2 (left panel).

Special graphs: complete graphs and stars

There are classes of graphs for which choosing RV 1 = V k , with k large, does not necessarily affect λ 2 . For these graphs, the eigenvalues -ω 2 k are equal so that the ratio 1

ω 2 k (RV 1 , V k ) 2
in the sum (23) does not decrease as k increases.

One example is the class of the complete graphs K n .

Definition 4.1 (Complete graph K n ). A clique or complete graph K n is a graph where every pair of distinct vertices is connected by a unique edge.

The clique K n has eigenvalue -n with multiplicity n -1 and eigenvalue 0. The eigenvectors for eigenvalue n can be chosen as v k = e 1 -e k , k = 2, . . . , n. Another special class of graphs where many eigenvalues are equal are stars. For these a single vertex, say 1, is connected to the n -1 other vertices. The eigenvalues with their multiplicities denoted as exponents are 0 1 , (-1) n-2 , , (-n) 1 .

Eigenvectors for -1 can be chosen as e 2 -e i (i = 3, . . . , n). The eigenvector for -n is (1, -1/(n -1), . . . , -1/(n -1)) T . Table 6 shows λ as a function of k for S 5 , S 7 and S 10 . Note that the ratio max(λ)/min(λ) increases as n varies from 5,7 to 10.

A more realistic case: France

The practical case of vaccinating a whole country can be tackled using our approach. Fig. 4 shows a map of the main railway lines in France. The fast lines are presented as continuous edges while the slower ones are dashed. In the graph Laplacian, this corresponds to weights 1 and 0.5 for respectively the fast and slow connections. We computed the largest eigenvalues of the matrix M as RV 1 = 0.3V k for k = 2, . . . n. The results are presented in table 7. 7: Largest eigenvalues of M for RV 1 = 0.3V k for the graph of France with weights 1 and 0.5 respectively continuous and dashed links.

Note how there is a factor of 50 in the maximal eigenvalue of M between the cases RV 1 = V 2 and RV 1 = V 24 . From a practical point of view, this means that the epidemic will grow at a rate 50 times slower with V 24 than V 2 , using the same number of vaccines. Another point is that the largest component of V 24 corresponds to the vertex (PAR1) of highest degree [START_REF] Cvetkovic | An Introduction to the Theory of Graph Spectra[END_REF]. It seems natural to vaccinate this vertex. Now, we consider that all the links have the same weights. The results are reported in table 8. They show a factor of 60 in the maximal eigenvalue of M between the cases RV 1 = V 2 and RV 1 = V 24 . k λ 2 5.6391 10 -1 3 3.1945 10 -1 4 2.0931 10

Figure 1 :

 1 Figure 1: A seven vertex graph

Figure 2 :

 2 Figure 2: The eigenvectors V i , i = 2, . . . , 7 of the seven vertex graph of Fig. 1.

Figure 3 :

 3 Figure 3: The eigenvectors V 1,2 (left panel) and V 4,12 (right panel) for the grid P 4 × P 12 .

Figure 4 :

 4 Figure 4: The main railway network in France where the fast (resp. slow) lines are shown as continuous (resp. dashed) edges.

  k

Table 1 :

 1 Largest eigenvalue λ of M for RV1

Table 2 :

 2 Maximal eigenvalue λ and projection p ij when vaccinating two vertices i, j for the 7 vertex graph of Fig.2.

	i	j k p ijk		λ	i	j k p ijk	λ
	1 4 6 2 4 6 1 3 6 3 5 6 2 5 6 1 4 7 2 4 7 3 4 6 1 3 7 3 5 7 2 3 6 2 5 7	7 5 6 7 4 7 4 5 6 7 5 6	-1.5538 10 -2 -1.5308 10 -2 -1.5086 10 -2 -1.4533 10 -2 -1.3843 10 -2 -1.3831 10 -2 -1.3448 10 -2 -1.3222 10 -2 -1.3188 10 -2 -1.2971 10 -2 -1.2318 10 -2 -1.2187 10 -2 i j k p ijk	1 2 6 1 5 6 3 4 7 2 3 7 1 2 7 1 5 7 4 5 6 4 5 7 1 4 5 2 4 5 1 3 5 3 4 5	4 4 4 3 3 5 3 3 3 6 5 3 λ	-1.1881 10 -2 -1.1275 10 -2 -1.1238 10 -2 -1.0042 10 -2 -9.6590 10 -3 -9.5776 10 -3 -6.2370 10 -3 -4.3165 10 -3 -2.8840 10 -3 -2.0491 10 -3 -1.7983 10 -3 -7.4494 10 -4
				1 2 5	4		7.5857 10 -4
				2 3 5	7		7.9548 10 -4
				3 6 7	6		1.8558 10 -3
				2 6 7	2		3.1658 10 -3
				1 6 7	2		4.7346 10 -3
				1 3 4	2		7.6481 10 -3
				1 2 4	7		8.3041 10 -3
				4 6 7	2		9.7040 10 -3
				2 3 4	2		1.2156 10 -2
				1 2 3	2		1.6396 10 -2
				5 6 7	2		1.9027 10 -2

Table 4 :

 4 . Largest eigenvalue λ of M for RV 1 = V k for a grid P 4 × P 12 .

	k	λ	k	λ	k	λ	k	λ	k	λ
	2	0.3090	11 0.0562	20 0.0299	29 0.0243	38 0.0185
	3	0.2063	12 0.0445	21 0.0278	30 0.0237	39 0.0180
	4	0.1396	13 0.0445	22 0.0291	31 0.0226	40 0.0167
	5	0.1396	14 0.0449	23 0.0263	32 0.0234	41 0.0167
	6	0.1404	15 0.0448	24 0.0263	33 0.0213	42 0.0158
	7	0.1017	16 0.0398	25 0.0266	34 0.0211	43 0.0155
	8	0.0841	17 0.0354	26 0.0261	35 0.0205	44 0.0153
	9	0.0752	18 0.0350	27 0.0252	36 0.0206	45 0.0141
	10 0.0588	19 0.0350	28 0.0248	37 0.0199	46 0.0133
					k	λ
					47 0.0127
					48 0.0126

Table 5 :

 5 Table 5 shows the eigenvalue λ of M for K 4 , K 5 , and K 7 from left to right. As expected there are no significant changes in λ as a function of k. Largest eigenvalue λ of M for RV 1 = 0.3V k for complete graphs K 4 , K 5 and K 7 from left to right.

	k	λ	k	λ	k	λ
	2 0.021156	2 0.019695	2 0.013034
	3 0.023520	3 0.019117	3 0.013184
	4 0.021153	4 0.019117	4 0.013594
			5 0.019117	5 0.011805
					6 0.012404
					7 0.012313

Table 6 :

 6 Largest eigenvalue λ of M for RV 1 = 0.3V k for star graphs n = 5, 7 and 10 from left to right

	k	λ	k	λ	k	λ
	2	0.10643	2	0.10974	2	0.049159
	3 0.075781	3 0.099318	3	0.055638
	4	0.12306	4	0.10453	4	0.19283
	5 0.019695	5	0.14166	5	0.19283
			6	0.12715	6	0.19283
			7 0.014059	7	0.19283
					8	0.19283
					9	0.19283
					10 0.0097722

Table 8 :

 8 Largest eigenvalues of M for RV 1 = 0.3V k for the graph of France with equal weights 1 on all links.

Acknowledgements

The authors are grateful to Gustavo Cruz for useful discussions. They thank the region of Normandy and the European Union for support through the grant Modélisation et Analyse des Systèmes Complexes en Biologie (MASyComB).

Conclusion

We studied a vaccination policy on a simple model of an epidemic on a geographical network by examining the maximum eigenvalue λ of a matrix formed by the susceptibles and the graph Laplacian matrix L.

We found that it is most effective to "vaccinate" the network along the eigenvector of L of the highest order, V n . This answers partially the questions of the introduction about which vertices one should vaccinate. In practice, one should vaccinate the vertices along a vector that has a maximum projection on V n .

To simplify, we assumed that the populations of each city to be equal. This assumption can be relaxed at the price of a more complex analysis. We sketch it here for completeness. Assuming a population N j at vertex j, the evolution reads

From this, it can be seen that the epidemic matrix M reads

Following the analysis of section 2, we introduce the vector

Then we see that the maximum eigenvalue λ of M will be minimum when S has a maximum projection on V n .