控制团数量的随机图模型会自发形成近似平衡的多分块结构。
Exponential random graph models with soft clique constraints
- 通过软团约束权重，使少团图更可能生成。
- 大图中顶点被分为r-1个大小相近的组，组间边密接近1/2，组内极稀疏。
- 结果与权重无关，适用于多种团规模组合场景。
固定 r≥3，令 𝔾ₙ 为顶点集 [n] = {1,…,n} 上所有简单图的集合。本文研究一种指数随机图模型：若图 G ∈ 𝔾ₙ 的 r-团数少于图 H ∈ 𝔾ₙ，G 比 H 更可能被采样；但所有图均具有正概率。图的团数偏好程度由正权重 w 决定。我们证明：当 n→∞ 时，几乎必然地，随机图在 𝔾ₙ 中具有一个顶点划分，分为 r−1 个大小大致相等的部分，部分之间的边密度接近 1/2，且对任意 ε>0，任一部分内部的边密度小于 ε。该渐近结构特性在 w>0 时独立于权重。我们还将结果扩展至多个团规模，每类团有各自权重的情形。
原文摘要 · Abstract (English)
Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n \to \infty$, a random graph from $\mathbf{G}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。