|
This article is cited in 2 scientific papers (total in 2 papers)
Large Systems
New modularity bounds for graphs $G(n,r,s)$ and $G_p(n,r,s)$
N. M. Derevyankoa, M. M. Koshelevb a Moscow Institute of Physics and Technology (National Research University), Moscow, Russia
b Lomonosov Moscow State University, Moscow, Russia
Abstract:
We analyze the behavior of the modularity of $G(n,r,s)$ graphs in the case of $r=o(\sqrt{{n}})$ and $n\to\infty$ and also that of $G_p(n,r,s)$ graphs for fixed $r$ and $s$ as $n\to\infty$. For $G(n,r,s)$ graphs with $r\ge cs^2$, we obtain substantial improvements of previously known upper bounds. Upper and lower bounds previously obtained for $G(n,r,s)$ graphs are extended to the family of $G_p(n,r,s)$ graphs with $p=p(n)=\omega\bigl(n^{-\frac{r-s-1}{2}}\bigr)$ and fixed $r$ and $s$.
Keywords:
modularity, Johnson graphs, clusterization, random graphs.
Received: 22.06.2021 Revised: 27.11.2021 Accepted: 27.11.2021
Citation:
N. M. Derevyanko, M. M. Koshelev, “New modularity bounds for graphs $G(n,r,s)$ and $G_p(n,r,s)$”, Probl. Peredachi Inf., 57:4 (2021), 87–109; Problems Inform. Transmission, 57:4 (2021), 380–401
Linking options:
https://www.mathnet.ru/eng/ppi2358 https://www.mathnet.ru/eng/ppi/v57/i4/p87
|
|