maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-4-288-307BQTEIRmais-1822Research ArticleDiscrete Mathematics in Relation to Computer ScienceАлгоритм предсказания связей в саморегулирующейся сети с адаптивной топологией на базе теории графов и машинного обученияAlgorithm for link prediction in self-regulating network with adaptive topology based on graph theory and machine learninghttps://orcid.org/0000-0003-1345-1874ПавленкоЕвгений ЮрьевичPavlenkoEvgeny Y.pavlenko@ibks.spbstu.ruСанкт-Петербургский политехнический университет Петра ВеликогоРоссияPeter the Great St. Petersburg Polytechnic UniversityRussian Federation202311122023304288307Copyright © Павленко Е.Ю., 20232023Павленко Е.Ю.Pavlenko E.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1822

В статье представлена графовая модель функционирования сети с адаптивной топологией, где узлы сети представляют собой вершины графа, а обмен данными между узлами представлен в виде ребер. Динамический характер сетевого взаимодействия осложняет решение задачи мониторинга и контроля функционирования сети с адаптивной топологией, которую необходимо выполнять для обеспечения гарантированно корректного сетевого взаимодействия. Значимость решения такой задачи обосновывается созданием современных информационных и киберфизических систем, в основе которых лежат сети с адаптивной топологией. Динамический характер связей между узлами, с одной стороны, позволяет обеспечивать саморегуляцию сети, с другой стороны, существенно осложняет контроль за работой сети в связи с невозможностью выделения единого шаблона сетевого взаимодействия. На базе разработанной модели функционирования сети с адаптивной топологией предложен графовый алгоритм предсказания связей, распространенный на случай с одноранговыми сетями. В основу алгоритма положены значимые параметры узлов сети, харатеризующие как их физические характеристики (уровень сигнала, заряд батареи), так и их характеристики как объектов сетевого взаимодействия (характеристики центральности вершин графа). Корректность и адекватность разработанного алгоритма подтверждена экспериментальными результатами по моделированию одноранговой сети с адаптивной топологией и ее саморегуляции при удалении различных узлов.

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.

