This article is cited in 2 papers

Large Systems

New modularity bounds for graphs $G(n,r,s)$ and $G_p(n,r,s)$

N. M. Derevyanko^a, M. M. Koshelev<sup>b

a</sup> 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.

UDC: 621.391 : 519.175.4

Received: 22.06.2021
Revised: 27.11.2021
Accepted: 27.11.2021

DOI: 10.31857/S0555292321040082

 English version: Problems of Information Transmission, 2021, 57:4, 380–401

Bibliographic databases:

• 
•