Locating the source of diffusion in the early stage utilizing network monitors and graph convolutional networks

Abstract

Locating the source of diffusion in complex networks is a critical and challenging problem, exemplified by tasks such as identifying the origin of power grid faults or detecting the source of computer viruses. The accuracy of source localization in most existing methods is highly dependent on the number of infected nodes. When there are few infected nodes in the network, the accuracy is relatively limited. This poses a major challenge in identifying the source in the early stages of diffusion. This article presents a novel deep learning-based model for source localization under limited information conditions, denoted as GCN-MSL (Graph Convolutional Networks and network Monitor-based Source Localization model). The GCN-MSL model is less affected by the number of infected nodes and enables the efficient identification of the diffusion source in the early stages. First, pre-deployed monitor nodes, controlled by the network administrator, continuously report real-time data, including node states and the arrival time of anomalous signals. These data, along with the network topology, are used to construct node features. Graph convolutional networks are employed to aggregate information from multiple-order neighbors, thereby forming comprehensive node representations. Subsequently, the model is trained with the true source labeled as the target, allowing it to distinguish the source node from other nodes within the network. Once trained, the model can be applied to locate hidden sources in other diffusion networks. Experimental results across multiple data sets demonstrate the superiority of the GCN-MSL model, especially in the early stages of diffusion, where it significantly enhances both the accuracy and efficiency of source localization. Additionally, the GCN-MSL model exhibits strong robustness and adaptability to variations in external parameters of monitor nodes. The proposed method holds significant value in the timely detection of anomalous signals within complex networks and preventing the spread of harmful information.

Graphical abstract

Keywords

source localization / graph convolutional network / network monitor / information diffusion

References

[1] Bai L, Cui L X, Jiao Y H, Rossi L, Hancock E R, (2022). Learning backtrackless aligned-spatial graph convolutional networks for graph classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44( 2): 783–798

[2] Cai K C, Xie H, Lui J C S, (2018). Information spreading forensics via sequential dependent snapshots. IEEE/ACM Transactions on Networking, 26( 1): 478–491

[3] Cheng L, Zhu P C, Gao C, Wang Z, Li X L, (2024). A heuristic framework for sources detection in social networks via graph convolutional networks. IEEE Transactions on Systems, Man, and Cybernetics. Systems, 54( 11): 7002–7014

[4] DongMZhengB LHungN Q VSuHLiG H (2019). Multiple rumor source detection with graph convolutional networks. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. New York: Association for Computing Machinery, 569–578

[5] Dong M, Zheng B L, Li G H, Li C L, Zheng K, Zhou X F, (2022). Wavefront-based multiple rumor sources identification by multi-task learning. IEEE Transactions on Emerging Topics in Computational Intelligence, 6( 5): 1068–1078

[6] Gong C, Li J C, Qian L W, Li S W, Yang Z W, Yang K W, (2024). HMSL: Source localization based on higher-order Markov propagation. Chaos, Solitons, and Fractals, 182: 114765

[7] GuoQZhangCZhangH SFuL Y (2021). IGCN: Infected graph convolutional network based source identification. In: Proceedings of 2021 IEEE Global Communications Conference. Piscataway: IEEE Press, 1–6

[8] Guo Z G, Zhang Y F, Liu S C, Wang X V, Wang L H, (2023). Exploring self-organization and self-adaption for smart manufacturing complex networks. Frontiers of Engineering Management, 10( 2): 206–222

[9] Hou D P, Gao C, Wang Z, Li X Y, Li X L, (2024). Random full-order-coverage based rapid source localization with limited observations for large-scale networks. IEEE Transactions on Network Science and Engineering, 11( 5): 4213–4226

[10] Jiang Y N, Wang R R, Sun J S, Wang Y S, You H F, Zhang Y, (2024a). Rumor localization, detection and prediction in social network. IEEE Transactions on Computational Social Systems, 11( 3): 3168–3178

[11] Jiang Z X, Hu Z L, Huang F L, (2024b). Source localization in signed networks based on dynamic message passing algorithm. Chaos, Solitons, and Fractals, 188: 115532

[12] Jin R C, Huang Y F, Zhang Z Y, Dai H Y, (2023). On the privacy guarantees of gossip protocols in general networks. IEEE Transactions on Network Science and Engineering, 10( 6): 3114–3130

[13] KingmaD PBaJ (2015). ADAM: A method for stochastic optimization. In: Proceedings of the 3rd International Conference for Learning Representations. OpenReview

[14] KipfT NWellingM (2017). Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations. Available at OpenReview.net

[15] Li Y F, Jia C Z, (2021). An overview of the reliability metrics for power grids and telecommunication networks. Frontiers of Engineering Management, 8( 4): 531–544

