Стохастические системы

Исследование количества треугольников в графах, эволюционирующих кластерным присоединением

М. Вайчюлис^a, Н. М. Маркович<sup>b

a</sup> Институт науки данных и цифровых технологий Вильнюсского университета, Литва
^b Институт проблем управления им. В.А. Трапезникова РАН, Москва

Аннотация: Модель кластерного присоединения (КП), предложенная Багроу и Брокманном (2013 г.), может быть использована как инструмент эволюции ненаправленных случайных сетей. В статье вводится обобщенное определение модели КП. Теоретические результаты получены для новой модели КП, которую можно рассматривать как предел прежней, когда параметр модели $\alpha$ стремится к нулю, а параметр $\epsilon=0$. Предметом исследования является количество треугольников связанных узлов в графе на шаге эволюции $n$ – важная характеристика кластеризации сети. Доказано, что количество треугольников стремится к бесконечности с вероятностью единица для предложенной модели эволюции при $n\to\infty$, а скорость роста среднего количества треугольников $E \Delta_n$ на шаге эволюции ${n\ge 2}$ выше логарифмической. Компьютерное моделирование использовано для моделирования последовательностей количества треугольников. Данное моделирование основано на обобщенной модели урн Пойа–Эггенбергера, что предложено впервые.

Ключевые слова: кластерное присоединение, коэффициент кластеризации, вес узла, случайный граф, эволюция, модель урн.

Статья представлена к публикации членом редколлегии: А. И. Ляхов

Поступила в редакцию: 18.01.2024
После доработки: 26.08.2024
Принята к публикации: 20.09.2024

DOI: 10.31857/S0005231024110034

 Англоязычная версия: Automation and Remote Control, 2024, 85:11, 978–989