Comparative Analysis of Centrality Measures of Network Nodes based on Principal Component Analysis

Cover Page

Cite item

Full Text

Abstract

. The analysis of networks of a diverse nature, which are citation networks, social networks or information and communication networks, includes the study of topological properties that allow one to assess the relationships between network nodes and evaluate various characteristics, such as the density and diameter of the network, related subgroups of nodes, etc. For this, the network is represented as a graph – a set of vertices and edges between them. One of the most important tasks of network analysis is to estimate the significance of a node (or in terms of graph theory – a vertex). For this, various measures of centrality have been developed, which make it possible to assess the degree of significance of the nodes of the network graph in the structure of the network under consideration.
The existing variety of measures of centrality gives rise to the problem of choosing the one that most fully describes the significance and centrality of the node.
The relevance of the work is due to the need to analyze the centrality measures to determine the significance of vertices, which is one of the main tasks of studying networks (graphs) in practical applications.
The study made it possible, using the principal component method, to identify collinear measures of centrality, which can be further excluded both to reduce the computational complexity of calculations, which is especially important for networks that include a large number of nodes, and to increase the reliability of the interpretation of the results obtained when evaluating the significance node within the analyzed network in solving practical problems.
In the course of the study, the patterns of representation of various measures of centrality in the space of principal components were revealed, which allow them to be classified in terms of the proximity of the images of network nodes formed in the space determined by the measures of centrality used.

About the authors

I. Yu Eremeev

Mozhaisky Military Space Academy

Email: eremeeviu@yandex.ru
Zdanovskaya str. 13

M. V Tatarka

Mozhaisky Military Space Academy

Email: maksimtbv@gmail.com
Zdanovskaya str. 13

F. L Shuvaev

Mozhaisky Military Space Academy

Email: cadetfed@mail.ru
Zdanovskaya str. 13

A. S Tsyganov

Mozhaisky Military Space Academy

Email: porudchik@mail.ru
Zdanovskaya str. 13

References

  1. Bonchi F., De Francisci G., Riondato M. Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms // Proceedings of the 25th International Conference Companion on World Wide Web. 2016. pp. 1017–1020.
  2. Щербакова Н.Г. Меры центральности в сетях // Проблемы информатики. 2015. № 1. С. 18–30.
  3. Бередихин С.В., Ляпунов В.М., Щербакова Н.Г. Мера важности научной перио-дики – «Центральность по посредничеству» // Проблемы информатики. 2014. № 3. С. 53–63.
  4. Юдина М.Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омский научный вестник. 2016. № 4. С. 161–165.
  5. Brandes U., Borgatti S., Freeman L. Maintaining the duality of closeness and be-tweenness centrality // Social Networks. 2016. vol. 44. pp. 153–159.
  6. Minoo A. et al. A Systematic Survey of Centrality Measures for Protein-Protein Inter-action Networks // BMC Systems Biology. 2018. vol. 12. no. 1. pp. 80.
  7. Chen P-Y., Choudhury S., Hero A., Multi-centrality graph spectral decompositions and their application to cyber intrusion detection // IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2016. pp. 4553–4557.
  8. Lu B., Sun H., Harris P., Xu M. Shp2graph: Tools to Convert a Spatial Network into an Igraph Graph in R // ISPRS Int. J. Geo-Inf. 2018. vol. 7. pp. 293.
  9. Csardi G, Nepusz T. The IGRAPH software package for complex network research // InterJournal, Complex Systems. 1695. 2006. vol. 1695. no. 5. pp. 1–9.
  10. Шуваев Ф.Л., Татарка М.В. Анализ динамики мер центральности математиче-ских моделей случайных графов // Научно-технический вестник информацион-ных технологий, механики и оптики. 2020. Т. 20. № 2. С. 249–256.
  11. Шуваев Ф.Л., Татарка М.В. Анализ математических моделей случайных гра-фов, применяемых в имитационном моделировании информационно-коммуникационных сетей // Вестник Санкт-Петербургского университета ГПС МЧС России. 2020. № 2. С. 67–77.
  12. Van Mieghem P., Ge X., Schumm P., Trajanovski S., Wang H. Spectral graph analysis of modularity and assortativity // Phys. Rev. 2010. vol. 82. no. 5. P. 056113.
  13. Barzel B., Biham O. Quantifying the connectivity of a network: the network correla-tion function method // Phys. Rev. 2009. vol. 80. pp. 046104.
  14. Barabasi A. Network Science // Cambridge university press. 2016. 453 p.
  15. Watts D., Strogatz H. Collective dynamics of «Small-world» networks // Nature. 1998. vol. 393. pp. 440–442.
  16. Hartmann A., Mézard M. Distribution of diameters for Erdős-Rényi random graphs // Phys. Rev. 2018. vol. 97. no. 3. pp. 032128.
  17. Le C., Levina E., Vershynin R. Concentration and regularization of random graphs // Random Structures&Algorithms. 2017. vol. 51. no. 3. pp. 538–561.
  18. Gibson H., Vickers P. Using adjacency matrices to lay out larger small-world net-works // Applied soft computing. 2016. vol. 42. pp. 80–92.
  19. Jalili M. et al. CentiServer: A Comprehensive Resource, Web-Based Application and R Package for Centrality Analysis // PLoS ONE. 2015. vol. 10. no. 11. pp. 0143111.
  20. Oldham, S. et al. Consistency and differences between centrality measures across distinct classes of networks // PLoS ONE. 2019. vol. 14. no. 7. pp. 0220061.
  21. Bloch F., Jackson M., Tebaldi P. Centrality measures in networks // SSRN. 2016. 42 p.
  22. Lê S., Josse J., Husson F. FactoMineR: A Package for Multivariate Analysis // Journal of Statistical Software. 2008. vol. 25. no. 1. pp. 1–18.
  23. Depaolini M., Ciucci D., Calegari S., Dominoni M. External Indices for Rough Clus-tering // Lecture Notes in Computer Science. 2018. vol. 11103. pp. 378–391.
  24. White S., Smyth P. Algorithms for estimating relative importance in networks // Pro-ceedings of the ninth ACM SIGKDD international conference on Knowledge discov-ery and data mining. 2003. pp. 266–275.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».