Анализ мер центральности узлов сетей на основе метода главных компонент
Ключевые слова:
метод главных компонент, мера центральности, граф, кластеризация, мера сходстваАннотация
Анализ сетей разнообразной природы, которыми являются сети цитирования, а также социальные или информационно-коммуникационные сети, включает изучение топологических свойств, позволяющих оценивать взаимосвязи между узлами сети и различные характеристики, такие как плотность и диаметр сети, связанные подгруппы узлов и тому подобное. Для этого сеть представляется в виде графа – совокупности вершин и ребер между ними. Одной из важнейших задач анализа сетей является оценивание значимости узла (или в терминах теории графов – вершины). Для этого разработаны различные меры центральности, позволяющие оценить степень значимости вершин сетевого графа в структуре рассматриваемой сети.
Существующее многообразие мер центральности порождает проблему выбора той, которая наиболее полно описывает значимость центральность узла.
Актуальность работы обусловлена необходимостью анализа мер центральности для определения значимости вершин, что является одной из основных задач изучения сетей (графов) в практических приложениях.
Проведенное исследование позволило с использованием метода главных компонент среди известных мер центральности выявить коллинеарные меры, которые в дальнейшем можно исключать из рассмотрения. Это позволяет уменьшить вычислительную сложность расчетов, что особенно важно для сетей с большим числом узлов, и повысить достоверность интерпретации получаемых результатов при оценивании значимости узла в рамках анализируемой сети при решении практических задач.
Выявлены закономерности представления различных мер центральности в пространстве главных компонент, что позволяет классифицировать их с точки зрения близости образов узлов сети, формируемых в определяемом применяемыми мерами центральности пространстве.
Литература
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.
Comparative Analysis of Centrality Measures of Network Nodes based on Principal Component Analysis
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.
Опубликован
Как цитировать
Раздел
Copyright (c) Игорь Юрьевич Еремеев, Максим Васильевич Татарка, Федор Леонидович Шуваев, Андрей Сергеевич Цыганов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).