[16] LingCJiangJ JWangJ XLiangZ (2022). Source localization of graph diffusion via variational autoencoders for graph inverse problems. In: Proceedings of 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: Association for Computing Machinery, 1010–1020

[17] Meel P, Vishwakarma D K, (2020). Fake news, rumor, information pollution in social media and web: A contemporary survey of state of-the-arts, challenges and opportunities. Expert Systems with Applications, 153: 112986

[18] MichaëlDXavierBPierreV (2016). Convolutional neural networks on graphs with fast localized spectral filtering. In: Proceedings of the 30th International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc, 3844–3852

[19] Ou Y, Guo Q, Liu J, (2022). Identifying spreading influence nodes for social networks. Frontiers of Engineering Management, 9( 4): 520–549

[20] Paluch R, Gajewski Ł G, Hołyst J A, Szymanski B K, (2020). Optimizing sensors placement in complex networks for localization of hidden signal source: A review. Future Generation Computer Systems, 112: 1070–1092

[21] Paluch R, Lu X Y, Suchecki K, Szymański B K, Hołyst J A, (2018). Fast and accurate detection of spread source in large complex networks. Scientific Reports, 8( 1): 2508

[22] Pan C Y, Wang J, Yan D, Zhang C S, Zhang X Z, (2024). A fast algorithm for diffusion source localization in large-scale complex networks. Journal of Complex Networks, 12( 2): cnae014

[23] Peng S T, Shu X C, Ruan Z Y, Huang Z G, Xuan Q, (2022). Classifying multiclass relationships between ASes using graph convolutional network. Frontiers of Engineering Management, 9( 4): 653–667

[24] Pinto P C, Thiran P, Vetterli M, (2012). Locating the source of diffusion in large-scale networks. Physical Review Letters, 109( 6): 068702

[25] Shah D, Zaman T, (2011). Rumors in a network: Who’s the culprit. IEEE Transactions on Information Theory, 57( 8): 5163–5181

[26] Shelke S, Attar V, (2019). Source detection of rumor in social network – A review. Online Social Networks and Media, 9: 30–42

[27] Shen Z S, Cao S N, Wang W X, Di Z R, Stanley H E, (2016). Locating the source of diffusion in complex networks by time-reversal backward spreading. Physical Review. E, 93( 3): 032301

[28] Tang W, Yang H, Pi J X, (2024). Dynamics and control strategies for SLBRS model of computer viruses based on complex networks. International Journal of Intelligent Systems, 2024( 1): 1–16

[29] Wang H J, Sun K J, (2020). Locating source of heterogeneous propagation model by universal algorithm. Europhysics Letters, 131( 4): 48001

[30] WangJ XJiangJ JZhaoL. (2022) An invertible graph diffusion neural network for source localization. In: Proceedings of 31st ACM World Wide Web Conference. New York: Association for Computing Machinery, 1058–1069

[31] WangZHouDGaoCLiXLiX (2023). Lightweight source localization for large-scale social networks. In: Proceedings of WWW′23: The ACM Web Conference 2023. New York: Association for Computing Machinery, 286–294

[32] WangZWangC KPeiJ SYeX J (2017). Multiple source detection without knowing the underlying propagation model. In: Proceedings of Thirty-First AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 217–223

[33] WilliamL HRexYJureL (2017). Inductive representation learning on large graphs. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. Red Hook: Curran Associates Inc, 1025–1035

[34] Wu Z, Pan S, Chen F, Long G, Zhang C, Yu P S, (2021). A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32( 1): 4–24

[35] Xu X, Qian T, Xiao Z, Zhang N, Wu J, Zhou F, (2024). PGSL: A probabilistic graph diffusion model for source localization. Expert Systems with Applications, 238: 122028

[36] Yang F, Yang S H, Peng Y, Yao Y B, Wang Z W, Li H J, Liu J X, Zhang R S, Li C G, (2020). Locating the propagation source in complex networks with a direction-induced search based Gaussian estimator. Knowledge-Based Systems, 195: 105674

[37] Zhao J, Cheong K H, (2023). Early identification of diffusion source in complex networks with evidence theory. Information Sciences, 642: 119061

[38] Zhou J, Cui G Q, Zhang Z Y, Yang C, Liu Z Y, Sun M S, (2019). Graph neural networks: A Review of methods and applications. Statistics, 2019: 2

[39] Zhou J Y, Jiang Y W, Huang B Q, (2021). Source identification of infectious diseases in networks via label ranking. PLoS One, 16( 1): e0245344

[40] Zhu K, Ying L, (2016). Information source detection in the SIR model: a sample-path-based approach. IEEE/ACM Transactions on Networking, 24( 1): 408–421

RIGHTS & PERMISSIONS

Higher Education Press