Модель эволюции распределений степеней вершин графов социальных сетей

Исследуются распределения степеней вершин сетевого графа, образованного дружескими связями социальной сети «ВКонтакте». Вершины социальных графов многомерны, поскольку пользователь описывается многими параметрами, основными из которых, указываемыми при регистрации, являются пол, возраст, регион проживания. Цель исследования состоит в разработке модели, позволяющей приближенно описать структуру связей графа на основе анализа эмпирических частот связей между вершинами. Выяснилось, что распределение вершин социального графа по степеням сильно зависит от того, какому параметру отвечает вершина. Так, распределение региональных связей без учета пола и возраста близко к равномерному, а распределение возрастных связей без учета пола и региона имеет треугольный вид. В результате «городской» граф имеет большое полносвязное ядро и разреженную периферию, а «возрастной» граф — полносвязные сообщества из 5–7 вершин, слабо связанных одно с другим. В работе построены модельные распределения степеней многомерных вершин сетевого графа и изучена зависимость плотности графа от ранга параметров вершин. Рассмотрены также различные способы кластеризации вершин с целью получения полносвязного графа и представлена модель эволюции матриц смежности.