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

Acta mathematica scientia,Series A ›› 2014, Vol. 34 ›› Issue (6): 1554-1577.

• Articles • Previous Articles Next Articles

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

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

CLC Number:

05C80

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.

Trendmd

References

[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

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

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 0