Preferential attachment with choice

DOI10.1002/RSA.20616zbMATH Open1341.05230arXiv1407.8421OpenAlexW2236316965MaRDI QIDQ5740274FDOQ5740274

Authors: John Haslegrave, Jonathan H. Jordan 

Publication date: 25 July 2016

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

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$.

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

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

zbMATH Keywords

random graphspreferential attachmentchoice

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• 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
• Condensation in preferential attachment models with location-based choice

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)