Degree Distribution of Competition-Induced Preferential Attachment Graphs

DOI10.1017/S0963548305006930MaRDI QIDQ5704385zbMATH OpenOpenAlexFDO

Authors

Publication date 14 November 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0502205

zbMATH Keywords

border toll optimization processMarkov processrandom graph process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Stochastic network models in operations research (90B15)

Abstract: We introduce a family of one-dimensional geometric growth models, constructed iteratively by locally optimizing the tradeoffs between two competing metrics, and show that this family is equivalent to a family of preferential attachment random graph models with upper cutoffs. This is the first explanation of how preferential attachment can arise from a more basic underlying mechanism of local competition. We rigorously determine the degree distribution for the family of random graph models, showing that it obeys a power law up to a finite threshold and decays exponentially above this threshold. We also rigorously analyze a generalized version of our graph process, with two natural parameters, one corresponding to the cutoff and the other a ``fertility parameter. We prove that the general model has a power-law degree distribution up to a cutoff, and establish monotonicity of the power as a function of the two parameters. Limiting cases of the general model include the standard preferential attachment model without cutoff and the uniform attachment model.

Recommendations

• Automata, Languages and Programming
• A Geometric Preferential Attachment Model of Networks
• Degree distribution nearby the origin of a preferential attachment graph
• A preferential attachment model with random initial degrees
• Preferential attachment random graphs with general weight function

Cited in

(8)

• Scale-free behavior of networks with the copresence of preferential and uniform attachment rules
• Dynamics of nearest-neighbour competitions on graphs
• Competing growth processes with random growth rates and random birth times
• TOPOLOGICAL ANALYSIS OF SPECIFIC SPATIAL COMPLEX NETWORKS
• scientific article; zbMATH DE number 6311840 (Why is no real title available?)
• On bucket increasing trees, clustered increasing trees and increasing diamonds
• Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds
• A combinatorial approach to the analysis of bucket recursive trees

This page was built for publication: Degree Distribution of Competition-Induced Preferential Attachment Graphs

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