В статье обобщаются базовые понятия, необходимые для исследования и моделирования интернет-сетей.
В данном контексте буду считать понятия “сеть” и “граф” эквивалентными. Для разделения определений используется термин “интернет-сеть” или просто “интернет” (я пишу с маленькой буквы), как обобщение понятия среды (локальной или глобальной) взаимодействия интернет-пользователей. Этот термин не включает в себя вопрос интернет-транспорта - в случае, когда речь идет о маршрутизации, это будет указано отдельно. Под понятием “социальная сеть” понимаются интернет-приложения, основанные на взаимодействиях интернет-пользователей. Понятие “нода” и “узел”, а так же “ребро” и “связь” тождественно в данной статье.
Базовые определения и метрики
Графом \(G\) называется структура, состоящая из \(N\) узлов (нод), соединенных \(L\) ребрами (связями).
Принято разделять графы на направленные (орграфы или directed graphs) и ненаправленные (undirected graphs). При аннотации графа запись определяет направление для направленного графа (\(l(i, j)\) - ребро \(l\) соединяет ноду \(i\) по направлению к ноде \(j\)). В ненаправленных графах связи считаются двунаправленными.
Могут рассматриваться взвешенные сети. В этом случае связь между нодами можно записать так: \(l(i, j, w)\).
Рассматриваются так же многослойные мультиплексные сети. В многослойных сетях каждый слой может строиться на разных наборах нод и/или ребер. Мультиплексные сети строятся на одном множестве нод/ребер. Мултиплексный граф можно отобразить в однослойный, определив разные типы ребер/нод. Темпоральный граф является частным случаем мультиплексного - в нем ребра или узлы являются динамическими и существуют только в определенном интервале времени. Отображение момента (или интервала) времени называется снапшотом графа. Каждый снапшот может интерпретироваться как слой мультиплекса. В общем случае в многослойных сетях могут сущестовать связи как внутри слоя, так и между слоями.
Частным случаем графа является двудольный граф - в нем ноды разделены на две группы так. что существуют только связи между нодами, принадлежащими разным группам.
В основном при анализе интернет-сетей приходится сталкиваться с направленными и ненаправленными графами, взвешенными графами, двудольными графами и мультиплексными сетями.
Полный (полносвязный) граф - это граф, в котором каждая нода соединена с каждой нодой. Для такого графа, если он ненаправленный, можно определить максимальное число связей, как: \(L_{max} = \frac{N\times(N-1)}{2}\)
Для направленного: \(L_{max} = N\times(N-1)\), для двудольного: \(L_{max} = N_1 \times N_2\)
Плотность графа определяет фактически существующую долю связей по отношению к числу связей полносвязного графа. Тогда разреженностью определяется доля отсутствующих ребер: \(d = \frac{L}{L_{max}}\)
Очевидно, что в ненаправленном графе: \(d = \frac{2L}{N\times(N-1)}\), для направленного: \(d = \frac{L}{N\times(N-1)}\), для полносвязного \(d = 1\).
Граф можно считать разреженным, если по мере роста графа число связей в нем растет пропорционально или медленнее числу нод (\(L \sim N\)). Если наблюдается более быстрый рост числа связей, то граф можно считать плотным (к примеру \(L \sim N^3\))
Подграф (подсеть) - выборка подмножества нод графа.
Клика - полносвзяный подграф
Эгосеть - подграф, состоящий из узла и его соседей. Эгосети часто рассматриваются при анализе социальных сетей. Понятие “соседей” здесь - это ноды графа, имеющие связи с рассматриваемым узлом. Из последнего происходит важная метрика: степень узла.
Степень узла определяется числом его соседей. Тогда средняя степень графа: \(\overline{K} = \frac{\sum_{i}K_i}{N}\), где в числителе по сути \(2L\) для ненаправленного графа. Тогда \(\overline{K} = \frac{2L}{N} = d \times (N - 1)\) для ненаправленного графа. Исходя из этого разреженность ненаправленного графа можно определить через среднюю степень узла как \(d = \frac{\overline{K}}{N-1}\). То же самое можно вывести и для направленного графа, подразумевая, что у узла есть \(K_{in}\) и \(K_{out}\). Очевидно, что \(K_{max} = N - 1\) для любого полносвязного графа.
При анализе социальных сетей рассматривают понятие ассортативности - схожести узлов на основе их признаков. Гомофилия сети определяет, что связи между ассортативными узлами более вероятны. Степенная корреляция - ассортативность на основе степени. В этом случае ноды с высокими степенями соединены с нодами с высокой степенью, а ноды с низкой - с низкостепепенными. Такие сети называются ассортативными (обратное указанному состояние - диссортативные сети)
Для взвешенных графов можно определить взвешенную степень (силу) узла - это сумма всех весов его связей: \(S_j = \sum_j W_{ij}\). Для направленного графа так же определяется \(S_{in}\) и \(S_{out}\): \(S_{i}^{in} = \sum_j W_{ji}\), а \(S_{i}^{out} = \sum_j W_{ij}\). При этом мы делаем допущение, что если между нодами нет связей, то \(W=0\)
Важным понятием является матрица смежности графа - это матрица \(N \times N\), где каждый элемент отображает связь между узлами \(i\) (строки) и \(j\) (столбцы). В ненаправленных графах матрицы смежности симметричны относительно диагонали (т.е. связи двунаправленные) и мы можем считать половину матрицы избыточной. Мы можем отображать в матрице как наличие связи, так и количество связей или их вес.
Сама по себе матрица неэффективна для хранения графа (из-за квадратичной сложности по пространству), хотя и очень эффективна в вычислительном плане благодаря матричным операциям. Часто графы сильно разрежены - тогда матрица харнит в основном нули. Чтобы избежать неэффективности часто графы хранят в списках смежности - это структуры, в которых сохраняются соседи для каждого узла. Еще один способ хранения - хранить список соседних нод для нод и/или пары узлов для ребер.
Путь - это непрерывная последовательность ребер. Число ребер определяет длину пути. Цикл - это путь, который можно замкнуть (это важно, так как во многих графовых алгоритмах делаются допущения об ацикличности графа). Простой путь никогда не проходит одно и то же ребро дважды. Кратчайший путь - путь с наименьшей из возможных длиной. Многие задачи в анализе сетей сводятся к поиску/прпедсказанию путей и поиску кратчайшего пути. Средняя длина пути в графе - это усредненное значение длин кратчайших путей между всеми нодами: \(l=\dfrac{2\sum_{i<i}l_{ij}}{N\times(N-1)}\), где \(l_{ij}\) длина кратчайшего пути между \(i\) и \(j\). Для направленной сети \(l=\dfrac{\sum_{i\neq j}l_{ij}}{N\times(N-1)}\).
Диаметр сети - это максимальная длина кратчайшего пути между всеми нодами графа. \(l_{max} = \max_{ij} l_{ij}\)
Связность сети - это мера количества связей в сети. Чем меньше связей и ниже плотность сети, тем более вероятно, что сеть несвязна. Если сеть несвязна, то можно выделить ее связные компоненты - это связные подграфы несвязной сети. Для ненаправленной сети определяют, что в таких компонентах есть путь, соединяющий каждую ноду, но нет пути наружу. В направленной сети выделяют слабосвязные компоненты и сильносвязные компоненты. Слабосвязными являются компоненты, которые можно было бы считать связными только при условии удаления направления связи.
Существует несколько подхода к вычислению расстояний в несвязной сети: измерять расстояние только в главной компоненте (самой большой связной компоненте графа) или можно вычислять расстояния для каждой из компонент, а затем делать обобщение. Средняя длина для несвязной сети вычислительно неразрешима (из-за неопределенности деления на 0). Можно использовать следующий трюк (пример для ненаправленной сети): \(l=\left(2\dfrac{\sum_{i=j}\dfrac{1}{l_{ij}}}{N\times(N-1)}\right)^{-1}\)
Часто рассматривается особый подтип сети, дерево - это такой граф, для которого удаление любой связи приводит к разделению на две компоненты. В деревьях нет циклов и существует только один путь между любой парой узлов. Для деревьев принято выделять какой-то узел как корень, таким образом деревья имеют иерархическую структуру.
Важным показателем сети является ее коэффициент кластеризации, который определяет долю пар соседей узла, соединенных друг с другом. Иными словами, этот коэффициент определяет количество треугольников, образуемых узлом совместно с соседями. \(c{i}=\dfrac{\tau \left( i\right) }{\tau _{\max }\left( i\right) } = \dfrac{2\tau \left( i\right) }{k_{i}\left( ki-1\right) }\), где \(\tau(i)\) - это число треугольников, включающих ноду \(i\). \(C(i)\) определен только для числа соседей \(k>1\), так как, в противном случае, треугольник невозможен. Коэффициент кластеризации всей сети в целом \(C=\dfrac{\sum _{i:k_{i} >1}C\left( i\right) }{N_{k >1}}\) - узлы со степенями \(k<2\) не рассматриваются.