МОДЕЛИ СЛУЧАЙНЫХ ГРАФОВ И ИХ ПРИМЕНЕНИЕ В СОЦИАЛЬНЫХ СЕТЯХ

RANDOM GRAPH MODELS AND THEIR APPLICATION IN SOCIAL NETWORKS

Nekhai Anastasiya Yuryevna

Student, Faculty of Engineering and Economics, Belarusian State University of Informatics and Radioelectronics,

Republic of Belarus, Minsk

Fedosyuk Lyudmila Petrovna

Scientific supervisor, Associate Professor, Department of Economic Informatics, Belarusian State University of Informatics and Radioelectronics,

Republic of Belarus, Minsk

АННОТАЦИЯ

В статье рассматриваются основные модели случайных графов, применяемые для анализа социальных сетей. Описываются модель Эрдёша-Реньи, конфигурационная модель, модели безмасштабных сетей на основе предпочтительного присоединения, модель малого мира Уоттса-Строгаца и экспоненциальные модели случайных графов. Показано, как эти модели используются в качестве нулевых эталонов, инструментов имитационного моделирования и средств статистического анализа механизмов формирования связей между пользователями.

ABSTRACT

The article discusses the main random graph models used for the analysis of social networks. It describes the Erdos-Renyi model, the configuration model, scale-free models based on preferential attachment, the Watts-Strogatz small-world model, and exponential random graph models. The paper shows how these models are applied as null models, tools for simulation, and methods for statistical analysis of link formation mechanisms between users.

Ключевые слова: случайный граф; социальная сеть; модель Эрдёша-Реньи; конфигурационная модель; безмасштабная сеть; экспоненциальная модель случайного графа.

Keywords: random graph; social network; Erdos-Renyi model; configuration model; scale-free network; exponential random graph model.

Социальные сети можно представить в виде графов, в которых вершины соответствуют пользователям, а рёбра описывают связи между ними, например переписку, подписки, участие в общих группах или совместных мероприятиях. Такие сети включают много участников и связей и изменяются во времени, поэтому для их изучения применяют модели случайных графов.

Одна из базовых моделей в теории случайных графов – модель Эрдёша-Реньи. В рамках этой модели предполагается, что между любыми двумя участниками связь возникает случайно, с одной и той же вероятностью и независимо от остальных связей. Эта модель хорошо подходит для изучения общих свойств случайных сетей: появления большой связной группы, среднего числа связей, примерных расстояний между участниками. При анализе социальных сетей модель Эрдёша-Реньи задаёт «случайный эталон», с которым сравнивают реальные сети. Если, например, в наблюдаемой социальной сети обнаруживается более высокий уровень группирования пользователей, чем в случайном графе с тем же числом вершин и рёбер, это свидетельствует о действии дополнительных механизмов, связанных с социальной природой связей.

Конфигурационная модель ориентирована на те ситуации, когда важно сохранить фактическое распределение числа связей у участников. В этой модели заранее задаётся, сколько связей имеет каждый узел, а далее связи распределяются случайным образом между участниками так, чтобы соблюсти эти значения. В результате получается случайная сеть с тем же распределением степеней, что и у реальной сети, но без специфической структуры групп и кластеров. На практике конфигурационная модель применяется как более строгая нулевая модель: с её помощью можно отделить эффекты, которые объясняются только неравномерным числом связей у пользователей, от эффектов, связанных с особыми паттернами соединений.

Во многих крупных социальных сетях наблюдается неравномерное распределение числа связей: большинство пользователей имеют немного контактов, а небольшая часть пользователей обладает очень большим числом связей. Для описания сетей с подобной структурой используются модели безмасштабных сетей, основанные на механизме предпочтительного присоединения. В этих моделях сеть рассматривается как растущая: новые участники последовательно включаются в сеть и связываются с уже существующими пользователями. Вероятность того, что новый участник установит связь с конкретным пользователем, возрастает с увеличением числа уже имеющихся у этого пользователя связей. Таким образом, узлы с большим числом связей получают новые связи чаще, чем остальные. На практике такие модели применяются для анализа того, как формируются центры активности в социальных сетях, а также для оценки влияния структурных лидеров на распространение информации.

Ещё одно важное свойство социальных сетей – это сочетание высокой локальной связанности с малой длиной пути между любыми двумя участниками. В сетях такого типа пользователи образуют плотные группы, при этом от одного участника до другого можно дойти через небольшое число промежуточных связей. Для описания такой структуры используется модель малого мира Уоттса-Строгаца. В исходной конфигурации сеть строится как регулярная: каждый участник соединён с ограниченным числом ближайших соседей. Затем часть связей перенаправляется на более удалённых участников случайным образом. Это приводит к появлению редких длинных связей, которые сокращают расстояния между далекими частями сети, но сохраняя высокий уровень локального объединения. Подобные модели используют для анализа сочетания локальных сообществ и глобальной связности, а также для исследования путей распространения новостей, сообщений и других видов контента.

Кроме генеративных моделей, описывающих правила построения сети, в анализе социальных сетей применяются статистические модели, которые задают распределение вероятностей на множестве возможных структур. К таким моделям относятся экспоненциальные модели случайных графов. В этом подходе вероятность конкретной сетевой структуры выражается через набор структурных характеристик: количество связей, число взаимных пар, число треугольников, показатели связи между пользователями с похожими атрибутами. Параметры модели отражают вклад каждого из этих механизмов в формирование сети. Экспоненциальные модели случайных графов используются для статистической проверки гипотез о том, присутствует ли в сети склонность к взаимным связям, образованию триад или объединению по признакам, таким как возраст, профессиональная сфера или интересы. На основе оценённых параметров можно судить, какие структурные эффекты действительно характерны для данной социальной сети.

Перечисленные модели применяются совместно при исследовании реальных социальных сетей. Модель Эрдёша-Реньи и конфигурационная модель служат эталонными случайными сетями, с которыми сравнивают наблюдаемые данные. Модели с предпочтительным присоединением показывают, как в сети формируются хабы (пользователи с большим числом связей) и помогают понять их роль в структуре и функционировании сети. Модель малого мира позволяет анализировать, как в сети сочетаются устойчивые локальные группы и короткие пути между любыми участниками. Экспоненциальные модели позволяют количественно оценить влияние различных социальных механизмов на структуру сети. Совместное использование этих подходов даёт возможность описывать, моделировать и объяснять наблюдаемые свойства социальных сетей, а также планировать эксперименты и разрабатывать алгоритмы обработки сетевых данных.

Список литературы:

1. Райгородский А.М. Модели случайных графов и их применения // Труды МФТИ. – 2010. – Т. 2. – № 4. – С. 130–140.
2. Newman M.E.J. The structure and function of complex networks // SIAM Review. – 2003. – Vol. 45. – P. 167–256.
3. Newman M.E.J. Models of the Small World: A Review // Journal of Statistical Physics. – 2000. – Vol. 101. – P. 819–841.
4. Barabasi A.-L., Albert R. Emergence of Scaling in Random Networks // Science. – 1999. – Vol. 286. – P. 509–512.