The power of choice combined with preferential attachement

DOI10.1214/ECP.V19-3461MaRDI QIDQ457799zbMATH OpenFDO

Authors Yury Malyshkin, Elliot Paquette

Publication date 29 September 2014

Published in Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

stochastic approximationpreferential attachmentchoice

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Abstract: We prove almost sure convergence of the maximum degree in an evolving tree model combining local choice and preferential attachment. At each step in the growth of the graph, a new vertex is introduced. A fixed, finite number of possible neighbors are sampled from the existing vertices with probability proportional to degree. Of these possibilities, the vertex with the largest degree is chosen. The maximal degree in this model has linear or near-linear behavior. This contrasts sharply with what is seen in the same choice model without preferential attachment. The proof is based showing the tree has a persistent hub by comparison with the standard preferential attachment model, as well as martingale and random walk arguments.

Recommendations

• Sublinear preferential attachment combined with a growing number of choices
• The power of choice over preferential attachment
• Preferential attachment with choice
• Vertices of high degree in the preferential attachment tree
• The power of choice in growing trees

Cited in

(19)

• Preferential attachment with choice
• Vertices of high degree in the preferential attachment tree
• Existence of a persistent hub in the convex preferential attachment model
• Choices and intervals
• Distance evolutions in growing preferential attachment graphs
• Preferential attachment with choice-based edge step
• Preferential attachment random graphs with edge-step functions
• On several properties of a class of hybrid recursive trees
• Random recursive hypergraphs
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• Preferential attachment with location-based choice: degree distribution in the noncondensation phase
• The power of choice in growing trees
• Sublinear preferential attachment combined with a growing number of choices
• Extensive condensation in a model of preferential attachment with fitness
• Choice-driven phase transition in complex networks
• Connectivity Transitions in Networks with Super-Linear Preferential Attachment
• Branching structure and maximum degree of an evolving random tree
• Preferences in negotiations. The attachment effect.
• The power of choice over preferential attachment

This page was built for publication: The power of choice combined with preferential attachement

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