# Predicting and Modeling Wildfire Propagation Areas with BAT and Maximum-State PageRank
## 2 Overview of Wildfire Propagation, Scale-Free Network, Barabasi-Albert Model, and BAT
### PageRank  
In recent years, numerous algorithms have been proposed to rank the importance of nodes in scale-free networks. Among these algorithms, PageRank used by Google in their search engine was historically the first and most well-known algorithm [54; 55]. Simply follows the basic property of a scale-free network, whereas PageRank assumes that many important nodes (websites) are expected to receive more links from other nodes (websites) [54].  
The PageRank of a node (page/website) \(i\) after obtaining a degree, as listed in Table 1, is given as follows [44]:  
\[PR(i)=(1-d)+d\times[PR(i_{1})/Deg_{out}(i_{1})+\ldots+PR(i_{n})/Deg_{out}(i_{n})] \tag{4}\]  
where  
* \(i_{1},\,i_{2},\,\ldots,\,i_{ini}\) are nodes with links to node \(i\)
* damping factor \(d\) is a number between 0 and 1 and it accounts for the \((1-d)\) chance of jumping into an arbitrary node.
* \(Deg_{out}(j)\) is the out-degree number of a node, i.e., the number of links going from node \(j\).  
As an important node refers to other important nodes that are linked to it, the steps of the PageRank algorithm [53] are listed in Algorithm 1.  
```
Input A scale-free network \(G(V,E)\) with node set \(V=\{0,1,\ldots,(n-1)\}\) and link set \(E\). Output Probability distribution, i.e., the PageRank value, PR(\(i\)) for all nodes \(i\in V\).
1: Let time \(t=0\). Set the initial PR(\(i\)) as \(1/n\) for node \(i\) and \(i=0,\,1,\ldots,\,(n-1)\).
2: Update PR(\(i\)) based on Equation (4) for all \(i\in V\).
3: Redistribute PR(\(i\)) equally among the other nodes for all nodes \(i\) with Degout(\(i\)) = 0.
4:if there is no change in PR(\(i\)) for \(i=0,\,1,\,2,\ldots,(n-1)\)then go to Stop.
5:else if let \(t=t+1\)return to line 2.
```  
**Algorithm 1** PageRank Algorithm [53]  
Line 1 initializes all node rankings with equal weights. Line 2 implements the basic concept of the PageRank defined in Equation (4) to update the node ranking recursively by adding the weight of every node that is linked to it and dividing it by the number of links emanating from the referring node [54]. The redistribution in line 3 is based on an underlying assumption that users will continue to search WWW if they enter a node (webpage in [54]) without exiting the link, i.e., a dead end. The procedure is repeated to update the rough PageRank value of each node in line 3 to converge to a constant number  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & **0** & **1** & **2** & **3** & **4** & **5** & **6** & **7** \\ \hline
1 & 0 & 0 & 0 & 0 & 0 & 0.166667 & 0.166667 & 0.2 \\
2 & 0 & 0 & 0 & 0 & 0 & 0.166667 & 0.166667 & 0 \\
3 & 0 & 0 & 0 & 0 & 0 & 0.166667 & 0.166667 & 0.2 \\
4 & 0 & 0 & 0 & 0 & 0 & 0.166667 & 0.166667 & 0.2 \\
5 & 0.5 & 0.333333 & 0.5 & 0.333333 & 0.333333 & 0 & 0.166667 & 0 \\
6 & 0 & 0.333333 & 0.5 & 0.333333 & 0.333333 & 0.166667 & 0 & 0.2 \\
7 & 0.5 & 0.333333 & 0 & 0.333333 & 0.333333 & 0 & 0.166667 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Normalized adjacency matrix based on each column.  
The output value PR(\(i\)) for all nodes \(i\) in the PageRank algorithm indicates the probability distribution of a user clicking on webpages (nodes) randomly to arrive at any particular webpage (node) [54; 55]. Hence, the PR(\(i\)) can be adapted to estimate the probability that a wildfire randomly ignites and propagates in an area. Thus, to model the growth of wildfire propagation and describe the related burning areas, PageRank is adopted to measure the importance of nodes (areas) and is then transformed to the appropriate probability, which is used in the proposed dynamic BAT.