# Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction
## 2 Methods
### Source Localization on Arbitrary Trees  
Consider first the case of an arbitrary tree. In graph theory, a tree is defined as a connected, undirected graph that contains no closed loops. Obviously, describing the diffusion process occurring in trees presents a natural advantage because there is only one path between the source and each observer. Recall that \(O=\{o_{1},o_{2},...,o_{K}\}\) is a set of \(K\) observers with diffusion timestamps \(T_{O}=[t_{o_{1}},t_{o_{2}},...,t_{o_{K}}]^{T}\). Since the diffusion delays \(\{\theta_{uv}\}\) along edges are random variables, the arrival times \(\{\tau_{o_{k}}\}\) for observations can also be viewed as random variables. Suppose that \(s\) is the source node and \(t_{0}\) is the initial time that \(s\) starts diffusion, and let \(\mathcal{P}(s,o_{k})\subset E\) be the path from the node \(s\) to the observer \(o_{k}\) with a length \(d_{sk}=|\mathcal{P}(s,o_{k})|\). As all diffusion delays \(\{\theta_{uv}\}\) along edges are i.i.d Gaussian variables \(\theta_{uv}\stackrel{{ i.i.d. }}{{\sim}}\mathcal{N}(\mu,\sigma^{2})\), the arrival time \(\tau_{o_{k}}\) of each observer \(o_{k}\in O\) can be inferred to follow a Gaussian distribution \(\tau_{o_{k}}\sim\mathcal{N}(t_{0}+d_{sk}\cdot\mu,d_{sk}\cdot\sigma^{2})\). Therefore, the joint distribution of the arrival time \(\mathcal{T}_{O}=[\tau_{o_{1}},\tau_{o_{2}},...,\tau_{o_{K}}]^{T}\) satisfies a K-dimensional Gaussian form \(\mathcal{T}_{O}\sim\mathcal{N}(\mu_{s},\Lambda_{s})\). Taking the above, the likelihood probability of observing the diffusion timestamps \(T_{O}\) at arrival time \(\mathcal{T}_{O}\) with respect to the source node \(s\), the initial time \(t_{0}\) and the delay standard deviation along edges \(\sigma\) is expressed as follows:  
\[P(T_{O}|s,t_{0},\sigma)=\frac{1}{(2\pi)^{K/2}|\Lambda_{s}|^{1/2}}exp(-\frac{1 }{2}(T_{O}-\mu_{s})^{T}\Lambda_{s}^{-1}(T_{O}-\mu_{s})). \tag{1}\]The mean vector \(\mu_{s}\) and the covariance matrix \(\Lambda_{s}\) of the joint Gaussian distribution are as follows:  
\[[\mu_{s}]_{k}=t_{0}+d_{sk}\cdot\mu \tag{2}\] \[[\Lambda_{s}]_{i,j}=\sigma^{2}\cdot[\Lambda_{ps}]_{i,j}, \tag{3}\]  
where \([\Lambda_{ps}]_{i,j}=|\mathcal{P}(s,o_{i})\cap\mathcal{P}(s,o_{j})|\) denotes the path intersection matrix, and the element of matrix represents the number of joint edges on two paths from node \(s\) to observer \(o_{i}\) and \(o_{j}\). Since we consider that no prior information is available on the location of the source node, the optimal estimator is the maximum likelihood estimator (MLE):  
\[(\hat{s},\hat{t_{0}},\hat{\sigma})=\underset{s\in V\backslash O \cdot t_{0},\sigma}{argmax\ }P(T_{O}|s,t_{0},\sigma). \tag{4}\]  
Let \(w_{s}=[w_{s1},w_{s2},...,w_{sK}]^{T}\) represent a K-dimensional column vector of the differences between the observation time and the mean arrival time for the observers:  
\[w_{sk}=t_{o_{k}}-\mu\cdot d_{sk}. \tag{5}\]  
For any estimator \(\hat{s}\), by maximizing Equation (1) with respect to \(t_{0}\), the MLE of \(t_{0}\) can be represented as  
\[\hat{t_{0}} =argmin_{t_{0}}(T_{O}-\mu_{s})^{T}\Lambda_{s}^{-1}(T_{O}-\mu_{s}) \tag{6}\] \[=argmin_{t_{0}}(w_{s}-t_{0}I)^{T}\Lambda_{s}^{-1}(w_{s}-t_{0}I)\] \[=I^{T}\Lambda_{ps}^{-1}w_{s}/I^{T}\Lambda_{ps}^{-1}I,\]  
where \(I=[1,1,...1]^{T}\) denotes a K-dimensional column vector full of 1s.