.png){kind=icon}
返回
Modularity of Preferential Attachment Graphs
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.76.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究一个偏好连接模型G(n)(h)。图G(n)(h)通过逐次添加新顶点从有限初始图生成。每个新顶点连接到h≥1个已存在的顶点，这些顶点按其当前度数成比例的概率被选择。我们特别关注G(n)(h)的社区结构，该结构以所谓的模块度来表示。我们证明，G(n)(h)的模块度以高概率被一个随着h趋于无穷大而趋于0的函数所上界。这解决了Prokhorenkova、Pralat和Raigorodskii在2016年提出的猜想。作为副产品，我们获得了关于G(n)(h)顶点子集的体积和边密度参数的新集中结果（这些结果本身就很有趣）。关键在于定义一个函数μ，它作为顶点子集的自然度量，与这些子集体积的平均大小成比例。这扩展了Frieze、Perez-Gimenez、Pralat和Reiniger在2019年关于该主题的研究结果。
Keyword:
Modularity
preferential attachment model
edge expansion
