DOI: 10.17586/2226-1494-2020-20-2-249-256


УДК004.942

АНАЛИЗ ДИНАМИКИ МЕР ЦЕНТРАЛЬНОСТИ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СЛУЧАЙНЫХ ГРАФОВ

Шуваев Ф.Л., Татарка М.В.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Шуваев Ф.Л., Татарка М.В. Анализ динамики мер центральности математических моделей случайных графов // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 2. С. 249–256. doi: 10.17586/2226-1494-2020-20-2-249-256


Аннотация
Предмет исследования. При проектировании и обеспечении информационной безопасности систем связи одним из самых мощных инструментов является имитационное моделирование, которое по сравнению с другими методами позволяет рассматривать системы связи большой емкости, улучшать качество решений по управлению ресурсом сети и точнее прогнозировать их последствия. При этом базовыми математическими моделями для анализируемых систем являются случайные графы. Они дают фундаментальное понимание свойств анализируемых сетей и служат основой для имитационного моделирования. Учитывая высокие темпы развития вычислительных возможностей компьютеров и сред имитационного моделирования, особенно актуальным становится вопрос исследования топологических свойств случайных графов, заключающийся в анализе вероятностной динамики мер центральности. Метод. В ходе эксперимента использованы методы расчета центральности для вершин и графа в целом, основанные на научном аппарате теории графов. При исследовании вероятностной динамики математических моделей графов применена методика сравнения, основанная на диаграммах размахов. Основные результаты. Выполнено исследование динамики мер центральности в модели случайного графа Эрдеша–Реньи, модели малого мира Уоттса–Строгатца и свободно масштабируемой модели Барабаши–Альберта. Проведено сравнение мер центральности этих моделей с реальной сетью. Выявлено, что топологические свойства реальной сети наиболее полно описывает модель Барабаши–Альберта. Представленный в статье анализ мер центральности позволяет проследить взаимосвязи между параметрами различных моделей графов, что в свою очередь может быть применено в анализе реальных сетей. Практическая значимость. Полученные результаты могут быть применены при моделировании физических и социальных систем, представленных в виде графов. Представленные материалы полезны специалистам, занимающимся анализом сетей в различных областях науки и техники: социологии, медицины, физики и радиотехники.

Ключевые слова: граф, вершина, центральность «по посредничеству», центральность «по близости», центральность «по степени», диаграмма размахов

Список литературы
  1. Райгородский А.М.Модели случайных графов. М.: Издательство МЦНМО, 2011. 134 с.
  2. Шевченко Д.Н., Литвин А.Ю., Федянин М.А. Имитационное моделирование графа состояний в задачах анализа надежности технических систем // Проблемы физики, математики и техники. 2018. № 3(36). С. 101–104.
  3. Chen P-Y., Choudhury S., Hero A.O. Multi-centrality graph spectral decompositions and their application to cyber intrusion detection // Proc. 41st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2016). 2016. P. 4553–4557. doi:10.1109/ICASSP.2016.7472539
  4. Newman M.E.J.Networks: an Introduction. N.Y.: Oxford University Press Inc., 2010. 1042 p.
  5. Rodrigue J.-P. The Geography of Transport Systems. Taylor & Francis, 2017. 440 p.
  6. Watts D., Strogatz H. Collective dynamics of «Small-world» networks // Nature. 1998. V. 393. N 6684. P. 440–442. doi: 10.1038/30918
  7. Hartmann A., Mézard M. Distribution of diameters for Erdős-Rényi random graphs // Physical Review E. 2018. V. 97. N 3. P. 032128. doi: 10.1103/PhysRevE.97.032128
  8. Le C., Levina E., Vershynin R. Concentration and regularization of random graphs // Random Structures and Algorithms. 2017. V. 51. N 3. P. 538–561. doi: 10.1002/rsa.20713
  9. Bonchi F., De Francisci G., Riondato M. Centrality measures on big graphs: exact, approximated, and distributed algorithms // Proc. 25th International Conference Companion on World Wide Web. 2016. P. 1017–1020. doi:10.1145/2872518.2891063
  10. Щербакова Н.Г. Меры центральности в сетях // Проблемы информатики. 2015. № 2. С. 18–30.
  11. Бредихин С.В., Ляпунов В.М., Щербакова Н.Г. Мера важности научной периодики – «Центральность по посредничеству» // Проблемы информатики. 2014. № 3. С. 53–63.
  12. Brandes U., Borgatti S., Freeman L.C. Maintaining the duality of closeness and betweenness centrality // Social Networks. 2016. V. 44. P. 153–159. doi: 10.1016/j.socnet.2015.08.003
  13. Юдина М.Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омский научный вестник. 2016. № 4. С. 161–165.
  14. Piraveenan M. Topological analysis of complex networks using assortativity. PhD Diss. Sydney: University of Sydney, 2010. 189 p.
  15. Van Mieghem P., Ge X., Schumm P., Trajanovski S., Wang H. Spectral graph analysis of modularity and assortativity // Physical Review E. 2010. V. 82. N 5. P. 056113. doi: 10.1103/PhysRevE.82.056113
  16. Barzel B., Biham O. Quantifying the connectivity of a network: the network correlation function method // Physical Review E. 2009. V. 80. N 4. P. 046104. doi: 10.1103/PhysRevE.80.046104
  17. Gibson H., Vickers P. Using adjacency matrices to lay out larger small-world networks // Applied Soft Computing Journal. 2016. V. 42. P. 80–92. doi: 10.1016/j.asoc.2016.01.036
  18. Barabasi A. Network Science. Glasgow: Cambridge University Press, 2016. 453 p.
  19. Stauffer D., Meyer-Ortmanns H. Simulation of consensus model of deffuant et al. on a Barabási–Albert network // International Journal of Modern Physics. 2004.V. 15. N 2. P. 241–246. doi: 10.1142/S0129183104005644
  20. Люк Д. Анализ сетей (графов) в среде R: Руководство пользователя / пер. с англ. А.М. Груздева. Издательство ДМК Пресс, 2017. 250 с.


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2020 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика