Модели предпочтительного присоединения вершин в случайных графах

Рассматриваются динамические модели случайных графов. Классическая модель предпочтительного присоединения была введена А.-Л. Барабашем и Р. Альберт в 1999 году для описания свойств веб-графов. В дальнейшем были предложены различные модификации указанной модели. В докладе дан краткий обзор существующих моделей сложных сетей, в том числе моделей предпочтительного присоединения. Добавление процедуры выбора вершин (для проведения новых ребер) позволяет получить новые асимптотические свойства распределения степеней вершин графов при растущем общем числе вершин. Эти свойства отличаются от тех, которые хорошо известны для классической модели предпочтительного присоединения. В докладе рассмотрены два случая – выбор вершины с наименьшей и с наибольшей степенью. Первый случай можно рассматривать как развитие известной урновой модели, введенной Ю. Азаром, А.З. Бродером, А.Р. Карлин и И. Упфалом в 1999 году. Показано, что асимптотические свойства указанной модели проявляются и в дереве предпочтительного присоединения. Второй случай является обобщением модели Мори дерева предпочтительного присоединения. Нами установлено три принципиально различных типа асимптотического поведения максимальной степени вершины. Таким образом, удалось получить полное описание возможного асимптотического поведения максимальной степени вершины в предложенной автором доклада модели случайных деревьев. Для доказательства основных результатов используется, главным образом, различная вероятностная техника (теория случайных блужданий, стохастическая аппроксимация и мартингальная техника). Применяется также аппарат теории функций.