Preferential attachment with fitness dependent choice

arXiv2012.07390MaRDI QIDQ6356002FDOQ6356002

Yury Malyshkin

Publication date: 14 December 2020

Abstract: We study the asymptotic behavior of the maximum degree in the evolving tree model with a choice based on both degree and fitness of a vertex. The tree is constructed in the following recursive way. Each vertex is assigned a parameter to it that is called a fitness of a vertex. We start from two vertices and an edge between them. On each step we consider a sample with repetition of $d$ vertices, chosen with probabilities proportional to their degrees plus some parameter $$. Then we add a new vertex and draw an edge from it to the vertex from the sample with the highest product of fitness and degree. We prove that dependent on parameters of the model, the maximum degree could exhibit three types of asymptotic behavior: sublinear, linear and of $n/lnn$ order, where $n$ is the number of edges in the graph.

Mathematics Subject Classification ID

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

This page was built for publication: Preferential attachment with fitness dependent choice

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