On the degree sequence of an evolving random graph process and its critical phenomenon

DOI10.1239/JAP/1261670700zbMATH Open1228.05123arXiv0806.4684OpenAlexW2044783009MaRDI QIDQ3402071FDOQ3402071

Authors: Xian Yuan Wu, Zhao Dong, Ke Liu, Kaiyuan Cai 

Publication date: 2 February 2010

Published in: Journal of Applied Probability (Search for Journal in Brave)

Abstract: In this paper we focus on the problem of the degree sequence for the following random graph process. At any time-step $t$, one of the following three substeps is executed: with probability $alph{a}_1$, a new vertex $x_t$ and $m$ edges incident with $x_t$ are added; or, with probability $alpha-alph{a}_1$, $m$ edges are added; or finally, with probability $1-a$, $m$ random edges are deleted. Note that in any case edges are added in the manner of preferential attachment. we prove that there exists a critical point $alph{a}_c$ satisfying: 1) if $alph{a}_1<alph{a}_c$, then the model has power law degree sequence; 2) if $alph{a}_1>alph{a}_c$, then the model has exponential degree sequence; and 3) if $alph{a}_1=alph{a}_c$, then the model has a degree sequence lying between the above two cases.

Full work available at URL: https://arxiv.org/abs/0806.4684

Recommendations

• On a 2-parameter class of scale free random graphs
• Phase transition on the degree sequence of a random graph process with vertex copying and deletion
• On a random graph evolving by degrees
• Evolution of random graph processes with degree constraints
• The degree sequence of a scale-free random graph process

zbMATH Keywords

power lawdegree sequencecritical phenomenonreal-world networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Cites Work

• Statistical mechanics of complex networks
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• The Structure and Function of Complex Networks
• Random Graphs
• Collective dynamics of `small-world' networks
• Exploring complex networks
• An introduction to the theory of large deviations
• The degree sequence of a scale-free random graph process
• A general model of web graphs
• The diameter of a scale-free random graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Popularity based random graph models leading to a scale-free degree sequence
• Coupling Online and Offline Analyses for Random Power Law Graphs
• Random Deletion in a Scale-Free Random Graph Process
• Title not available (Why is that?)
• Software testing processes as a linear dynamic system

Cited In (13)

• A generalization of the Buckley-Osthus model for web graphs
• Further properties of a random graph with duplications and deletions
• Random cherry graphs
• On dynamic random graphs with degree homogenization via anti-preferential attachment probabilities
• Transition of the degree sequence in the random graph model of Cooper, Frieze, and Vera
• Asymptotic properties of a random graph with duplications
• Phase transition on the degree sequence of a random graph process with vertex copying and deletion
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• The effect of random edge removal on network degree sequence
• The three kinds of degree distributions and Nash equilibrium on the limiting random network
• Asymptotic degree distribution of a duplication-deletion random graph model
• On a random graph evolving by degrees
• Evolution of random graph processes with degree constraints

This page was built for publication: On the degree sequence of an evolving random graph process and its critical phenomenon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3402071)