Fast and accurate detection of spread source in large complex networks

Area of Science:

• Network Science
• Epidemiology
• Computer Science

Background:

• Identifying spread origins in complex networks is crucial for applications like epidemic control and rumor tracking.
• Existing methods, such as the Pinto, Thiran, and Vetterli Algorithm (PTVA), utilize observer data but can be computationally intensive.
• Observer information quality can vary, impacting the accuracy of source localization.

Purpose of the Study:

• To develop a more efficient and accurate algorithm for locating spread sources in complex networks.
• To address the limitations of existing methods by incorporating observer information quality.
• To reduce the computational complexity of spread source localization.

Main Methods:

• Proposed a Gradient Maximum Likelihood Algorithm (GMLA) that prioritizes high-quality observer data.
• GMLA filters out observers with low-quality information (late spread detection times).
• Evaluated GMLA's performance against PTVA on synthetic and real-world networks (Gnutella), considering unknown spreader identities.

Main Results:

• GMLA significantly reduces computational complexity from O(N^α) to O(N^2 log N).
• GMLA demonstrates superior localization accuracy compared to PTVA, especially on scale-free networks.
• The algorithm performs effectively even when the identities of spreaders are unknown to observers.

Conclusions:

• The Gradient Maximum Likelihood Algorithm (GMLA) offers a more efficient and accurate approach to spread source localization in complex networks.
• Prioritizing high-quality observer data is key to improving localization performance.
• GMLA provides a valuable advancement for applications requiring rapid and precise identification of spread origins.