Core percolation in random graphs: a critical phenomena analysis

被引:73
作者
Bauer, M [1 ]
Golinelli, O [1 ]
机构
[1] CEA Saclay, Serv Phys Theor, F-91191 Gif Sur Yvette, France
关键词
D O I
10.1007/s10051-001-8683-4
中图分类号
O469 [凝聚态物理学];
学科分类号
070205 ;
摘要
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.
引用
收藏
页码:339 / 352
页数:14
相关论文
共 16 条
[1]  
[Anonymous], P 22 IEEE ANN S FDN
[2]  
Aronson J, 1998, RANDOM STRUCT ALGOR, V12, P111, DOI 10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO
[3]  
2-#
[4]  
Barber M. N, 1983, PHASE TRANSITIONS CR, P146
[5]   Random incidence matrices: Moments of the spectral density [J].
Bauer, M ;
Golinelli, O .
JOURNAL OF STATISTICAL PHYSICS, 2001, 103 (1-2) :301-337
[6]   Exactly solvable model with two conductor-insulator transitions driven by impurities [J].
Bauer, M ;
Golinelli, O .
PHYSICAL REVIEW LETTERS, 2001, 86 (12) :2621-2624
[7]  
BAUER M, 2000, J INTEGER SEQUENCES, V3
[8]  
BOLLOBAS B, 1995, MATH SCI, V20, P69
[9]  
Cvetkovic D. M., 1980, Spectra of Graphs-Theory and Application
[10]   Meanders: exact asymptotics [J].
Di Francesco, P ;
Golinelli, O ;
Guitter, E .
NUCLEAR PHYSICS B, 2000, 570 (03) :699-712