Мы исследуем асимптотическое поведение максимальной степени в графах пространственного предпочтительного присоединения, с дополнительным шагом с выбором ребер. В пространственных моделях предпочтительного присоединения каждой вершине присваивается координата (в нашем случае, случайное число в [0,1]). Модель строится рекурсивно, причем шаг рекурсии состоит из двух частей. Сначала мы вводим новую вершину и проводим k ребер от нее к близлежащим вершинам, выбранным с помощью слегка модифицированного правила пространственного предпочтительного присоединения. Затем мы проводим m ребер между вершинами по правилу обычного предпочтительного присоединения. В статье доказывается, что в зависимости от параметров модели максимальная степень может демонстрировать сублинейное (аналогично стандартному предпочтительному присоединению) и линейное поведение двух видов: случайное распределение, подобное классической урновой модели, и концентрацию у фиксированного значения (такой эффект наблюдался в моделях предпочтительного присоединения с выбором).
We study the asymptotic behavior of the maximum degree in the spatial preferential attachment graph model with a preferential attachment edge step. In spatial models, each vertex is assigned a coordinate (in our case, in [0,1]). The model is built recursively, with the recursion step consisting of two parts. First, we introduce a new vertex and draw k edges from it to close vertices, chosen by a slightly modified spatial preferential attachment rule. Then, we draw m edges between vertices by the preferential attachment rule. We prove that, dependent on model parameters, the maximum degree could exhibit sublinear (similar to the standard preferential attachment) and linear behavior of 2 types: random distribution similar to the classical urn model and concentration over a fixed value (such an effect was observed in models with the addition of choice).
The authors declare that there are no conflicts of interest present.