Теория графов компьютерные сети

Теория сетей: базовые понятия и метрики

В статье обобщаются базовые понятия, необходимые для исследования и моделирования интернет-сетей.

В данном контексте буду считать понятия “сеть” и “граф” эквивалентными. Для разделения определений используется термин “интернет-сеть” или просто “интернет” (я пишу с маленькой буквы), как обобщение понятия среды (локальной или глобальной) взаимодействия интернет-пользователей. Этот термин не включает в себя вопрос интернет-транспорта — в случае, когда речь идет о маршрутизации, это будет указано отдельно. Под понятием “социальная сеть” понимаются интернет-приложения, основанные на взаимодействиях интернет-пользователей. Понятие “нода” и “узел”, а так же “ребро” и “связь” тождественно в данной статье.

Базовые определения и метрики

Графом \(G\) называется структура, состоящая из \(N\) узлов (нод), соединенных \(L\) ребрами (связями).

Принято разделять графы на направленные (орграфы или directed graphs) и ненаправленные (undirected graphs). При аннотации графа запись определяет направление для направленного графа (\(l(i, j)\) — ребро \(l\) соединяет ноду \(i\) по направлению к ноде \(j\)). В ненаправленных графах связи считаются двунаправленными.

Могут рассматриваться взвешенные сети. В этом случае связь между нодами можно записать так: \(l(i, j, w)\).

Рассматриваются так же многослойные мультиплексные сети. В многослойных сетях каждый слой может строиться на разных наборах нод и/или ребер. Мультиплексные сети строятся на одном множестве нод/ребер. Мултиплексный граф можно отобразить в однослойный, определив разные типы ребер/нод. Темпоральный граф является частным случаем мультиплексного — в нем ребра или узлы являются динамическими и существуют только в определенном интервале времени. Отображение момента (или интервала) времени называется снапшотом графа. Каждый снапшот может интерпретироваться как слой мультиплекса. В общем случае в многослойных сетях могут сущестовать связи как внутри слоя, так и между слоями.

Частным случаем графа является двудольный граф — в нем ноды разделены на две группы так. что существуют только связи между нодами, принадлежащими разным группам.

В основном при анализе интернет-сетей приходится сталкиваться с направленными и ненаправленными графами, взвешенными графами, двудольными графами и мультиплексными сетями.

Читайте также:  Вычислительной сети и его использование

Полный (полносвязный) граф — это граф, в котором каждая нода соединена с каждой нодой. Для такого графа, если он ненаправленный, можно определить максимальное число связей, как: \(L_ = \frac\)

Для направленного: \(L_ = N\times(N-1)\), для двудольного: \(L_ = N_1 \times N_2\)

Плотность графа определяет фактически существующую долю связей по отношению к числу связей полносвязного графа. Тогда разреженностью определяется доля отсутствующих ребер: \(d = \frac>\)

Очевидно, что в ненаправленном графе: \(d = \frac\), для направленного: \(d = \frac\), для полносвязного \(d = 1\).

Граф можно считать разреженным, если по мере роста графа число связей в нем растет пропорционально или медленнее числу нод (\(L \sim N\)). Если наблюдается более быстрый рост числа связей, то граф можно считать плотным (к примеру \(L \sim N^3\))

Подграф (подсеть) — выборка подмножества нод графа.

Клика — полносвзяный подграф

Эгосеть — подграф, состоящий из узла и его соседей. Эгосети часто рассматриваются при анализе социальных сетей. Понятие “соседей” здесь — это ноды графа, имеющие связи с рассматриваемым узлом. Из последнего происходит важная метрика: степень узла.

Степень узла определяется числом его соседей. Тогда средняя степень графа: \(\overline = \fracK_i>\), где в числителе по сути \(2L\) для ненаправленного графа. Тогда \(\overline = \frac = d \times (N — 1)\) для ненаправленного графа. Исходя из этого разреженность ненаправленного графа можно определить через среднюю степень узла как \(d = \frac<\overline>\). То же самое можно вывести и для направленного графа, подразумевая, что у узла есть \(K_\) и \(K_\). Очевидно, что \(K_ = N — 1\) для любого полносвязного графа.

