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

DOI10.1239/JAP/1261670700MaRDI QIDQ3402071zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

power lawdegree sequencecritical phenomenonreal-world networks

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(13)

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

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)