Графы в компьютерных сетях это

Лекция «Сети и теория графов»

Учебные цели: формирование представления о графе и его основных характеристиках.

Тип: Лекция
Автор: Екатерина Калинина
Трудомкость: 2 ч.
Тема: Основы сетевого анализа

Основу теории графов заложила так называемая «Задача о кёнигсбергских мостах», на сегодняшний день ставшая классической. Суть задачи состоит в следующем:

Бывший Кенигсберг (ныне Калининград) расположен на реке Преголя. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.

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

Граф в теории графов – это, в общем случае, математический объект (или геометрическая схема), который представляет собой совокупность вершин, соединенных рёбрами.

Вершины, в зависимости от контекста задачи, могут изображать точки назначения (города, острова, местоположения людей и т.п.), узлы связи (в компьютерных сетях), конкретных людей или адресатов и т.д. Значения рёбер также зависит от условий задачи – они могут обозначать как пути между вершинами, так и связи разного рода (социальные, экономические, физические и т.п.). Поэтому сейчас все чаще выделяют особые виды графов в рамках конкретных областей применения: социальные, молекулярные, веб‑графы и др.

Основные понятия теории графов:

  1. Говорят, что ребро инцидентно вершине, если эта вершина является концом данного ребра.
  2. Два ребра называются смежными, если они имеют общую концевую вершину. Две вершины, инцидентные одному ребру, также называют смежными.
  3. Два ребра называются кратными, если множества их концевых вершин совпадают.
  4. Ребро называется петлёй, если его концы совпадают.
  5. Степень вершины – это количество рёбер, концом которых она является. Если вершине не инцидентно ни одно ребро, такую вершину называют изолированной.
  6. Путь в графе – это любая последовательность вершин, в которой каждые две соседние вершины соединены ребром.
  7. Цикл в графе – это путь, у которого начальная и конечная вершина совпадают.
  1. Ориентированный граф – граф, в котором каждое ребро имеет направление, обозначаемое стрелкой.
  2. Неориентированный граф – граф, в котором рёбра не имеют направлений.
  3. Смешанный граф – граф, в котором присутствуют как ориентированные, так и не ориентированные рёбра.
  4. Мультиграф – граф, содержащий кратные рёбра.
  5. Псевдограф – граф, содержащий кратные рёбра и петли.
  6. Простой граф – граф, в котором не содержатся кратные рёбра и петли.
  7. Полный граф – простой неориентированный граф, в котором две любые вершины смежны.
  8. Плоский граф – граф, который может быть изображён на плоскости без пересечения рёбер.
  9. Дерево – это граф, не содержащий циклов.
Читайте также:  Контроль безопасности в компьютерных сетях

Синонимичным к понятию «граф» является понятие «сеть». Однако сетями чаще всего называют такие графы, вершины которых определенным образом помечены, т.е. несут смысловую нагрузку. Таким образом, графом чаще называют строгий математический объект, к которому применимы все законы теории графов, о сетях чаще говорят в контексте прикладных (социологических, биологических, химических и т.д.) исследований.

Теория сетей и сетевой анализ находят свое применение в различных областях науки, техники, а также повседневной деятельности людей:

  • транспортные системы и сети перевозок;
  • инженерные сети;
  • биологические сети;
  • нейросети (и искусственный интеллект);
  • социальные сети;
  • нарративные (повествовательные) сети;
  • компьютерные сети и др.

Литература

Тематические проекты, онлайн-курсы и программное обеспечение

Библиографическая ссылка: Калинина Е. Сети и теория графов // Изучаем Digital Humanities [Электронный ресурс]. 2018. URL: https://dhumanities.ru/?p=1850

контакты

Динара Амировна Гагарина, сооснователь DH CLOUD Community

Источник

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

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

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

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

Графом \(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