Random Full-Order-Coverage Based Rapid Source Localization With Limited Observations for Large-Scale Networks

Abstract

The rapid spread of misinformation in social media presents significant threats to society, highlighting the importance of early inference of the diffusion source to minimize potential losses. Although sensor-based methods have proven effective in source localization, their reliance on sufficient information from all sensors restricts their ability to accurately identify the source with limited data from a few sensors, thereby limiting their application in early propagation scenarios. To address these challenges, this paper introduces a novel method called <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</u> andom <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</u> ull-order-coverage based <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">r</u> apid <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</u> ource <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</u> ocalization (RF-RSL). RF-RSL improves the <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">g</u> reedy-based <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</u> trategy (GS) in a random deployment way to quickly provide extensive coverage of deployed sensors over a wide area, followed by the <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">l</u> imited-information-oriented <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</u> trategy (LS) for source inference with an early response mechanism. Specifically, LS incorporates a quick preprocessing step to eliminate invalid candidates and a novel source estimator for precise source identification. The experiments demonstrate that RF-RSL consistently outperforms the best baseline by at least 5% and exhibits exceptional advantages of up to 30% when deployed with fewer sensors. Moreover, RF-RSL showcases a remarkable speed advantage of over 10 times compared to the best baseline in large-scale networks.