Locating the Source of Information in Social Networks using Critical Nodes
Received: 15 October 2024 | Revised: 6 November 2024 | Accepted: 16 November 2024 | Online: 2 February 2025
Corresponding author: Mohammed Amin Tahraoui
Abstract
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.
Keywords:
source detection, information diffusion, critical nodes, observation nodes, social networksDownloads
References
S. Shelke and V. Attar, "Source detection of rumor in social network – A review," Online Social Networks and Media, vol. 9, pp. 30–42, Jan. 2019.
M. Anwer, S. M. Khan, M. U. Farooq, and Waseemullah, "Attack Detection in IoT using Machine Learning," Engineering, Technology & Applied Science Research, vol. 11, no. 3, pp. 7273–7278, Jun. 2021.
E. Yoo, W. Rand, M. Eftekhar, and E. Rabinovich, "Evaluating information diffusion speed and its determinants in social media networks during humanitarian crises," Journal of Operations Management, vol. 45, pp. 123–133, Jul. 2016.
S. S. Ali, T. Anwar, and S. A. M. Rizvi, "A Revisit to the Infection Source Identification Problem under Classical Graph Centrality Measures," Online Social Networks and Media, vol. 17, May 2020, Art. no. 100061.
F. Yang, R. Zhang, Y. Yao, and Y. Yuan, "Locating the propagation source on complex networks with Propagation Centrality algorithm," Knowledge-Based Systems, vol. 100, pp. 112–123, May 2016.
S. Xu, C. Teng, Y. Zhou, J. Peng, Y. Zhang, and Z. K. Zhang, "Identifying the diffusion source in complex networks with limited observers," Physica A: Statistical Mechanics and its Applications, vol. 527, Aug. 2019, Art. no. 121267.
N. Karamchandani and M. Franceschetti, "Rumor source detection under probabilistic sampling," in 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, Jul. 2013, pp. 2184–2188.
W. Li, C. Guo, Y. Liu, X. Zhou, Q. Jin, and M. Xin, "Rumor source localization in social networks based on infection potential energy," Information Sciences, vol. 634, pp. 172–188, Jul. 2023.
P. C. Pinto, "Locating the Source of Diffusion in Large-Scale Networks," Physical Review Letters, vol. 109, no. 6, 2012.
F. Yang et al., "Locating the propagation source in complex networks with a direction-induced search based Gaussian estimator," Knowledge-Based Systems, vol. 195, May 2020, Art. no. 105674.
R. Paluch, X. Lu, K. Suchecki, B. K. Szymański, and J. A. Hołyst, "Fast and accurate detection of spread source in large complex networks," Scientific Reports, vol. 8, no. 1, Feb. 2018, Art. no. 2508.
X. Zhang, Y. Zhang, T. Lv, and Y. Yin, "Identification of efficient observers for locating spreading source in complex networks," Physica A: Statistical Mechanics and its Applications, vol. 442, pp. 100–109, Jan. 2016.
W. Xu and H. Chen, "Scalable Rumor Source Detection under Independent Cascade Model in Online Social Networks," in 2015 11th International Conference on Mobile Ad-hoc and Sensor Networks (MSN), Shenzhen, China, Dec. 2015, pp. 236–242.
W. Zang, P. Zhang, C. Zhou, and L. Guo, "Discovering Multiple Diffusion Source Nodes in Social Networks," Procedia Computer Science, vol. 29, pp. 443–452, Jan. 2014.
W. Luo and W. P. Tay, "Finding an infection source under the SIS model," in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, Vancouver, BC, Canada, May 2013, pp. 2930–2934.
Z. Chen, K. Zhu, and L. Ying, "Detecting Multiple Information Sources in Networks under the SIR Model," IEEE Transactions on Network Science and Engineering, vol. 3, no. 1, pp. 17–31, Jan. 2016.
K. Zhu, Z. Chen, and L. Ying, "Catch’Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, Feb. 2017.
A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos, "Detecting critical nodes in sparse graphs," Computers & Operations Research, vol. 36, no. 7, pp. 2193–2200, Jul. 2009.
M. Lalou, M. A. Tahraoui, and H. Kheddouci, "Component-cardinality-constrained critical node problem in graphs," Discrete Applied Mathematics, vol. 210, pp. 150–163, Sep. 2016.
J. A. Bondy and U. S. R. Murty, Graph theory with applications. London, UK: The Macmillan Press, 1976.
M. Lalou, M. A. Tahraoui, and H. Kheddouci, "The Critical Node Detection Problem in networks: A survey," Computer Science Review, vol. 28, pp. 92–117, May 2018.
D. Lusseau and L. Conradt, "The emergence of unshared consensus decisions in bottlenose dolphins," Behavioral Ecology and Sociobiology, vol. 63, no. 7, pp. 1067–1077, May 2009.
Z. Wang, Y. Wang, J. Ma, W. Li, N. Chen, and X. Zhu, "Link prediction based on weighted synthetical influence of degree and H-index on complex networks," Physica A: Statistical Mechanics and its Applications, vol. 527, Aug. 2019, Art. no. 121184.
J. Zhu and L. Wang, "Identifying Influential Nodes in Complex Networks Based on Node Itself and Neighbor Layer Information," Symmetry, vol. 13, no. 9, Sep. 2021, Art. no. 1570.
C. Gao, J. Liu, and N. Zhong, "Network immunization and virus propagation in email networks: experimental evaluation and analysis," Knowledge and Information Systems, vol. 27, no. 2, pp. 253–279, May 2011.
Downloads
How to Cite
License
Copyright (c) 2024 Karima Mouley, Mohammed Amin Tahraoui

This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after its publication in ETASR with an acknowledgement of its initial publication in this journal.