# Protection Strategy for Edge-Weighted Graphs in Disease Spread
## 2 Basic Definitions
### Dil-\(\mathsf{W}^{\text{n}}\) Ranking  
The following definition comes from [27; 33]. Let us consider an undirected weighted graph \((G,w)\) with \(G=(V,E)\) and \(V=\{v_{1},v_{2},\ldots,v_{n}\}\). Definition 6 (Degree centrality [33]): The degree centrality of \(v_{i}\in V\) of an edge-weighted graph \((G,w)\), denoted by \(C_{D}^{\text{max}}(v_{i})\), is defined as  
\[C_{D}^{\text{max}}(v_{i})=deg(v_{i})^{(1-\alpha)}\cdot S(v_{i})^{\alpha}, \tag{1}\]  
where \(\alpha\in[0,1]\). The parameter \(\alpha\) is called _tuning parameter_. Notice that when \(\alpha=0\) then \(C_{D}^{\text{max}}(v_{i})=deg(v_{i})\) and when \(\alpha=1\) then \(C_{D}^{\text{max}}(v_{i})=S(v_{i})\). Definition 7 (Importance edge [27]): The importance of an edge \(e_{ij}\in E\), denoted by \(I^{\alpha}(e_{ij})\), is defined as  
\[I^{\alpha}(e_{ij})=\frac{\left(C_{D}^{\text{max}}(v_{i})-p_{i}^{\alpha} \right)\cdot\left(C_{D}^{\text{max}}(v_{j})-p_{j}^{\alpha}\right)}{\lambda^{ \alpha}},\]  
where, for \(k\in\{i,j\}\), \(p_{k}^{\alpha}=(p+1)^{(1-\alpha)}\cdot t_{k}^{\alpha}\) with \(p\) is the number of triangles, one edge of the triangle is \(e_{ij}\), \(t_{k}^{\alpha}\) is the weight of the sum of the edges incident to \(v_{k}\) that form a triangle with \(e_{ij}\) and \(\lambda^{\alpha}=\frac{p^{(1-\alpha)}\cdot\left(t_{i}+t_{j}\right)^{\alpha}}{ 2}+1\). **Definition 8** (Contribution [27]). : _The contribution that \(v_{i}\in V\) makes to the importance of the edge \(e_{ij}\), denoted by \(W^{\alpha}(e_{ij})\), is defined as_  
\[W^{\alpha}(e_{ij})=I^{\alpha}(e_{ij})\cdot\frac{C_{D}^{\alpha\alpha}(v_{i})-w_{ ij}^{\alpha}}{C_{D}^{\alpha\alpha}(v_{i})+C_{D}^{\alpha\alpha}(v_{j})-2w_{ ij}^{\alpha}},\]  
_where \(w_{ij}\) is the weight of \(e_{ij}\)._  
**Definition 9** (Importance of vertex DIL-W\({}^{\alpha}\)[27]). : _The importance of a vertex \(v_{i}\in V\), denoted by \(L^{\alpha}(v_{i})\), is defined as_  
\[L^{\alpha}(v_{i})=C_{D}^{\alpha\alpha}(v_{i})+\sum_{y_{j}\in N(v_{i})}W^{ \alpha}(e_{ij}).\]  
From the definition of Degree centrality (Definition 6) proposed by [PERSON] in [33], we can see that when the tuning parameter \(\alpha\) is 0 the Definitions 7, 8 and 9 of importance edge, contribution, and importance of vertex respectively, are the same than the proposed by [PERSON] et al. in [30] for an undirected and unweighted network. **3. Strategy Protection**  
In this section, we provide definitions of the protection of a graph when a disease spreads on it. Moreover, we state the protection strategy. **Definition 10**. : _Protecting a vertex means removing all of its corresponding edge (See Figure 1)._  
It is also possible to find in the literature that protecting a vertex means removing the vertex from the graph. See for instance [13]. **Definition 11**. : _The numbers of vertices allowed to protect is called protection budget, denoted by \(k\)._  
It is clear that \(k\in\mathbb{Z}^{+}\). **Definition 12**. : _We will say that the survival rate, denoted by \(\sigma\), is the ratio of vertices that remain uninfected at the end of disease over the total numbers of vertices._  
Therefore, our problem is: given a graph \(G=(E,V)\), SIR model, and a protection budget \(k\), the goal is to find a set of vertices \(\mathcal{S}\subseteq V\) such that  
\[\theta^{*}=\arg\max_{\mathcal{S}\subseteq V}\sigma, \tag{2}\]  
with \(|\mathcal{S}|=k\). However, the problem (2) is NP-Hard (see [34]). Figure 1: The left side shows a graph without protection or infection. On the right side, we see an infected node (red) and a protected node (green) in the same graph. It is well known that an index to measure the connection of a graph is the efficiency of the networks (see [35]). High connectivity of the graph indicates high efficiency. In [27] the authors show that the DIL-\(W^{\alpha}\) ranking provides good results, regarding the rate of decline in network efficiency (more details in [28]), when it comes to eliminating the nodes best positioned by this ranking.