2.3. Связность сети .
Поскольку понятие «сеть связи» многообразно, затруднительно составить в общем виде такой перечень параметров, который, с одной стороны, достаточно бы полно характеризовал любую конкретную сеть, а с другой – не содержал бы дублирующих или избыточных именно для данной сети параметров.
Ниже предлагается перечень сетевых параметров, по которому на основании выбранных критериев можно произвести интегральную оценку состояния сети:
· Связность и разветвлённость
Под протяжённостью сети в данном контексте подразумевается суммарная длина всех линий, образующих рассматриваемую сеть
Под связностью сети связи (network connectivity) в данном контексте подразумевается свойство сети, заключающееся в возможности установления связи (соединения) между любыми парами узлов этой сети. Если между хотя бы одной парой узлов соединение невозможно, то сеть является несвязной. Сеть является односвязной, если между всеми узлами возможно соединение и двусвязной, если между узлами возможно соединение по двум независимым путям и т.д. На практике сети имеют неоднородную связность, т.е. имеются, например, фрагменты двусвязные и трехсвязные.
Связность сети является важным параметром, во многом определяющим живучесть сети.
Однако рассчитать указанные выше параметры связности реальной сети большим количеством узлов довольно сложно.
Разветвлённость сети – это параметр, близкий по своей сути к связности. Он характеризуется количеством линий (рёбер) сходящимся к узлам сети. Этот параметр иногда называют доступностью узлов. Формально сеть считается хорошо разветвлённой, если каждому узлу соответствует не менее трёх-четырёх линий. Этот параметр определить гораздо легче.
Термин «пропускная способность» применительно к сети является в значительной степени условным, хотя в литературе встречается достаточно часто. Условность этого термина связана с тем, что информация в разветвлённой сети не передаётся в каком-то определённом направлении, а вводится и принимается одновременно во многих точках и циркулирует по сложной системе линий. Обычно параметр пропускная способность используется для отдельной линии.
Анализ общих характеристик сетей
Произведем анализ общих характеристик сетей. Прежде всего, все сети могут быть разделены на два функциональных класса в зависимости от объекта информации, обрабатываемого в данной сети. Если сеть обрабатывает (коммутирует) отдельное сообщение пользователя или его часть, то такая сеть по отечественной терминологии является вторичной сетью, а по зарубежной терминологии называется сервисной или мельтисервисной сетью. В первичной сети информация обрабатывается не на уровне отдельного сообщения пользователя, а только на агрегированном уровне, не анализируя адреса и признаков начала и конца сообщения, например, кадр SDH, который может состоять из передаваемых элементов (байтов) многих сообщений или быть заполнен частью одного сообщения передается без анализа содержимой в кадре информации. Кроме того, первичная сеть является физической сетью линий и узлов, а все вторичные сети, например, вторичная телефонная сеть, являются логическими сетями,которые строятся на базе первичной сети.. Логические сети обычно имеют структуру отличную от физической сети линий и узлов. Например, пусть телефонная сеть, изображенная на рис1.2а, состоит из телефонных станций АТС1, АТС2,АТС3 и АТС4, связанных прямыми пучками телефонных каналов по типу «каждая с каждой». На рис1.2б отображены совпадающие с АТС сетевые узлы и линии первичной или транспортной сети, на которой строится приведенная на рис1.2а телефонная сеть.
Теория сетей: базовые понятия и метрики
В статье обобщаются базовые понятия, необходимые для исследования и моделирования интернет-сетей.
В данном контексте буду считать понятия “сеть” и “граф” эквивалентными. Для разделения определений используется термин “интернет-сеть” или просто “интернет” (я пишу с маленькой буквы), как обобщение понятия среды (локальной или глобальной) взаимодействия интернет-пользователей. Этот термин не включает в себя вопрос интернет-транспорта — в случае, когда речь идет о маршрутизации, это будет указано отдельно. Под понятием “социальная сеть” понимаются интернет-приложения, основанные на взаимодействиях интернет-пользователей. Понятие “нода” и “узел”, а так же “ребро” и “связь” тождественно в данной статье.
Базовые определения и метрики
Графом \(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
Как сохранить знания с помощью foam и github