Abstract
Locating the origins of diffusion processes in complex networks—such as the spread of infectious diseases, computer viruses, or social media rumors—is a critical task for containment and mitigation. While single-source identification has been extensively studied, real-world scenarios often involve multiple simultaneous origins. This paper presents a novel "K-center" method for multi-source identification. By transforming probabilistic transmission rates into "effective distances," the complex spatiotemporal dynamics of diffusion are linearized, allowing for efficient network partitioning. The proposed algorithm achieves a computational complexity of $O(mn \log \alpha)$, significantly outperforming existing $O(n^k)$ approaches. Evaluations on real-world datasets, including the North American power grid and Facebook social graphs, demonstrate superior accuracy in source localization even when the number of sources is unknown.
Introduction
In an increasingly interconnected global society, the rapid "diffusion" of harmful entities poses a significant threat. Whether it is a biological pathogen like Ebola, a malicious computer worm like Cryptolocker, or a viral rumor on social media platforms, the ability to quickly identify the "Patient Zeros" is paramount for effective quarantine and intervention.
Historically, source identification research has focused on finding a single origin. However, modern diffusion events are rarely so simple; they often emerge from multiple locations simultaneously due to global travel or coordinated digital campaigns. Identifying multiple sources is notoriously difficult due to the heterogeneous nature of network structures and the exponential computational cost associated with traditional multi-source search algorithms. Furthermore, in practical scenarios, the number of sources ($k$) and the start time of the diffusion ($T$) are typically unknown.
Methodology
The SI Diffusion Model
The researchers base their work on the Susceptible-Infected (SI) model. In this model, a node is either susceptible to the entity or has already been infected. Once infected, a node remains in that state and can transmit the entity to its neighbors with a certain probability.
Linearization via Effective Distance
The core innovation of this approach is the transition from standard "hop counts" to "effective distance." In a standard network view, diffusion appears as a chaotic, stochastic process. By defining effective distance as a function of transmission probability—where low probability corresponds to a large distance and high probability to a short distance—the diffusion process is "stretched" into a uniform wave moving outward from the source.
The K-center Algorithm
The K-center method treats source identification as a network partitioning problem, similar to K-means clustering. The algorithm follows an iterative process:
- Voronoi Partitioning: Every infected node is assigned to its nearest estimated source based on effective distance.
- Centroid Recalculation: For each partition, the algorithm identifies a new center node that minimizes the sum of effective distances to all other nodes in that partition.
- Convergence: This process repeats until the centers stabilize. The authors mathematically proved that the objective function is monotonically decreasing, ensuring convergence.
To handle large-scale networks, the team utilized the Pettie-Ramachandran algorithm for shortest path calculations, achieving a complexity of $O(mn \log \alpha)$. This represents a massive speedup over previous $O(n^3)$ or $O(n^k)$ methods, making it viable for massive social networks.
Experimental Evaluation
The method was tested against three real-world network topologies:
- North American Power Grid: 4,941 nodes representing physical infrastructure.
- Yeast Protein-Protein Interaction Network: 2,361 nodes representing biological pathways.
- Facebook Network: A large-scale social graph with 45,813 nodes.
Estimation of $k$ and $T$
A significant challenge in multi-source identification is not knowing how many sources exist. The researchers developed a heuristic based on the stability of the estimated spreading time ($T$). They observed that as the assumed number of sources ($k$) increases toward the true value, the estimated $T$ decreases. Once $k$ reaches the actual number of sources, $T$ stabilizes. This provides a reliable "stopping condition" for the algorithm.
Key Results
The K-center method demonstrated superior accuracy across all test networks. In the Facebook dataset, the algorithm consistently identified sources within 3–4 hops of the ground truth, even with five simultaneous origins. This significantly outperformed competing methods like Dynamic Age and Multi-Rumor-Center (MRC).
In the Yeast network, the heuristic for estimating the number of sources was particularly effective, correctly identifying $k=2$ in over 80% of trials. The computational efficiency was also confirmed, with the algorithm scaling gracefully to the nearly 46,000 nodes of the Facebook graph.
Conclusion and Future Work
The K-center method provides a robust and efficient framework for identifying multiple origins in complex diffusion processes. By linearizing the problem through effective distance, it brings geometric optimization tools to the study of network epidemics.
Future research will focus on relaxing the "complete observation" requirement, as real-world data is often partial. Additionally, incorporating "community structure" could further refine the partitioning process and improve localization accuracy in highly clustered environments.
Summary updated