# Heuristics for Spreading Alarm throughout a Network
## 3 The Proposed Algorithms to Obtain the Shortest Burning Sequence
### Maximum Eigenvector Centrality Heuristic
\(\mathbf{TG}\) in the Algorithm 1 means a temporary graph with the same nodes as graph \(\mathbf{G}\), from which are successively deleted edges between the union of nodes \(\mathbf{V}_{e}(x_{i})\) from the neighborhood of nodes from the sequence \(\mathbf{X}\). The sequence \(\mathbf{X}\) is successively enlarged. The range of this neighborhood \(\mathbf{V}_{e}(x_{i})\), is successively diminishing, i.e., in the beginning, the nodes belonging to \(\mathbf{V}_{e}(x_{i})\) are all the nodes distanced up to \(bg\)-1 from the node \(x_{1}\), while the last vertex set \(\mathbf{V}_{e}(x_{i})\) contains only the node \(x_{bg}\). A component of a graph is a subgraph in which any two nodes are connected by a path, and to which no additional node can be added. The eccentricity of a node \(v\) in a connected graph is the maximum graph distance between \(v\) and any other node \(u\) of \(\mathbf{G}\). The graph diameter is the maximum eccentricity. The graph radius is the minimum graph eccentricity. The function eigen_centrality(\(\mathbf{G}\)) takes a graph \(\mathbf{G}\) and returns the eigenvector centralities of positions of vertices \(v\) within it. The function ego (\(\mathbf{G}\), _order_, \(x_{i}\)) calculates the vertices \(\mathbf{V}_{e}(x_{i})\) of the neighborhood of the given vertex \(x_{i}\) of graph \(\mathbf{G}\) within the given graph distance over from \(x_{i}\). For the graph \(\mathbf{G}=(\mathbf{V},\mathbf{E})\), let \(\mathbf{S}_{i}\subset\mathbf{V}\) be a subset of vertices of \(\mathbf{G}\), such that \(\mathbf{S}_{i}=\cup_{j=1}^{j-i}\mathbf{V}_{e}(x_{j})\). Then the induced subgraph \(\mathbf{G}[\mathbf{S}_{i}]\) is the graph whose vertex set is \(\mathbf{S}_{i}\) and whose edge set consists of all of the edges in \(\mathbf{E}\) that have both endpoints in \(\mathbf{S}_{i}\). Its edges are removed from \(\mathbf{TG}\). Since for \(|\mathbf{V}|=n\) and \(|\mathbf{E}|=m\) the \(bg\) is bounded from above by \(n\), the largest eigenvalue can be found with complexity O(\(m\)\(\log n\)) which likely dominates the finding ego neighborhood by breath-first search, and the algorithm is called by binary search O(\(\log n\)) times, the complexity of Algorithm 1 is less than O(\(m\)\(n\)\(\log^{2}n\)). ```
0: A network \(\mathbf{G}=(\mathbf{V},\mathbf{E})\) and a guess value \(bg\) of a burning number
0: A sequence \(\mathbf{X}\)= \(x_{1}\),..., \(x_{bg}\) of nodes from \(\mathbf{G}\)
1:\(\mathbf{X}\leftarrow\emptyset\); \(\mathbf{TG}\leftarrow\mathbf{G}\);
2:for\(i=1,\,\ldots,\,bg\)do
3: maxDiameterComp \(\leftarrow\) component of \(\mathbf{TG}\) with maximum diameter
4:if\(i\geq\) radius of maxDiameterComp
5:then\(x_{i}\gets v\in\mathbf{V}_{\text{\(maxDiameterComp)}\setminus\mathbf{X}}\)\(eccentricity(v,\text{maxDiameterComp)}\)
6:else\(x_{i}\gets v\in\mathbf{V}_{\text{\(post\))}}\max\limits_{v\in\mathbf{V}(\text{\(post\))}\setminus\mathbf{X}}\)\(eigen\_centrality(\mathbf{v},\mathbf{TG})\);
7:\(\mathbf{X}\leftarrow\mathbf{X}\cup x_{i}\)
8:\(\mathbf{V}_{e}(x_{i})\leftarrow\text{ego}(\mathbf{G},\,bg-i,\,x_{i})\);
9:\(\mathbf{S}_{i}\leftarrow\cup_{j=1}^{j-i}\mathbf{V}_{e}(x_{j})\);
10:\(\mathbf{TG}\leftarrow\mathbf{G}(\mathbf{V},\mathbf{E}(\mathbf{TG}))\backslash\mathbf{E}(\mathbf{G}[\mathbf{S}_{ i}])\);
11:if\(\mathbf{S}_{i}\equiv\mathbf{V}\)then return \(\mathbf{X}\) else return FAILED TO BURN
```  
**Algorithm 1** Maximum eigenvector centrality heuristic for a shortest burning sequence  
The greedy approach of Algorithm 1 often fails, because by burning the graph from its center, the unburned nodes are likely left in too many unconnected components, when each component spends at least one node in the \(\mathbf{X}\) sequence to be burned. Algorithm 1 fails to find an optimum even for one of the simplest graphs, a path. This is shown in Figure 2. Its left-hand side (a), going from top to bottom, shows an ideal run with burning number 3.