一类偏向删点及顶点有限制的随机图上的相变

数学物理学报 ›› 2014, Vol. 34 ›› Issue (6): 1554-1577.

一类偏向删点及顶点有限制的随机图上的相变

王彬

桂林理工大学理学院广西桂林 |541004

收稿日期:2013-03-27 修回日期:2014-06-18 出版日期:2014-12-25 发布日期:2014-12-25
基金资助:
国家自然科学基金(11001137, 11401127)、广西自然科学基金(2014GXNSFCA118015)和桂林理工大学科研启动金资助

Phase Transition in A Random Graph Process with Preferential Deletion and Limiting on Vertices

WANG Bin

College of Science, Guilin University of Technology, Guilin Guangxi |541004

Received:2013-03-27 Revised:2014-06-18 Online:2014-12-25 Published:2014-12-25
Supported by:
国家自然科学基金(11001137, 11401127)、广西自然科学基金(2014GXNSFCA118015)和桂林理工大学科研启动金资助

摘要/Abstract

摘要：

固定α₀∈[0,1)及β∈[0, 1/2). 该文引入如下随机图过程(G_t)_t≥1: 设在时刻1及2已存在图G₁=G₂, 其中G₁的顶点为v₁, v₂ 且它们之间有2条边相连. 当t≥3时, G_t定义如下: (i) G_t_-1中任意顶点v不活跃的概率为α₀. 顶点不活跃意味着其不能与t 时刻新增加的顶点相连. 此概率独立于自己以及其他顶点t-1之前的状态; (ii) 以概率1-β增加一个新顶点v_t. 在G_t-₁中以概率dw(t-1)/∑_vd_v(t-1) 选一顶点w, 其中d_w(t-1)表w在G_t_-1中的度. 若w是活跃的则在v_t与w之间连1条边, 否则在v_t上加个环; (iii) 以概率β在G_t-₁中删去一顶点u, 其中u被选中的概率为(1-d_u(t-1)/∑_vd_v(t-1))/(n_t_-1-1). 此处, n_t-₁是G_t_-1的顶点个数. 令N_k(t)表G_t中度为k的顶点个数. 该文证明了G_t度分布的期望在2β/ 1-α₀=1附近存在一相变: 当2β/1-α₀ >1时, N_k(t)/t 的期望是呈指数衰减的; 2β/1-α₀<1时, N_k(t)/t 的期望是呈幂律衰减的.

关键词: 度序列, 偏向删点, 随机图过程, 活跃

Abstract:

The following random graph process G_t is introduced. Assuming that at the time-step 1 and 2 there has been a graph G₁=G₂consisting of vertices v₁, v₂and 2 edges between them. At time-step t≥3, G_tis defined as follows: (i) each vertex v∈G_t-1 is inactive with probability α₀, independently its and other vertices' statuses before t-1. The inactiveness of v means it can not being connected by more edges; (ii) with probability 1-β a new vertex v_t is added along with one edge connected to it. Then a vertex w_i is chosen with probability proportional to its degree. If w_i is active then connect v_tto w_i. Otherwise, the edge of v_t is connected to itself; (iii) with probability β a vertex is deleted preferentially from the network. It is proved that there is a phase transition on expected degree distribution when 2β//(1-α₀) is in the vicinity of 1. In the supercritical regime (2β/(1-α₀)>1), its expected fraction of vertices with degree k decays exponentially. While in the subcritical regime (2β/(1-α₀)<1), the expected fraction of vertices with degree k decreases asymptotically as a power law.

Key words: Degree sequence, Preferential deletion, Random graph process, Inactive

中图分类号:

05C80

王彬. 一类偏向删点及顶点有限制的随机图上的相变[J]. 数学物理学报, 2014, 34(6): 1554-1577.

WANG Bin. Phase Transition in A Random Graph Process with Preferential Deletion and Limiting on Vertices[J]. Acta mathematica scientia,Series A, 2014, 34(6): 1554-1577.

参考文献

[1] Albert R, Barab\'{a}si A L. Statistical mechanics of complex networks. Rev Modern Phys, 2002, 74(1): 47--97

[2] Barab\'{a}si A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5349): 509--512

[3] Bollob\'{a}s B. Random Graphs. Cambridge: Cambridge University Press, 2001

[4] Bollob\'{a}s B, et al. The degree sequence of a scale free random graph process. Random Structures Algorithms, 2001, 18(3): 279--290

[5] Bonato A. A Course on the Web Graph. Providence, RI: American Mathematical Society, 2008

[6] Chung F, Lu L. Coupling online and offline analyses for random power law graphs. Internet Math, 2003, 1(4): 409--461

[7] Cooper C, Frieze A. A general model of web graphs.Random Structures Algorithms,2003, 22(3): 311--335

[8] Cooper C, Frieze A, Vera J. Random deletion in a scale-free random graph process. Internet Math, 2003, 1(4): 463--483

[9] Deo N, Cami A. Preferential deletion in dynamic models of web-like networks. Inform Process Lett, 2007, 102(4): 156--162

[10] Dorogovtsev S N, Mendes J F F, Samukhin A N. Structure of growing networks with preferential linking. Phys Rev Lett, 2000, 85(21): 4633--4636

[11] Erd\"{o}s P, R\'{e}nyi A. On random graphs. Publ Math Debrecen, 1959, 5(2): 290--297

[12] Jordan C. Calculus of Finite Differences. Sopron, Hungary: Rottig and Romwalter, 1939

[13] Jordan J. The degree sequences and spectra of scale-free random graphs. Random Structure Algorithms, 2006, 29(2): 226--242

[14] Mori T F. The maximum degree of the Barabasi-Albert random tree. Combin Probab Comput, 2005, 14(3): 339--348

[15] Newman M E J. The structure and function of complex networks. SIAM Rev, 2003, 45(2): 167--256

[16] Pralat P, Wormald N. Growing protean graphs. Internet Mathematics, 2009, 4(1): 1--16

[17] van der Hofstad R. Random Graphs and Complex Networks. Lecture notes in preparation, 2014. See http://www.win.tue.nl/rhofstad/

[18] Tang L, Wang B. A scale-free network with limiting on vertices. Phys A, 2010, 389(10): 2147--2154

[19] Wu X Y, et al. On the degree sequence of an evolving random graph process and its critical phenomenon. J Appl Probab, 2009, 46(4): 1213--1220

[20] Zhou T, et al. Modelling collaboration networks based on nonlinear preferential attachment. Internat J Modern Phys C, 2007, 18(2): 297--314