# Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction
## 3 Experiments and Analysis
### Results on General Graphs  
Simulations on general graphs are performed on synthetic networks and real networks. For synthetic networks, we consider three common types, i.e., Erdos-Renyi random network \(\text{ER}(N,k)\), Barabasi-Albert scale-free network \(\text{BA}(N,k)\) and Watts-Strogatz small-world network \(\text{WS}(N,k,p)\), where \(N\) denotes the number of nodes, \(k\) denotes the average degree, and \(p\) denotes the rewiring probability in WS networks. A brief introduction of some basic topological features is shown in Table 2.  
Figure 6 shows the performance on three synthetic networks with an average degree \(\langle k\rangle=4\) and signal-to-noise ratio \(\mu/\sigma=3\). Unlike the case on arbitrary trees in previous section, the algorithm performances vary greatly on general graphs. The results demonstrate a uniform ranking of the four methods under all three metrics that GLAD-modified \(>\) TRBS \(>\) GLAD-naive \(>\) GAU. Although GLAD-naive presents satisfactory results in arbitrary trees, its performance is just normal in general trees. However, one advantage of GLAD-naive is maintained in that it performs consistently better than GAU, thus illustrating the necessity of estimating diffusion parameters for different nodes. In arbitrary trees, GLAD-naive always performs better than GLAD-modified, whereas the situation is completely reversed in general graphs, which explains once again the great need to design a special algorithm on general graphs. Theoretically, if one BFS tree rooted at one node is indeed the diffusion tree, GLAD-naive will definitely outperform GLAD-modified, which is consistent with the results in arbitrary trees. Nevertheless, that condition is difficult to satisfy in dense networks because there are so many BFS trees in such networks. In addition, the uncertainty of the diffusion delay along edges further weakens our ability to determine which tree is the true diffusion tree. Taken together, although the likelihood function for GLAD-modified is just an approximation of GLAD-naive, it can present a much better performance on general graphs. Another important finding is that it is often easier to locate the diffusion source in a homogeneous network like ER and WS than in a heterogeneous one like BA. The greatest obstacle of source localization problem in a heterogeneous network is the information redundancy of observers. Consider a simple heterogeneous case of a star-like network with one center node connected with many peripheral nodes. In such a network, regardless of which node is the real source, it cannot be uniquely identified since we do not know the exact initial time of diffusion. Actually, the information provided by peripheral observers is equivalent to the information provided by the center node, thus increasing the difficulty of locating the source in a heterogeneous network. However, such situations do not occur in homogeneous networks because there are only a few peripheral nodes in such networks. Next, we consider the results of source localization in real networks. Nine networks from different fields are used to compare the performances. States [24] is a network of 48 contiguous states and the District of Columbia of USA, where an edge exists if two states share a border. Dolphins [25] contains the frequent associations between 62 dolphins in a community. Polbooks [26] represents the frequent co-purchasing books about US politics sold by the online bookseller Amazon.com. Football [27] is a network of American football games between Division IA colleges during regular season Fall 2000. Enron [28] email communication network covers the communications among the employees in Enron corporation between 1999 and 2003. Jazz [29] is a social collaboration network where nodes are Jazz