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

Шуваев Федор Леонидович, Татарка Максим Васильевич

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

2020 , ТОМ 20, НОМЕР 2 ( март-апрель )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

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

Аннотация

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

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

Список литературы

Райгородский А.М.Модели случайных графов. М.: Издательство МЦНМО, 2011. 134 с.
Шевченко Д.Н., Литвин А.Ю., Федянин М.А. Имитационное моделирование графа состояний в задачах анализа надежности технических систем // Проблемы физики, математики и техники. 2018. № 3(36). С. 101–104.
Chen P-Y., Choudhury S., Hero A.O. Multi-centrality graph spectral decompositions and their application to cyber intrusion detection // Proc. 41^st IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2016). 2016. P. 4553–4557. doi:10.1109/ICASSP.2016.7472539
Newman M.E.J.Networks: an Introduction. N.Y.: Oxford University Press Inc., 2010. 1042 p.
Rodrigue J.-P. The Geography of Transport Systems. Taylor & Francis, 2017. 440 p.
Watts D., Strogatz H. Collective dynamics of «Small-world» networks // Nature. 1998. V. 393. N 6684. P. 440–442. doi: 10.1038/30918
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
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
Bonchi F., De Francisci G., Riondato M. Centrality measures on big graphs: exact, approximated, and distributed algorithms // Proc. 25^th International Conference Companion on World Wide Web. 2016. P. 1017–1020. doi:10.1145/2872518.2891063
Щербакова Н.Г. Меры центральности в сетях // Проблемы информатики. 2015. № 2. С. 18–30.
Бредихин С.В., Ляпунов В.М., Щербакова Н.Г. Мера важности научной периодики – «Центральность по посредничеству» // Проблемы информатики. 2014. № 3. С. 53–63.
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
Юдина М.Н. Узлы в социальных сетях: меры центральности и роль в сетевых процессах // Омский научный вестник. 2016. № 4. С. 161–165.
Piraveenan M. Topological analysis of complex networks using assortativity. PhD Diss. Sydney: University of Sydney, 2010. 189 p.
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
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
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
Barabasi A. Network Science. Glasgow: Cambridge University Press, 2016. 453 p.
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
Люк Д. Анализ сетей (графов) в среде R: Руководство пользователя / пер. с англ. А.М. Груздева. Издательство ДМК Пресс, 2017. 250 с.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License