Preferential attachment random graphs with edge-step functions

DOI10.1007/S10959-019-00959-0MaRDI QIDQ2224970zbMATH OpenOpenAlexWikidataFDO

Authors Caio Alves, Rodrigo Ribeiro, Rémy Sanchis

Publication date 4 February 2021

Published in Journal of Theoretical Probability (Search for Journal in Brave)

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

zbMATH Keywords

complex networksconcentration boundsKaramata's theorypower-lawpreferential attachmentregularly varying functionsscale-free

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Other physical applications of random processes (60K40)

Abstract: We propose a random graph model with preferential attachment rule and emph{edge-step functions} that govern the growth rate of the vertex set. We study the effect of these functions on the empirical degree distribution of these random graphs. More specifically, we prove that when the edge-step function $f$ is a emph{monotone regularly varying function} at infinity, the sequence of graphs associated to it obeys a power-law degree distribution whose exponent is related to the index of regular variation of $f$ at infinity whenever said index is greater than $-1$. When the regularly variation index is less than or equal to $-1$, we show that the proportion of vertices with degree smaller than any given constant goes to $0$ a. s..

Recommendations

• Preferential attachment random graphs with general weight function
• Diameter of P.A. random graphs with edge-step functions
• Scale-free property for degrees and weights in a preferential attachment random graph model
• Degree distribution nearby the origin of a preferential attachment graph
• A preferential attachment model with random initial degrees

Cites work

• A general model of web graphs
• A preferential attachment model with random initial degrees
• Collective dynamics of `small-world' networks
• Complex graphs and networks
• Diameter of P.A. random graphs with edge-step functions
• Edge exchangeable models for interaction networks
• Emergence of Scaling in Random Networks
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• Large communities in a scale-free network
• On tail probabilities for martingales
• Random graphs and complex networks. Volume 1
• Robust analysis of preferential attachment models with fitness
• Spatial preferential attachment networks: power laws and clustering coefficients
• The degree sequence of a scale-free random graph process
• The power of choice combined with preferential attachement

Cited in

(14)

• Multivariate regular variation of discrete mass functions with applications to preferential attachment networks
• Growing network: models following nonlinear preferential attachment rule
• Distance evolutions in growing preferential attachment graphs
• Directed hybrid random networks mixing preferential attachment with uniform attachment mechanisms
• Clustering in preferential attachment random graphs with edge-step
• Spread of infection over P.A. random graphs with edge insertion
• Diameter of P.A. random graphs with edge-step functions
• Fluctuations in a general preferential attachment model via Stein's method
• Asymptotic degree distribution in preferential attachment graph models with multiple type edges
• Preferential attachment random graphs with general weight function
• Asymptotic results of a multiple-entry reinforcement process
• Clustering and cliques in preferential attachment random graphs with edge insertion
• Preferential attachment with choice-based edge step
• Condensation effects in spatial preferential attachmentwith edge step

This page was built for publication: Preferential attachment random graphs with edge-step functions

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