Locating the Source of Information in Social Networks using Critical Nodes

Authors

  • Karima Mouley LME Laboratory, Faculty of Technology, Hassiba Benbouali University, Chlef, Algeria | Department of Informatics, Faculty of Exact Sciences and Informatics, Ηassiba Benbouali University, Chlef, Algeria
  • Mohammed Amin Tahraoui LIA Laboratory, Department of Informatics, Faculty of Exact Sciences and Informatics, Hassiba Benbouali University, Chlef, Algeria
Volume: 15 | Issue: 1 | Pages: 19136-19142 | February 2025 | https://doi.org/10.48084/etasr.9283

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 networks

Downloads

Download data is not yet available.

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

[1]
Mouley, K. and Tahraoui, M.A. 2025. Locating the Source of Information in Social Networks using Critical Nodes. Engineering, Technology & Applied Science Research. 15, 1 (Feb. 2025), 19136–19142. DOI:https://doi.org/10.48084/etasr.9283.

Metrics

Abstract Views: 64
PDF Downloads: 38

Metrics Information

Most read articles by the same author(s)