Fragility of nonconvergence in preferential attachment graphs with three types

DOI10.2140/INVOLVE.2021.14.531MaRDI QIDQ2233381zbMATH OpenOpenAlexFDO

Authors Ben Andrews, Jonathan H. Jordan

Publication date 18 October 2021

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.00704, https://eprints.whiterose.ac.uk/176662/7/involve-v14-n3-p13-s.pdf

zbMATH Keywords

rock-paper-scissorspreferential attachmentcompeting types

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: Preferential attachment networks are a type of random network where new nodes are connected to existing ones at random, and are more likely to connect to those that already have many connections. We investigate further a family of models introduced by Antunovi'{c}, Mossel and R'{a}cz where each vertex in a preferential attachment graph is assigned a type, based on the types of its neighbours. Instances of this type of process where the proportions of each type present do not converge over time seem to be rare. Previous work found that a "rock-paper-scissors" setup where each new node's type was determined by a rock-paper-scissors contest between its two neighbours does not converge. Here, two cases similar to that are considered, one which is like the above but with an arbitrarily small chance of picking a random type and one where there are four neighbours which perform a knockout tournament to determine the new type. These two new setups, despite seeming very similar to the rock-paper-scissors model, do in fact converge, perhaps surprisingly.

Recommendations

• Non-convergence of proportions of types in a preferential attachment graph with three co-existing types
• Preferential attachment graphs with co-existing types of different fitnesses
• Random networks with concave preferential attachment rule
• Nongrowing preferential attachment random graphs
• Asymptotic behavior and distributional limits of preferential attachment graphs

Cites work

• A survey of random processes with reinforcement
• Asymptotic behavior and distributional limits of preferential attachment graphs
• Coexistence in preferential attachment networks
• Emergence of Scaling in Random Networks
• Non-convergence of proportions of types in a preferential attachment graph with three co-existing types
• The degree sequence of a scale-free random graph process

Cited in

(1)

• Non-convergence of proportions of types in a preferential attachment graph with three co-existing types

This page was built for publication: Fragility of nonconvergence in preferential attachment graphs with three types

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