Comparative analysis of random graph models
He study of networks of diverse nature, which are citation networks, social networks, or information and telecommunications networks, is given attention in various fields of science: physics, biology, computer science, and mathematics. In-depth studies of the topological properties of such networks contribute to the understanding of its functionality and other inherent features, such as stability. In studies of a diverse nature, much attention is paid to the construction and verification of the adequacy of models, since the reliability of the results depends on it. In the field of network research based on graph theory, there are about ten mathematical models, the main ones being the Erdos-Renyi random graph model (ER), the freely scalable Barabashi-Albert model (BA), and the exponential random graph model (ERGM). The most important quality of the EMSG models is shown in the fact that there are 15 basic network statistics that characterize real networks and allow us to draw statistically significant conclusions about which statistics control the network under study. In this study, a comparative analysis of graph models is carried out, and a statistical assessment of their adequacy to real networks is carried out based on the calculation of the Euclidean distance between the networks. To calculate the Euclidean distance, graph models were presented in the space of parameters of graph characteristics, such as: average path distance (SR), density (PG), assortativity (AS), degree centrality (DC), closeness centrality (CC), betweenness centrality (BC), eigen vector centrality (EVC), transitivity (Tr), diameter (Di). The parameter space was reduced on the basis of McKay statistics. These statistics showed that the characteristics of the AS, BC, and EVC did not meet the requirements of data uniformity, so they were excluded. As a result of the study, it is shown that the closest to real networks that reflect the types of human activity are ERGM. This proximity to real networks was achieved, among other things, by an improved algorithm for configuring ERGM, which consists in selecting the best combination of terminals according to the Akaike information criterion.
Keywords
graph,
exponential model,
criterion of agreement,
measure of proximity,
assessmentAuthors
| Kuzmin Vladimir N. | Mozhaisky Military Space Academy, St. Petersburg | kuzmindvn@ya.ru |
| Shuvaev Fedor L. | Mozhaisky Military Space Academy, St. Petersburg | cadetfed@mail.ru |
| Rozganov Maxim V. | Mozhaisky Military Space Academy, St. Petersburg | mrozganov@mail.ru |
Всего: 3
References
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. P. 4553-4557.
Шуваев Ф.Л., Татарка М.В. Анализ динамики мер центральности математических моделей случайных графов // Научно технический вестник информационных технологий, механики и оптики. 2020. Т. 20, № 2. С. 249-256.
Hartmann A., Mezard M. Distribution of diameters for Erdos-Renyi random graphs // Phys. Rev. 2018. V. 97, № 3. DOI: 10.1103/PhysRevE.97.032128
Gibson H., Vickers P. Using adjacency matrices to lay out larger small-world networks // Applied Soft Computing. 2016. V. 42. P. 80-92.
Шуваев Ф.Л., Татарка М.В. Анализ математических моделей случайных графов, применяемых в имитационном модели ровании информационно-коммуникационных сетей // Вестник Санкт-Петербургского университета ГПС МЧС России. 2020. № 2. C. 67-77.
Barabasi A.Network Science. Glasgow : Cambridge university press, 2016. 453 p.
Bonchi F., De Francisci G., Riondato M. Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms // Proc. of the 25th International Conference Companion on World Wide Web. 2016. P. 1017-1020.
Brandes U., Borgatti S., Freeman L. Maintaining the duality of closeness and betweenness centrality // Social Networks. 2016. V. 44. P. 153-159.
Minoo A., Salehzadeh-Yazdi А., Razaghi-Moghadam Z., Hennig H., Wolkenhauer O. A Systematic survey of centrality measures for protein-protein interaction networks // Systems Biology. 2018. V. 12 (1). P. 80-88.
Seo H., Thorson S.J. ERGM approach to press freedom, regime type, and Internet connectedness // First Monday. 2019. V. 24, № 9. URL: https://firstmonday.org/ojs/index.php/fm/article/view/9428 (accessed: 05.09.2020).
Wang P., Robins G., Pattison P., Lazega E. Social selection models for multilevel networks // Social Networks. 2015. V. 35. P. 96-115.
Golshid Sharifnia S., Saghaei A. A statistical approach for social network change detection: an ERGM based framework // Communications in Statistics - Theory and Methods. 2020. DOI: 10.1080/03610926.2020.1772981
Marnissi Y., Chouzenoux E., Benazza-Benyahia A., Pesquet J. Majorize-minimize adapted Metropolis-Hastings algorithm // IEEE Xplore, 2020. P. 2356-2369.
Teixeira J., Stutz L., Knupp D., Silva Neto A. A new adaptive approach of the Metropolis-Hastings algorithm applied to structural damage identification using time domain data // Applied Mathematical Modelling. 2020. V. 82 (1). P. 587-606.
Zvereva О. Triad Census Usage for Communication Network Analysis // CEUR Workshop Proc. 2016. V. 1710. Р. 378-389.
Brunson J.C. Triadic analysis of affiliation networks // Network Science. 2015. V. 3(4). Р. 480-508.
Faust K. A puzzle concerning triads in social networks: Graph constraints and the triad census // Social Networks. 2010. № 32. P. 221-233.
Package ‘network'. URL: https://cran.r-project.org/web/packages/network/network.pdf (accessed: 05.09.2020).
Package ‘ergm'. URL: https://cran.r-project.org/web/packages/ergm/ergm.pdf (accessed: 05.09.2020).
Panichkitkosolkul W. Confidence intervals for the coefficient of variation in a normal distribution with a known population mean // Journal of probability and statistic. 2013. № 2. P. 34-46.
Albatineh A., Golam Kibria B., Wilcox M., Zogheib B. Confidence interval estimation for the population coefficient of variation using ranked set sampling: a simulation study // Journal of applied statistics. 2014. V. 41. P. 733-751.
Beigy M. Coefficient of Variation: cv_versatile. 2019. URL: https://cran.r-project.org/web/packages/cvcqv/vignettes/cv_versatile.html (accessed: 04.12.2020).
