论文标题
关于具有给定度序列的3个规则随机图和随机图的模块化
On the modularity of 3-regular random graphs and random graphs with given degree sequences
论文作者
论文摘要
图的模块化是衡量其社区结构的参数。其值越高（$ 0 $和$ 1 $），图形越多。 在本文中，我们表明，随机$ 3 $定期图的模块化至少是$ 0.667026 $渐近（A.A.S.），从而证明了McDiarmid和Skerman的猜想。我们还改善了A.A.S.上限给出$ 0.789998 $。 对于均匀选择的图形$ g_n $，比给定的有限度序列具有平均度$ d（g_n）$的平均度序列，并带有$ | cc（g_n）| $许多连接的组件，我们区分了两个巨大组件存在的制度。在亚临界方案中，我们计算模块化的第二项。在超临界制度中，我们证明有$ \ varepsilon> 0 $，对于其中，模块化为A.A.S.至少\ begin {equation*} \ dfrac {2 \ left（1-μ\ right）} {d（g_n）}+\ varepsilon，\ end \ end {equation*}，其中$μ$是$μ$几乎是$ \ dfrac {| cc {| cc（g_n）|
The modularity of a graph is a parameter that measures its community structure; the higher its value (between $0$ and $1$), the more clustered the graph is. In this paper we show that the modularity of a random $3$-regular graph is at least $0.667026$ asymptotically almost surely (a.a.s.), thereby proving a conjecture of McDiarmid and Skerman. We also improve the a.a.s. upper bound given therein to $0.789998$. For a uniformly chosen graph $G_n$ over a given bounded degree sequence with average degree $d(G_n)$ and with $|CC(G_n)|$ many connected components, we distinguish two regimes with respect to the existence of a giant component. In the subcritical regime, we compute the second term of the modularity. In the supercritical regime, we prove that there is $\varepsilon > 0$, for which the modularity is a.a.s. at least \begin{equation*} \dfrac{2\left(1 - μ\right)}{d(G_n)}+\varepsilon, \end{equation*} where $μ$ is the asymptotically almost sure limit of $\dfrac{|CC(G_n)|}{n}$.
