# Software Fault Localization Based on SALSA Algorithm
## 3 Proposed Approach
### Sort Suspicious Statements  
In this paper, the random walk model is used in this stage to evaluate the importance of nodes in the network structure of the RSCDG. The suspicion values of statements serve as node weights that are propagated along the links between nodes, ultimately resulting in a ranking of suspicious statements. In the SALSA algorithm, random walk theory and Markov chains are combined to analyze the web page link structure by constructing a bipartite undirected graph, calculating the scores of each node, including Hub scores and Authority scores. This method involves analyzing two distinct Markov chains: the hub chain and the authority chain. In the hub chain, the random walk starts at a hub node, moves to an authority node via an outgoing link, and then returns to another hub node via an incoming link. The hub chain primarily focuses on the out-degree of nodes, that is, how many other nodes a particular node points to. The authority chain is the reverse of the hub chain. The authority chain starts at an authority node, moves to a hub node via an incoming link, and then returns to another authority node via another outgoing link. The authority chain primarily focuses on the in-degree of nodes, that is, how many other nodes point to that particular page. A webpage may score high in the hub chain, indicating that it is an important source of information. At the same time, it may also score high in the authority chain, indicating that it is an important receiver of information. In this paper, the RSCDG is constructed as an undirected bipartite graph, i.e., RSCDG = (Vh, Va, E). Node set Vh: Contains all nodes with an out-degree greater than 0, which are nodes that point to other nodes. Node set Va: Contains all nodes with an in-degree greater than 0, which are nodes that are pointed to by other nodes. Edge set E: Contains all the linking relationships from one node to another. In the bipartite graph we derived, we will perform two types of random walks. First, a random walk on the hub chain: starting from a node in Vh, moving to a node on the authority side via an edge, and then returning to a node on the hub side via another edge. Second, a random walk on the authority chain: starting from a node in Va, moving to a node on the hub side via an edge, and then returning to a node on the authority side via another edge. The hub chain simulates a random walk on the hub side, where each state in the chain corresponds to a node in Vh, and transitions between states correspond to walks from one hub node to another through an intermediary authority node. The authority chain simulates a random walk on the authority side, where each state in the chain corresponds to a node in Va, and transitions between states correspond to walks from one authority node to another through an intermediary hub node. To implement a random walk on a Markov chain, we need to define a transition probability matrix. Since we are conducting random walks on two Markov chains, we need to create two random matrices: the hub matrix H and the authority matrix A. The acquisition of matrices H and A is as follows. Firstly, based on the linking structure of the RSCDG, we obtain the adjacency matrix W corresponding to the directed graph RSCDG. If node i points to node j, then the value of Wij is 1; otherwise, it is 0. Then, based on the adjacency matrix W, we obtain the row-normalized matrix Wr and the column-normalized matrix Wc. The row-normalized matrix Wr is obtained by dividing each non-zero element in W by the sum of the elements in that row. This operation normalizes the sum of each row to 1, representing the probability distribution of links emanating from node i, as shown in Equation (1). Note that if \(\sum_{k=1}^{n}W_{ik}=0\), then \((W^{r})_{ij}=0\). \[(W^{r})_{ij}=\frac{W_{ij}}{\sum_{k=1}^{n}W_{ik}} \tag{1}\]The column-normalized matrix \(\mathrm{W^{c}}\) is derived by dividing each non-zero element in matrix \(\mathrm{W}\) by the sum of the elements in its corresponding column.