Використання понять теорії графів для аналізу складних мереж

ВИКОРИСТАННЯ ПОНЯТЬ ТЕОРІЇ ГРАФІВ ДЛЯ АНАЛІЗУ СКЛАДНИХ МЕРЕЖ

THE USAGE OF GRAPH THEORY CONCEPTS FOR THE COMPLEX NETWORKS ANALYSIS

 Сторінки: 59-63. Номер: №1, 2022 (305) 
 Автори:
МІХАЛЕВСЬКА Г. І.
https://orcid.org/0000-0001-8576-7734
e-mail: gmihalevska@gmail.com
МІХАЛЕВCЬКИЙ В. Ц.
https://orcid.org/0000-0002-8197-8005
e-mail: cezar_mv@ukr.net
Хмельницький національний університет
Galina MIKHALEVSKA, Vitalii MIKHALEVSKYI
Khmelnytskyi National University
DOI: https://www.doi.org/10.31891/2307-5732-2022-305-1-59-63

Анотація мовою оригіналу

В статті розглянуто і досліджується використання понять теорії графів для аналізу складних мереж. Абстрактно від їх фізичної природи розглядаються топологічні властивості цих мереж, які істотно визначають функціонування мереж і становлять предмет дослідження комплексних мереж.
Розглянуто один з напрямків аналізу складних мереж – їх візуалізацію, яка дозволяє отримати важливу інформацію про структуру і властивості мережі без точних розрахунків. Описано основні інструменти візуалізації, у переважній більшості, вільно поширювані, безкоштовні програми.
Ключові слова: складні мережі, топологія, візуалізація мережі, граф, Graph Online, Gephi.

Розширена анотація англійською  мовою

The article considers and investigates the usage of graph theory concepts for the complex networks analysis. Abstract from their physical nature, the topological properties of these networks are considered, which significantly determine the functioning of networks and are the subject of study of complex networks. Each node of the network can be connected with other nodes by a certain number of connections that may have a direction, or nodes can be connected with each other by symmetrical connections. Also in modern systems of analysis and visualization of networks such concepts as degrees of vertices, ranking, clustering, modularity, algorithms of laying of graphs, etc. are widely used.
To calculate the parameters of the network as a whole use the number of nodes, the number of edges, the geodetic distance between nodes, the average distance from one node to another, density – the ratio of the number of edges in the network to the maximum possible number of edges for a given number of nodes; number of triads, diameter of the network (maximum geodetic distance). Structural network analysis includes: click detection (subgroups that are more interconnected than other click nodes); identification of network components; finding bridges (nodes, the removal of which breaks the network into incoherent parts); groups of equivalent nodes (which have the most similar communication profiles). One of the areas of complex networks analysis is their visualization, which allows to obtain important information about the structure and properties of the network without accurate calculations. Software tools for the complex networks analysis support the calculation of all the described parameters of the nodes, the network as a whole, provide its structural analysis and visualization, work with different data formats.
For the complex networks analysis, the main visualization tools are described, in the vast majority, freely distributed, free programs.
Keywords: complex networks, topology, network visualization, graph, Graph Online, Gephi.

Література

1. Albert-Laszlo Barabasi. Network Science. Cambridge University Press, 2016.
2. Аналіз соціальних мереж [Eлектронний ресурс]. – Режим доступу : http://www.lib.mdpu.org.ua/e-book/analiz_soc/official/index.htm
3. Зубок В.Ю. Огляд використання математичних параметрів складної мережі для аналізу топології Інтернет / В.Ю. Зубок, О.Т. Дармохвал // Збірник наукових праць Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України. – К. : ІПМЕ ім. Г.Є. Пухова НАН України, 2010. – Вип. 55. – С. 19–29.
4. Ланде Д.В. Візуалізація та аналіз мережевих структур : навчальний посібник / Д.В. Ланде, І.Ю. Субач; ІСЗЗІ КПІ ім. Ігоря Сікорського. – К. : КПІ ім. Ігоря Сікорського, Вид-во «Політехніка», 2021. – 80 с.
5. Ланде Д.В. Основи теорії і практики інтелектуального аналізу даних у сфері кібербезпеки: навчальний посібник / Ланде Д.В., Субач І.Ю., Бояринова Ю.Є. – К. : ІСЗЗІ КПІ ім. Ігоря Сікрорського, 2018. – 300 с.
6. Манодж Б. С. Складні мережі: перспектива мереж та обробки сигналів / Манодж Б. С., Абхішек Чакраборті та Рахул Сінгх. – Пірсон, Нью-Йорк, США, 2018.
7. Снарский А.А. Моделирование сложных сетей : учебное пособие / Снарский А.А., Ландэ Д.В. – К. : Инжиниринг, 2015. – 212 с.

References

1. Albert-Laszlo Barabasi. Network Science. – Cambridge University Press, 2016.
2. Analysis of social networks [Electronic resource]. – Access mode: http://www.lib.mdpu.org.ua/e-book/analiz_soc/official/index.htm
3. Zubok V.Y. Review of the use of mathematical parameters of a complex network for the analysis of the Internet topology / V.Y. Zubok, О.Т. Darmohval // Collection of scientific works of the Institute of Modeling Problems in Energy named after G.Y. Pukhov National Academy of Sciences of Ukraine. – K .: IPME them. G.Y. Pukhov National Academy of Sciences of Ukraine, 2010. – Issue. 55. – P. 19-29.
4. Lande D.V. Visualization and analysis of network structures: a textbook / D.V. Lande, I.Y. Subach; ISZZI KPI them. Igor Sikorsky. – K .: KPI them. Igor Sikorsky, Polytechnic Publishing House, 2021. – 80 p.
5. Lande D.V., Subach I.Y., Boyarinova Y.E. Fundamentals of the theory and practice of data mining in the field of cybersecurity: a textbook. – K .: ISZZI KPI them. Igor Sikorsky, 2018. – 300 p.
6. Manodzh B.S., Abhishek Chakraborty and Rahul Singh. Complex Networks: The Perspective of Networking and Signal Processing, Pearson, New York, USA, 2018.
7. Snarsky A.A., Lande D.V. Modeling of complex networks: a textbook. – К .: Ingeneering, 2015. – 212 p.