Preferential attachment with choice

DOI10.1002/RSA.20616MaRDI QIDQ5740274zbMATH OpenOpenAlexFDO

Authors John Haslegrave, Jonathan H. Jordan

Publication date 25 July 2016

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphspreferential attachmentchoice

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We consider the degree distributions of preferential attachment random graph models with choice similar to those considered in recent work by Malyshkin and Paquette and Krapivsky and Redner. In these models a new vertex chooses $r$ vertices according to a preferential rule and connects to the vertex in the selection with the $s$th highest degree. For meek choice, where $s>1$, we show that both double exponential decay of the degree distribution and condensation-like behaviour are possible, and provide a criterion to distinguish between them. For greedy choice, where $s=1$, we confirm that the degree distribution asympotically follows a power law with logarithmic correction when $r=2$ and shows condensation-like behaviour when $r>2$.

Recommendations

• The power of choice over preferential attachment
• The power of choice combined with preferential attachement
• Preferential attachment with location-based choice: degree distribution in the noncondensation phase
• Condensation in preferential attachment models with location-based choice
• A preferential attachment model with random initial degrees

Cites work

• scientific article; zbMATH DE number 5485446 (Why is no real title available?)
• A general model of web graphs
• Achlioptas process phase transitions are continuous
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Emergence of Scaling in Random Networks
• Random trees and general branching processes
• The degree sequence of a scale-free random graph process
• The degree sequences and spectra of scale-free random graphs
• The power of choice combined with preferential attachement
• The power of choice in growing trees
• The power of choice over preferential attachment

Cited in

(15)

• Condensation in preferential attachment models with location-based choice
• Dynamical fitness models: evidence of universality classes for preferential attachment graphs
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Random recursive hypergraphs
• The fluid mechanics of liquid democracy
• Preferential attachment with location-based choice: degree distribution in the noncondensation phase
• The power of choice combined with preferential attachement
• Random walk attachment graphs
• Automata, Languages and Programming
• The power of choice in growing trees
• Sublinear preferential attachment combined with a growing number of choices
• Choice-driven phase transition in complex networks
• The power of two choices for random walks
• Geometric preferential attachment in non-uniform metric spaces
• The power of choice over preferential attachment

This page was built for publication: Preferential attachment with choice

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