On nodes of small degrees and degree profile in preferential dynamic attachment circuits

DOI10.1007/S11009-019-09726-4MaRDI QIDQ2195950zbMATH OpenOpenAlexWikidataFDO

Authors Panpan Zhang, Hosam M. Mahmoud

Publication date 28 August 2020

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

complex networkdegree profilemultivariate martingalepreferential attachmentPólya urnrandom circuit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Martingales with discrete parameter (60G42)

Abstract: We investigate the joint distribution of nodes of small degrees and the degree profile in preferential dynamic attachment circuits. In particular, we study the joint asymptotic distribution of the number of the nodes of outdegree $0$ (terminal nodes) and outdegree $1$ in a very large circuit. The expectation and variance of the number of those two types of nodes are both asymptotically linear with respect to the age of the circuit. We show that the numbers of nodes of outdegree $0$ and $1$ asymptotically follow a two-dimensional Gaussian law via multivariate martingale methods. We also study the exact distribution of the degree of a node, as the circuit ages, via a series of P'olya-Eggenberger urn models with "hiccups" in between. The exact expectation and variance of the degree of nodes are determined by recurrence methods. Phase transitions of these degrees are discussed briefly. This is an extension of the abstract [20].

Recommendations

• On terminal nodes and the degree profile of preferential dynamic attachment circuits
• Joint degree distributions of preferential attachment random graphs
• Degree asymptotics with rates for preferential attachment random graphs
• Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment
• Random networks with sublinear preferential attachment: degree evolutions

Cites work

• A generalized Pólya urn and limit laws for the number of outputs in a family of random circuits
• A limit law for outputs in random recursive circuits
• A note on limit theorems for multivariate martingales
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Asymptotic joint normality of counts of uncorrelated motifs in recursive trees
• Asymptotic normality of degree counts in a preferential attachment model
• Asymptotic normality of in- and out-degree counts in a preferential attachment model
• Degree asymptotics with rates for preferential attachment random graphs
• Emergence of Scaling in Random Networks
• Generalized gamma approximation with rates for urns, walks and trees
• Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Joint degree distributions of preferential attachment random graphs
• Limit laws for terminal nodes in random circuits with restricted fan-out: a family of graphs generalizing binary search trees
• On terminal nodes and the degree profile of preferential dynamic attachment circuits
• On the structure of random plane‐oriented recursive trees and their branches
• Polya Urn Models
• Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution
• Profiles of random trees: Limit theorems for random recursive trees and binary search trees
• Profiles of random trees: Plane-oriented recursive trees
• Robust analysis of preferential attachment models with fitness
• The class of tenable zero-balanced Pólya urn schemes: characterization and Gaussian phases
• The degree distribution of thickened trees
• The degree profile in some classes of random graphs that generalize recursive trees
• The degree sequence of a scale-free random graph process

Cited in

(8)

• Directed hybrid random networks mixing preferential attachment with uniform attachment mechanisms
• Dynamic Pólya-Eggenberger urns
• Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment
• Profile of random exponential recursive trees
• Uniform preferential selection model for generating scale-free networks
• The degree profile in some classes of random graphs that generalize recursive trees
• On terminal nodes and the degree profile of preferential dynamic attachment circuits
• Degree profile of hierarchical lattice networks

This page was built for publication: On nodes of small degrees and degree profile in preferential dynamic attachment circuits

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