Geometric preferential attachment with choice-based edge step

Abstract

We study the asymptotic behavior of the maximum degree in the geometric graph model with a preferential attachment choice-based edge step. Geometric graphs are natural models that describe some nanoscale systems, while preferential attachment provides a good description of complex networks, particularly different neural networks. The model is a recursively built sequence of graphs. We start with the initial graph on a single vertex and we add a new vertex and draw a few edges on each step. Each vertex is assigned a parameter that represents its location. The recursion step consists of two parts. First, we introduce a new vertex and draw edges to close enough vertices. This step represents the geometric part of the model. Then, we draw edges between vertices by preferential attachment with the choice rule. We prove that dependent on model parameters, the maximum degree could exhibit sublinear (similar to the standard preferential attachment) and linear (representing concentration effect) behavior.

Keywords

• geometric graphs
• complex networks
• random graphs
• preferential attachment
• power of choice