Core percolation in random graphs: a critical phenomena analysis
Core percolation in random graphs: a critical phenomena analysis
复制标题
DOI：
10.1007/s10051-001-8683-4
复制
发表时间：
2001-12-01
影响因子：
1.6
通讯作者：
Golinelli, O
中科院分区：
文献类型：
--
作者：
Bauer, M;Golinelli, O
我们研究的数值和分析发生了什么事的平均连通性α的随机图时，它的叶子和他们的邻居被反复删除的点时，没有叶子。剩余部分由孤立的顶点加上一个我们称之为核的导出子图组成。在无限随机图的热力学极限下，我们解析地计算了叶子移除的动力学、孤立顶点的数目以及核中的顶点和边的数目。我们证明了二级相变发生在α = e = 2.718.在过渡之下，核心很小，但在过渡之上，它占据初始图的有限部分。有限尺寸标度性质，然后在临界区域进行了详细的数值研究，我们提出了一个一致的临界指数，这并不符合该模型的标准渗流指数集。我们阐明了随机图的邻接矩阵的谱性质和组合优化中的几个方面。
We study both numerically and analytically what happens to a random graph of average connectivity alpha when its leaves and their neighbors are removed iteratively up to the point when no leaf remains. The remnant is made of isolated vertices plus an induced subgraph we call the core. In the thermodynamic limit of an infinite random graph, we compute analytically the dynamics of leaf removal, the number of isolated vertices and the number of vertices and edges in the core. We show that a second order phase transition occurs at alpha = e = 2.718...: below the transition, the core is small but above the transition, it occupies a finite fraction of the initial graph. The finite size scaling properties are then studied numerically in detail in the critical region, and we propose a consistent set of critical exponents, which does not coincide with the set of standard percolation exponents for this model. We clarify several aspects in combinatorial optimization and spectral properties of the adjacency matrix of random graphs.