Title: New bounds on the modularity of $G(n,p)$ Show Chinese title

Title: 关于$G(n,p)$模性新的界限

Abstract: Modularity is a parameter indicating the presence of community structure in the graph. Nowadays it lies at the core of widely used clustering algorithms. We study the modularity of the most classical random graph, binomial $G(n,p)$. In 2020 McDiarmid and Skerman proved, taking advantage of the spectral graph theory and a specific subgraph construction by Coja-Oghlan from 2007, that there exists a constant $b$ such that with high probability the modularity of $G(n,p)$ is at most $b/\sqrt{np}$. The obtained constant $b$ is very big and not easily computable. We improve upon this result showing that a constant under $3$ may be derived here. Interesting is the fact that it might be obtained by basic probabilistic tools. We also address the lower bound on the modularity of $G(n,p)$ and improve the results of McDiarmid and Skerman from 2020 using estimates of bisections of random graphs derived by Dembo, Montanari, and Sen in 2017. Show Chinese abstract

Abstract: 模ularity 是一个参数，用于指示图中是否存在社区结构。如今，它已成为广泛使用的聚类算法的核心。 我们研究了最经典的随机图——二项式随机图 $G(n,p)$ 的模ularity。 2020年，McDiarmid 和 Skerman 借助2007年由 Coja-Oghlan 提出的谱图理论以及特定子图构造方法，证明了存在一个常数 $b$，使得以高概率来说， $G(n,p)$ 的模ularity 至多为 $b/\sqrt{np}$。所得的常数 $b$ 非常大且难以计算。 我们改进了这一结果，表明这里可以得到一个小于 $3$ 的常数。有趣的是，这可能通过基本的概率工具获得。 我们还探讨了 $G(n,p)$ 的模ularity 下界，并利用 Dembo、Montanari 和 Sen 在2017年得出的关于随机图划分的估计值，改进了 McDiarmid 和 Skerman 在2020年的结果。