Locating the Source of Information in Social Networks using Critical Nodes

Locating the information source within social networks is crucial to understand information propagation. The source can be detected based on specific nodes known as observation nodes, and identifying them is a critical challenge that can significantly affect the accuracy of identification. To address this issue, this study proposes a novel source detection approach based on the Susceptible-Infected (SI) model and the Critical Node Problem (CNP). CNP involves identifying a subset of nodes within a graph whose removal results in the maximum reduction of a given connectivity metric, thereby isolating significant areas within the graph. A heuristic algorithm was developed, grounded in the maximal independent set for general graphs to solve the CNP, allowing the identification of the most crucial observation nodes that enhance the accuracy and using the data recorded from them to estimate the localization of the source. Experimental evaluations on various real-world networks showed that the proposed approach achieved a source detection accuracy of up to 89%, outperforming existing methods. These results demonstrate the robustness of the proposed approach, highlighting its potential to significantly improve accuracy in network-based source localization tasks across multiple applications.