моделированиесети с адаптивной топологиейграфовая модельпредсказание связейметрики центральностиmodelingnetworks with adaptive topologygraph modellink predictioncentrality metricsИсследование выполнено за счет гранта Российского научного фонда № 22-21-20008. Исследование выполнено за счет гранта Санкт-Петербургского научного фонда в соответствии с соглашением от 15 апреля 2022 г. №61/220.The research is funded by the Russian Science Foundation, project no. 22-21-20008. The research is funded by the grant of the St. Petersburg Science Foundation in accordance with the agreement of April 15, 2022 № 61/220.ReferencesV. Student and R. Dhir, “A study of ad hoc network: A review,” International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 3, pp. 135–138, 2013.V. Student and R. Dhir, “A study of ad hoc network: A review,” International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 3, pp. 135–138, 2013.V. Amulya, “Cyber Physical Systems by Using Wireless Sensor Networks,” International Journal of Science and Research, vol. 7, no. 4, pp. 1380–1396, 2018.V. Amulya, “Cyber Physical Systems by Using Wireless Sensor Networks,” International Journal of Science and Research, vol. 7, no. 4, pp. 1380–1396, 2018.V. L. Narasimhan, A. A. Arvind, and K. Bever, “Greenhouse asset management using wireless sensor-actor networks,” in International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM'07), 2007, pp. 9–14.V. L. Narasimhan, A. A. Arvind, and K. Bever, “Greenhouse asset management using wireless sensor-actor networks,” in International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM'07), 2007, pp. 9–14.T. Taleb, D. Bottazzi, M. Guizani, and H. Nait-Charif, “Angelah: a framework for assisting elders at home,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 4, pp. 480–494, 2009.T. Taleb, D. Bottazzi, M. Guizani, and H. Nait-Charif, “Angelah: a framework for assisting elders at home,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 4, pp. 480–494, 2009.P. Mohan, V. N. Padmanabhan, and R. Ramjee, “Nericell: rich monitoring of road and traffic conditions using mobile smartphones,” in Proceedings of the 6th ACM conference on Embedded network sensor systems, 2008, pp. 323–336.P. Mohan, V. N. Padmanabhan, and R. Ramjee, “Nericell: rich monitoring of road and traffic conditions using mobile smartphones,” in Proceedings of the 6th ACM conference on Embedded network sensor systems, 2008, pp. 323–336.A. Thiagarajan et al., “Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones,” in Proceedings of the 7th ACM conference on embedded networked sensor systems, 2009, pp. 85–98.A. Thiagarajan et al., “Vtrack: accurate, energy-aware road traffic delay estimation using mobile phones,” in Proceedings of the 7th ACM conference on embedded networked sensor systems, 2009, pp. 85–98.S. Mathur et al., “Parknet: drive-by sensing of road-side parking statistics,” in Proceedings of the 8th international conference on Mobile systems, applications, and services, 2010, pp. 123–136.S. Mathur et al., “Parknet: drive-by sensing of road-side parking statistics,” in Proceedings of the 8th international conference on Mobile systems, applications, and services, 2010, pp. 123–136.J. Wang, Z. Li, M. Li, Y. Liu, and Z. Yang, “Sensor network navigation without locations,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 7, pp. 1436–1446, 2012.J. Wang, Z. Li, M. Li, Y. Liu, and Z. Yang, “Sensor network navigation without locations,” IEEE Transactions on Parallel and Distributed Systems, vol. 24, no. 7, pp. 1436–1446, 2012.E. Y. Pavlenko, “Functional Model of Adaptive Network Topology of Large-Scale Systems Based on Dynamical Graph Theory,” Automatic Control and Computer Sciences, vol. 56, no. 8, pp. 1016–1024, 2022.E. Y. Pavlenko, “Functional Model of Adaptive Network Topology of Large-Scale Systems Based on Dynamical Graph Theory,” Automatic Control and Computer Sciences, vol. 56, no. 8, pp. 1016–1024, 2022.Z. Stanfield, M. Coşkun, and M. Koyutürk, “Drug response prediction as a link prediction problem,” Scientific reports, vol. 7, no. 1, p. 40321, 2017.Z. Stanfield, M. Coşkun, and M. Koyutürk, “Drug response prediction as a link prediction problem,” Scientific reports, vol. 7, no. 1, p. 40321, 2017.T. J. Lakshmi and S. D. Bhavani, “Link prediction approach to recommender systems,” Computing, 2023, doi: 10.1007/s00607-023-01227-0.T. J. Lakshmi and S. D. Bhavani, “Link prediction approach to recommender systems,” Computing, 2023, doi: 10.1007/s00607-023-01227-0.M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich, “A review of relational machine learning for knowledge graphs,” Proceedings of the IEEE, vol. 104, no. 1, pp. 11–33, 2015.M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich, “A review of relational machine learning for knowledge graphs,” Proceedings of the IEEE, vol. 104, no. 1, pp. 11–33, 2015.N. N. Daud, S. H. Ab Hamid, M. Saadoon, F. Sahran, and N. B. Anuar, “Applications of link prediction in social networks: A review,” Journal of Network and Computer Applications, vol. 166, p. 102716, 2020.N. N. Daud, S. H. Ab Hamid, M. Saadoon, F. Sahran, and N. B. Anuar, “Applications of link prediction in social networks: A review,” Journal of Network and Computer Applications, vol. 166, p. 102716, 2020.Z. Qiu, J. Wu, W. Hu, B. Du, G. Yuan, and P. Yu, “Temporal link prediction with motifs for social networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 3, pp. 3145–3158, 2023.Z. Qiu, J. Wu, W. Hu, B. Du, G. Yuan, and P. Yu, “Temporal link prediction with motifs for social networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 35, no. 3, pp. 3145–3158, 2023.H. Nassar, A. R. Benson, and D. F. Gleich, “Neighborhood and PageRank methods for pairwise link prediction,” Social Network Analysis and Mining, vol. 10, no. 1, p. 63, 2020.H. Nassar, A. R. Benson, and D. F. Gleich, “Neighborhood and PageRank methods for pairwise link prediction,” Social Network Analysis and Mining, vol. 10, no. 1, p. 63, 2020.X.-H. Yang, X. Yang, F. Ling, H.-F. Zhang, D. Zhang, and J. Xiao, “Link prediction based on local major path degree,” Modern Physics Letters B, vol. 32, no. 29, pp. 1850348–306, 2018.X.-H. Yang, X. Yang, F. Ling, H.-F. Zhang, D. Zhang, and J. Xiao, “Link prediction based on local major path degree,” Modern Physics Letters B, vol. 32, no. 29, pp. 1850348–306, 2018.S. Kumar, A. Mallik, and B. S. Panda, “Link prediction in complex networks using node centrality and light gradient boosting machine,” World Wide Web, vol. 25, no. 6, pp. 2487–2513, 2022.S. Kumar, A. Mallik, and B. S. Panda, “Link prediction in complex networks using node centrality and light gradient boosting machine,” World Wide Web, vol. 25, no. 6, pp. 2487–2513, 2022.J. Cheriyan and G. P. Sajeev, “m-PageRank: A novel centrality measure for multilayer networks,” Advances in Complex Systems, vol. 23, no. 5, p. 2050012, 2020.J. Cheriyan and G. P. Sajeev, “m-PageRank: A novel centrality measure for multilayer networks,” Advances in Complex Systems, vol. 23, no. 5, p. 2050012, 2020.F. Feng, X. Liu, B. Yong, R. Zhou, and Q. Zhou, “Anomaly detection in ad-hoc networks based on deep learning model: A plug and play device,” Ad Hoc Networks, vol. 84, pp. 82–89, 2019.F. Feng, X. Liu, B. Yong, R. Zhou, and Q. Zhou, “Anomaly detection in ad-hoc networks based on deep learning model: A plug and play device,” Ad Hoc Networks, vol. 84, pp. 82–89, 2019.R. Meddeb, F. Jemili, B. Triki, and O. Korbaa, “Anomaly-based behavioral detection in mobile Ad-Hoc networks,” Procedia Computer Science, vol. 159, pp. 77–86, 2019.R. Meddeb, F. Jemili, B. Triki, and O. Korbaa, “Anomaly-based behavioral detection in mobile Ad-Hoc networks,” Procedia Computer Science, vol. 159, pp. 77–86, 2019.M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” in Advances in Neural Information Processing Systems 31 (NeurIPS 2018), 2018, pp. 5165–5175.M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” in Advances in Neural Information Processing Systems 31 (NeurIPS 2018), 2018, pp. 5165–5175.B. P. Chamberlain et al., “Graph Neural Networks for Link Prediction with Subgraph Sketching.” 2023.B. P. Chamberlain et al., “Graph Neural Networks for Link Prediction with Subgraph Sketching.” 2023.M. Niu, L. Liu, and J. Shu, “Link Quality Prediction for Wireless Networks: Current Status and Future Directions,” in Proceedings of the 2023 8th International Conference on Intelligent Information Technology, 2023, pp. 52–56.M. Niu, L. Liu, and J. Shu, “Link Quality Prediction for Wireless Networks: Current Status and Future Directions,” in Proceedings of the 2023 8th International Conference on Intelligent Information Technology, 2023, pp. 52–56.J. Chen, Y. Han, D. Li, and J. Nie, “Link prediction and route selection based on channel state detection in UASNs,” International Journal of Distributed Sensor Networks, vol. 7, no. 1, p. 939864, 2011.J. Chen, Y. Han, D. Li, and J. Nie, “Link prediction and route selection based on channel state detection in UASNs,” International Journal of Distributed Sensor Networks, vol. 7, no. 1, p. 939864, 2011.H. Shao, L. Wang, H. Liu, and R. Zhu, “A link prediction method for MANETs based on fast spatio-temporal feature extraction and LSGANs,” Scientific Reports, vol. 12, no. 1, p. 16896, 2022.H. Shao, L. Wang, H. Liu, and R. Zhu, “A link prediction method for MANETs based on fast spatio-temporal feature extraction and LSGANs,” Scientific Reports, vol. 12, no. 1, p. 16896, 2022.F. Harary and G. Gupta, “Dynamic graph models,” Mathematical and Computer Modelling, vol. 25, no. 7, pp. 79–87, 1997.F. Harary and G. Gupta, “Dynamic graph models,” Mathematical and Computer Modelling, vol. 25, no. 7, pp. 79–87, 1997.L. K. Ketshabetswe, A. M. Zungeru, M. Mangwala, J. M. Chuma, and B. Sigweni, “Communication protocols for wireless sensor networks: A survey and comparison,” Heliyon, vol. 5, no. 5, p. E01591, 2019.L. K. Ketshabetswe, A. M. Zungeru, M. Mangwala, J. M. Chuma, and B. Sigweni, “Communication protocols for wireless sensor networks: A survey and comparison,” Heliyon, vol. 5, no. 5, p. E01591, 2019.D. Kandris, C. Nakas, D. Vomvas, and G. Koulouras, “Applications of wireless sensor networks: an up-to-date survey,” Applied system innovation, vol. 3, no. 1, p. 14, 2020.D. Kandris, C. Nakas, D. Vomvas, and G. Koulouras, “Applications of wireless sensor networks: an up-to-date survey,” Applied system innovation, vol. 3, no. 1, p. 14, 2020.M. Kim, S. Park, and W. Lee, “Energy and distance-aware hopping sensor relocation for wireless sensor networks,” Sensors, vol. 19, no. 7, p. 1567, 2019.M. Kim, S. Park, and W. Lee, “Energy and distance-aware hopping sensor relocation for wireless sensor networks,” Sensors, vol. 19, no. 7, p. 1567, 2019.

The authors declare that there are no conflicts of interest present.