RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2021, том 57, выпуск 4, страницы 87–109 (Mi ppi2358)

Эта публикация цитируется в 2 статьях

Большие системы

Новые оценки модулярности графов $G(n,r,s)$ и $G_p(n,r,s)$

Н. М. Деревянкоa, М. М. Кошелевb

a Московский физико-технический институт (национальный исследовательский университет)
b Московский государственный университет им. М.В. Ломоносова

Аннотация: Исследуется поведение модулярности графов $G(n,r,s)$ для случая $r=o(\sqrt{{n}})$ и $n\to\infty$, а также графов $G_p(n,r,s)$ при фиксированных $r$, $s$ и $n\to\infty$. Для графов $G(n,r,s)$ при $r\ge cs^2$ получены существенные улучшения предыдущих верхних оценок. На семейство графов $G_p(n,r,s)$ при $p=p(n)=\omega\bigl(n^{-\frac{r-s-1}{2}}\bigr)$ и фиксированных $r$ и $s$ перенесены верхние и нижние оценки, полученные ранее для графов $G(n,r,s)$.

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

УДК: 621.391 : 519.175.4

Поступила в редакцию: 22.06.2021
После переработки: 27.11.2021
Принята к печати: 27.11.2021

DOI: 10.31857/S0555292321040082


 Англоязычная версия: Problems of Information Transmission, 2021, 57:4, 380–401

Реферативные базы данных:


© МИАН, 2024