Algorithm for link prediction in self-regulating network with adaptive topology based on graph theory and machine learning

E. Y. Pavlenko

Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 4, pp. 288-307.

Résumé

The paper presents a graph model of the functioning of a network with adaptive topology, where the network nodes represent the vertices of the graph, and data exchange between the nodes is represented as edges. The dynamic nature of network interaction complicates the solution of the task of monitoring and controlling the functioning of a network with adaptive topology, which must be performed to ensure guaranteed correct network interaction. The importance of solving such a problem is justified by the creation of modern information and cyber-physical systems, which are based on networks with adaptive topology. The dynamic nature of links between nodes, on the one hand, allows to provide self-regulation of the network, on the other hand, significantly complicates the control over the network operation due to the impossibility of identifying a single pattern of network interaction. On the basis of the developed model of network functioning with adaptive topology, a graph algorithm for link prediction is proposed, which is extended to the case of peer-to-peer networks. The algorithm is based on significant parameters of network nodes, characterizing both their physical characteristics (signal level, battery charge) and their characteristics as objects of network interaction (characteristics of centrality of graph nodes). Correctness and adequacy of the developed algorithm is confirmed by experimental results on modeling of a peer-to-peer network with adaptive topology and its self-regulation at removal of various nodes.

Détail

Keywords: modeling, networks with adaptive topology, graph model, link prediction, centrality metrics.

Bibliographie

[1] V. Student, R. Dhir, “A study of ad hoc network: A review”, International Journal of Advanced Research in Computer Science and Software Engineering, 3:3 (2013), 135–138

[2] V. Amulya, “Cyber physical systems by using wireless sensor networks”, International Journal of Science and Research, 7:4 (2018), 1380–1396

[3] V. L. Narasimhan, A. A. Arvind, K. Bever, “Greenhouse asset management using wireless sensor-actor networks”, International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, UBICOMM'07, IEEE, 2007, 9–14

[4] T. Taleb, D. Bottazzi, M. Guizani, H. Nait-Charif, “Angelah: A framework for assisting elders at home”, IEEE Journal on Selected Areas in Communications, 27:4 (2009), 480–494 | DOI

[5] P. Mohan, V. N. Padmanabhan, R. Ramjee, “Nericell: Rich monitoring of road and traffic conditions using mobile smartphones”, Proceedings of the 6th ACM conference on Embedded network sensor systems, 2008, 323–336 | DOI

[6] A. Thiagarajan et al, “Vtrack: Accurate, energy-aware road traffic delay estimation using mobile phones”, Proceedings of the 7th ACM conference on embedded networked sensor systems, 2009, 85–98 | DOI

[7] S. Mathur et al, “Parknet: Drive-by sensing of road-side parking statistics”, Proceedings of the 8th international conference on Mobile systems, applications, and services, 2010, 123–136 | DOI

[8] J. Wang, Z. Li, M. Li, Y. Liu, Z. Yang, “Sensor network navigation without locations”, IEEE Transactions on Parallel and Distributed Systems, 24:7 (2012), 1436–1446 | DOI

[9] E. Y. Pavlenko, “Functional model of adaptive network topology of large-scale systems based on dynamical graph theory”, Automatic Control and Computer Sciences, 56:8 (2022), 1016–1024 | DOI

[10] Z. Stanfield, M. Cos?kun, M. Koyuturk, “Drug response prediction as a link prediction problem”, Scientific reports, 7:1 (2017), 40–321 | DOI

[11] T. J. Lakshmi, S. D. Bhavani, “Link prediction approach to recommender systems”, Computing, 2023 | DOI

[12] M. Nickel, K. Murphy, V. Tresp, E. Gabrilovich, “A review of relational machine learning for knowledge graphs”, Proceedings of the IEEE, 104:1 (2015), 11–33 | DOI

[13] N. N. Daud, S. H. Ab Hamid, M. Saadoon, F. Sahran, N. B. Anuar, “Applications of link prediction in social networks: A review”, Journal of Network and Computer Applications, 166 (2020), 102–716 | DOI

[14] Z. Qiu, J. Wu, W. Hu, B. Du, G. Yuan, P. Yu, “Temporal link prediction with motifs for social networks”, IEEE Transactions on Knowledge and Data Engineering, 35:3 (2023), 3145–3158

[15] H. Nassar, A. R. Benson, D. F. Gleich, “Neighborhood and pagerank methods for pairwise link prediction”, Social Network Analysis and Mining, 10:1 (2020), 63 | DOI

[16] X.-H. Yang, X. Yang, F. Ling, H. F. Zhang, D. Zhang, J. Xiao, “Link prediction based on local major path degree”, Modern Physics Letters B, 32:29 (2018), 1850348 | DOI | MR

[17] S. Kumar, A. Mallik, B. Panda, “Link prediction in complex networks using node centrality and light gradient boosting machine”, World Wide Web, 25:6 (2022), 2487–2513 | DOI | MR

[18] J. Cheriyan, G. Sajeev, “m-PageRank: A novel centrality measure for multilayer networks”, Advances in Complex Systems, 23:5 (2020), 2050012 | DOI | MR

[19] F. Feng, X. Liu, B. Yong, R. Zhou, Q. Zhou, “Anomaly detection in ad-hoc networks based on deep learning model: A plug and play device”, Ad Hoc Networks, 84 (2019), 82–89 | DOI

[20] R. Meddeb, F. Jemili, B. Triki, O. Korbaa, “Anomaly-based behavioral detection in mobile ad-hoc networks”, Procedia Computer Science, 159 (2019), 77–86 | DOI

[21] M. Zhang, Y. Chen, “Link prediction based on graph neural networks”, NeurIPS 2018, Advances in Neural Information Processing Systems, 31, 2018, 5165–5175

[22] B. P. Chamberlain et al, Graph neural networks for link prediction with subgraph sketching, 2023, arXiv: 2209.15486 [cs.LG]

[23] M. Niu, L. Liu, J. Shu, “Link quality prediction for wireless networks: Current status and future directions”, Proceedings of the 2023 8th International Conference on Intelligent Information Technology, 2023, 52–56

[24] J. Chen, Y. Han, D. Li, J. Nie, “Link prediction and route selection based on channel state detection in UASNs”, International Journal of Distributed Sensor Networks, 7:1 (2011), 939–864 | DOI

[25] H. Shao, L. Wang, H. Liu, R. Zhu, “A link prediction method for MANETs based on fast spatio-temporal feature extraction and LSGANs”, Scientific Reports, 12:1 (2022), 16–896 | DOI | MR

[26] F. Harary, G. Gupta, “Dynamic graph models”, Mathematical and Computer Modelling, 25:7 (1997), 79–87 | DOI | MR | Zbl

[27] L. K. Ketshabetswe, A. M. Zungeru, M. Mangwala, J. M. Chuma, B. Sigweni, “Communication protocols for wireless sensor networks: A survey and comparison”, Heliyon, 5:5 (2019), E01591 | DOI

[28] D. Kandris, C. Nakas, D. Vomvas, G. Koulouras, “Applications of wireless sensor networks: An up-to-date survey”, Applied system innovation, 3:1 (2020), 14 | DOI

[29] M. Kim, S. Park, W. Lee, “Energy and distance-aware hopping sensor relocation for wireless sensor networks”, Sensors, 19:7 (2019), 1567 | DOI