# Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction
## 2 Methods
### Source Localization on General Graphs  
When information is diffused on general graphs, the source localization problem will be more difficult. In general graphs, a spanning tree grows naturally with the diffusion process based on the sequence at which information first reaches each node. Unfortunately, although the real diffusion process in the network is a deterministic process, we cannot ascertain which spanning tree is the actual diffusion tree because the exact diffusion delays along edges are unknown. For that reason, to find the MLE for the diffusion parameters \((t_{0},\sigma)\) and the source \(s\), we need to optimize the likelihood function in Equation (1) over all possible spanning trees rooted at each candidate source. However, the naive strategy is intractable in practice because, even in medium-sized networks, the number of spanning trees is too large and the computational cost is prohibitive for modern computers. One possible solution is to assume that the actual diffusion tree is a breadth-first search (BFS) tree, instead of an arbitrary spanning tree. This assumption corresponds to the case that information travels from the source to each observer along the shortest mean diffusion delay path, which is reasonable and intuitive. Nevertheless, even for the same root node, different search strategies may lead to different BFS trees. The naivest approach is to randomly select a BFS tree as the diffusion tree, although this leads to a poor performance according to our numerical experiments in the next section. In the following, we introduce an approximation method to efficiently locate the source in general graphs. In graph theory, an important feature is that for any BFS tree with the same root \(s\), the distance \(d_{sk}\) between \(s\) and each observer \(o_{k}\) never changes. Recall the diffusion parameters \(\mu_{s}\) and \(\Lambda_{s}\). As can be seen in Equation (2), the mean vector \(\mu_{s}\) does not change in different BFS trees. On the other hand, from Equation (3), we could find that, although the covariance matrix \(\Lambda_{s}\) may vary in different BFS trees, the diagonal elements in each \(\Lambda_{s}\) remain unchanged. In addition, matrix \(\Lambda_{s}\) is diagonally dominant and sparse in large networks so that the diagonal matrix of \(\Lambda_{s}\) can replace it with little effect on parameter estimation and likelihood maximization. Inspired by these phenomena, we proposed to perform the optimization with a modified function:  
\[\tilde{P}(T_{O}|s,t_{0},\sigma)=\frac{1}{(2\pi)^{K/2}|D_{s}|^{1/2}}exp(-\frac{ 1}{2}(T_{O}-\mu_{s})^{T}D_{s}^{-1}(T_{O}-\mu_{s})), \tag{14}\]  
where \(D_{s}=diag(\Lambda_{s})\) denotes the diagonal matrix of the original covariance matrix \(\Lambda_{s}\). As \(D_{s}\) does not change in different BFS trees, one can randomly build a BFS tree and obtain it. In the new optimization problem, the corresponding MLE for \(t_{0}\) can be given by  
\[\tilde{t_{0}} =I^{T}D_{ps}^{-1}w_{s}/I^{T}D_{ps}^{-1}I=\sum_{k}d_{sk}^{-1}w_{sk} /\sum_{k}d_{sk}^{-1}, \tag{15}\]  
where \(w_{sk}=t_{o_{k}}-\mu\cdot d_{sk}\) is the same as in Equation (5). Then, the auxiliary variable should be  
\[\tilde{z}_{s} =(w_{s}-\tilde{t_{0}}I)^{T}D_{ps}^{-1}(w_{s}-\tilde{t_{0}}I)=\sum _{k}(w_{sk}-\tilde{t_{0}})^{2}d_{sk}^{-1}. \tag{16}\]  
The MLE of \(\sigma\) remains the same as in a previous subsection:  
\[\tilde{\sigma}=(\tilde{z}_{s}/K)^{1/2}. \tag{17}\] \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**MLE** & **B** & **C** & **D** & **E** & **G** & **H** & **I** & **K** \\ \hline \(\tilde{t}_{0}\) & 0.404 & \(-0.596\) & \(-0.177\) & \(-1.177\) & 0.489 & \(-0.511\) & \(-\)**0.424** & \(-1.424\) \\ \(\hat{\sigma}\) & 1.056 & 1.056 & 0.583 & 0.583 & 1.108 & 1.108 & **0.099** & 0.099 \\ \(OBJ_{s}\) & 5.700 & 6.617 & 2.133 & 3.050 & 5.989 & 6.906 & \(-\)**8.499** & \(-7.583\) \\ \hline \hline \end{tabular}
\end{table}