Limit Distributions of the Number of Loops and the Number of Multiple Edges of One Vertex of a Configuration Graph

В настоящее время существует большое число работ, посвященных
изучению случайных графов предназначенных для моделирования сложных сетей
коммуникаций (см., например, [1] – [3]). Одна из наиболее известных моделей –
конфигурационная модель с независимыми одинаково распределенными степенями
вершин ([1] – [3]). Построение этой модели состоит из двух этапов. На первом этапе для
каждой из
N
вершин графа определяется ее степень в соответствии с некоторым
распределением вероятностей. Для удобства изложения процесса построения такой модели
часто используется понятие полуребра, введенное в [3]. Из каждой вершины графа может
выходить несколько полуребер, число которых равно степени данной вершины.
Подразумевается, что все вершины и полуребра различны. На втором этапе построения
происходит последовательное образование ребер: на каждом шаге два полуребра
выбираются равновероятно и, соединившись, образуют ребро; если сумма всех полуребер
является нечетным числом, то вводится вспомогательная вершина, степень которой равна 1,
и последнее свободное полуребро образует ребро с этой дополнительной вершиной.

This article examines a chance graph that contains
N
vertices, in which
independent similarly distributed chance quantities
  N
, ,
1 
, which are equal to the degrees of
the graph’s vertices, have a binomial distribution with parameters
N, p
, where the parameter
p  pN
is chosen in such a way that
N  , Np  , 0    .
The author obtains the
limit distributions of the number of loops and the number of multiple edges of one vertex of a
chance graph.