При анализе социальных сетей рассматривают понятие ассортативности — схожести узлов на основе их признаков. Гомофилия сети определяет, что связи между ассортативными узлами более вероятны. Степенная корреляция — ассортативность на основе степени. В этом случае ноды с высокими степенями соединены с нодами с высокой степенью, а ноды с низкой — с низкостепепенными. Такие сети называются ассортативными (обратное указанному состояние — диссортативные сети)

Читайте также:  Плюсы и минусы полносвязной топологии сети

Для взвешенных графов можно определить взвешенную степень (силу) узла — это сумма всех весов его связей: \(S_j = \sum_j W_\). Для направленного графа так же определяется \(S_\) и \(S_\): \(S_^ = \sum_j W_\), а \(S_^ = \sum_j W_\). При этом мы делаем допущение, что если между нодами нет связей, то \(W=0\)

Важным понятием является матрица смежности графа — это матрица \(N \times N\), где каждый элемент отображает связь между узлами \(i\) (строки) и \(j\) (столбцы). В ненаправленных графах матрицы смежности симметричны относительно диагонали (т.е. связи двунаправленные) и мы можем считать половину матрицы избыточной. Мы можем отображать в матрице как наличие связи, так и количество связей или их вес.

Сама по себе матрица неэффективна для хранения графа (из-за квадратичной сложности по пространству), хотя и очень эффективна в вычислительном плане благодаря матричным операциям. Часто графы сильно разрежены — тогда матрица харнит в основном нули. Чтобы избежать неэффективности часто графы хранят в списках смежности — это структуры, в которых сохраняются соседи для каждого узла. Еще один способ хранения — хранить список соседних нод для нод и/или пары узлов для ребер.

Путь — это непрерывная последовательность ребер. Число ребер определяет длину пути. Цикл — это путь, который можно замкнуть (это важно, так как во многих графовых алгоритмах делаются допущения об ацикличности графа). Простой путь никогда не проходит одно и то же ребро дважды. Кратчайший путь — путь с наименьшей из возможных длиной. Многие задачи в анализе сетей сводятся к поиску/прпедсказанию путей и поиску кратчайшего пути. Средняя длина пути в графе — это усредненное значение длин кратчайших путей между всеми нодами: \(l=\dfracl_>\), где \(l_\) длина кратчайшего пути между \(i\) и \(j\). Для направленной сети \(l=\dfracl_>\).

Читайте также:  Сеть смешанной топологии в которую входят несколько локальных вычислительных сетей это

Диаметр сети — это максимальная длина кратчайшего пути между всеми нодами графа. \(l_ = \max_ l_\)

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

Существует несколько подхода к вычислению расстояний в несвязной сети: измерять расстояние только в главной компоненте (самой большой связной компоненте графа) или можно вычислять расстояния для каждой из компонент, а затем делать обобщение. Средняя длина для несвязной сети вычислительно неразрешима (из-за неопределенности деления на 0). Можно использовать следующий трюк (пример для ненаправленной сети): \(l=\left(2\dfrac\dfrac>>\right)^\)

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

Важным показателем сети является ее коэффициент кластеризации, который определяет долю пар соседей узла, соединенных друг с другом. Иными словами, этот коэффициент определяет количество треугольников, образуемых узлом совместно с соседями. \(c=\dfrac\left( i\right) > = \dfrac\), где \(\tau(i)\) — это число треугольников, включающих ноду \(i\). \(C(i)\) определен только для числа соседей \(k>1\), так как, в противном случае, треугольник невозможен. Коэффициент кластеризации всей сети в целом \(C=\dfrac <\sum _1>C\left( i\right) >1>>\) — узлы со степенями \(k

Как сохранить знания с помощью foam и github

Источник

Оцените статью
Adblock
detector