Лекция «Сети и теория графов»
Учебные цели: формирование представления о графе и его основных характеристиках.
Тип: Лекция
Автор: Екатерина Калинина
Трудомкость: 2 ч.
Тема: Основы сетевого анализа
Основу теории графов заложила так называемая «Задача о кёнигсбергских мостах», на сегодняшний день ставшая классической. Суть задачи состоит в следующем:
Бывший Кенигсберг (ныне Калининград) расположен на реке Преголя. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Издавна гостей Кёнигсберга интересовал вопрос: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался этой задачей, после чего привел строгое доказательство того, что сделать это невозможно. Результаты исследования Эйлера заложили основу теории графов и отлично иллюстрируют направление её развития в настоящее время.
Граф в теории графов – это, в общем случае, математический объект (или геометрическая схема), который представляет собой совокупность вершин, соединенных рёбрами.
Вершины, в зависимости от контекста задачи, могут изображать точки назначения (города, острова, местоположения людей и т.п.), узлы связи (в компьютерных сетях), конкретных людей или адресатов и т.д. Значения рёбер также зависит от условий задачи – они могут обозначать как пути между вершинами, так и связи разного рода (социальные, экономические, физические и т.п.). Поэтому сейчас все чаще выделяют особые виды графов в рамках конкретных областей применения: социальные, молекулярные, веб‑графы и др.
Основные понятия теории графов:
- Говорят, что ребро инцидентно вершине, если эта вершина является концом данного ребра.
- Два ребра называются смежными, если они имеют общую концевую вершину. Две вершины, инцидентные одному ребру, также называют смежными.
- Два ребра называются кратными, если множества их концевых вершин совпадают.
- Ребро называется петлёй, если его концы совпадают.
- Степень вершины – это количество рёбер, концом которых она является. Если вершине не инцидентно ни одно ребро, такую вершину называют изолированной.
- Путь в графе – это любая последовательность вершин, в которой каждые две соседние вершины соединены ребром.
- Цикл в графе – это путь, у которого начальная и конечная вершина совпадают.
- Ориентированный граф – граф, в котором каждое ребро имеет направление, обозначаемое стрелкой.
- Неориентированный граф – граф, в котором рёбра не имеют направлений.
- Смешанный граф – граф, в котором присутствуют как ориентированные, так и не ориентированные рёбра.
- Мультиграф – граф, содержащий кратные рёбра.
- Псевдограф – граф, содержащий кратные рёбра и петли.
- Простой граф – граф, в котором не содержатся кратные рёбра и петли.
- Полный граф – простой неориентированный граф, в котором две любые вершины смежны.
- Плоский граф – граф, который может быть изображён на плоскости без пересечения рёбер.
- Дерево – это граф, не содержащий циклов.
Синонимичным к понятию «граф» является понятие «сеть». Однако сетями чаще всего называют такие графы, вершины которых определенным образом помечены, т.е. несут смысловую нагрузку. Таким образом, графом чаще называют строгий математический объект, к которому применимы все законы теории графов, о сетях чаще говорят в контексте прикладных (социологических, биологических, химических и т.д.) исследований.
Теория сетей и сетевой анализ находят свое применение в различных областях науки, техники, а также повседневной деятельности людей:
- транспортные системы и сети перевозок;
- инженерные сети;
- биологические сети;
- нейросети (и искусственный интеллект);
- социальные сети;
- нарративные (повествовательные) сети;
- компьютерные сети и др.
Литература
Тематические проекты, онлайн-курсы и программное обеспечение
Библиографическая ссылка: Калинина Е. Сети и теория графов // Изучаем 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
Как сохранить знания с помощью foam и github