Ю.Л. Павлов.
О максимальной модулярности случайных конфигурационных графов
Ключевые слова: случайный конфигурационный граф; модулярность; предельная теорема
Рассматриваются конфигурационные графы со случайными независимыми одинаково распределенными степенями вершин. Эти степени равны числу полуребер вершин, занумерованных в произвольном порядке. Граф строится путем попарного равновероятного соединения полуребер для образования ребер. Такие модели можно использовать для адекватного описания топологии транспортных, электрических, социальных сетей и Интернета. Важной характеристикой структуры графа является модулярность. Это мера кластеризации графа в случае разделения вершин на группы (кластеры). Графы с высокой модулярностью обладают высокой плотностью ребер между вершинами внутри кластеров, но слабыми связями между вершинами разных кластеров. В статье обсуждаются понятие модулярности и его свойства в случайных конфигурационных графах. Максимальная модулярность графа используется для описания уровня его кластеризации и для нахождения наилучшего разделения вершин. Доказана предельная теорема для максимальной модулярности при стремлении числа вершин к бесконечности.
Индексируется в РИНЦ