# Heuristics for Spreading Alarm throughout a Network
## 3 The Proposed Algorithms to Obtain the Shortest Burning Sequence
### Maximum Eigenvector Centrality Heuristic  
The simplest approach to a burning number sequence seems to be a greedy algorithm. If the value of our guess of the burning number is labelled \(bg\) (aka burn guess), then we want to select such a node, which neighborhood up to the graph distance \(bg-1\) should have the biggest number of nodes (which we then burn). While we could go through all the nodes and find out the one with the maximum neighborhood, such an approach seems to be too computationally demanding. One may guess, that such nodes should be somewhere near the \"center\" of the network. However, what is the center of a network? There exist various definitions of centrality. The most popular one is a node \(v\) with a minimum eccentricity, i.e., a node with the shortest of the maximum graph distance between \(v\) and any other node of the network. However, in our pivotal trials we had more success with maximum eigenvector centrality [26], which we further used. Therefore, for the number of rounds \(i\) from \(bg\) to 1 we always selected the node \(x_{i}\) with the maximum eigenvector centrality value. The maximum eigenvector centrality value is always evaluated for the remaining reduced network with unburned nodes. Only in the case, when for the number \begin{table}
\begin{tabular}{c c c c c|c c c|c|c} \hline \hline  & & & & & \multicolumn{3}{c|}{**Burning Number by Tested**} & & \\  & & & & & & & Algorithms & & \\
**Name of** & **Description** & **\(|\)V** & **\(|\)E** & **\(|\)V** & **\(|\)V** & **\(|\)V** & **\(|\)V** & **\(|\)V** \\
**Network** & **Description** & **\(|\)V** & **\(|\)E** & **\(|\)V** & **\(|\)V** & **\(|\)V** & **\(|\)V** & **\(|\)V** \\ \hline _line of 49 nodes_ & artificial example & 49 & 48 & 2 & **12** & **8** & **7** & **7** & 42\% \\ _squaredLdealBurn7_ & artificial example & 231 & 418 & 4 & **15** & **10** & **7** & **7** & 53\% \\ _Reed98_ & Facebook & 962 & 18,812 & 313 & 9 & **4** & **4** & **4** & 56\% \\ _polblogs_ & polit. blogosphere & 643 & 2280 & 165 & **12** & **6** & **7** & **6** & 50\% \\ _bi-1k-2k_ & generated graphs & 1000 & 1996 & 69 & 9 & **6** & **6** & **6** & 33\% \\ _malibas_ & economic problem & 1258 & 7513 & 206 & 9 & **6** & **6** & **6** & 33\% \\ _netscience_ & co-authorship & 379 & 914 & 34 & **12** & **7** & **7** & **6** & 50\% \\ _lattice2D_ & \(33\times 33\) regular lat. & 1089 & 2112 & 4 & **24** & **14** & **13** & **13** & 46\% \\ _lattice3D_ & \(10\times 10\times 10\) reg. lat. & 1000 & 2700 & 6 & **15** & **11** & **11** & **10** & 33\% \\ _binary tree_ & regular & 1000 & 999 & 3 & **21** & **10** & **10** & **10** & 52\% \\ _ternary tree_ & regular & 1000 & 999 & 4 & **15** & **7** & **7** & **7** & 53\% \\ _Geometric random_ & 10 generated nets & 1000 & 3764.4 & 17.9 & **21** & **12.8** & **11.7** & **11** & 48\% \\ _Erdős-Ranyi_ & 10 generated nets & 1000 & 6013.3 & 24.2 & 6 & **5** & **5** & **5** & 17\% \\ _Barahsi-Albert_ & 10 generated nets & 1000 & 2994 & 80.1 & 9 & **4.9** & **4.9** & **4.9** & 46\% \\ \hline \multicolumn{8}{c}{average improvement achieved by the best Algorithm 3 compared to Bonato:} & & & **37\%** \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Burning number results for tested networks and algorithms. of rounds \(i\) the component of the remaining reduced network with maximum diameter has a radius smaller or equal to \(i\), the selected node \(x_{i}\) is the node with minimum eccentricity from that component. The neighborhood subgraph of nodes within the graph distance \(i-1\) from \(v\) is however determined from the original network, which may occasionally burn a few more nodes. Having a series of selected nodes \(x_{1}\),..., \(x_{i}\), together with their (diminishing) neighborhood subgraphs, we remove from the original network every edge connecting a couple of nodes from these subgraphs, and then continue to select the next node \(x_{i}\) in the next round.