Граф - математическая модель представления сетевых структур. Впредь в курсе слова сеть и граф будут обозначать одно и тоже.
Графом $\mathcal{G}$ называется пара множеств $\mathcal{G} = (V, E)$, где $V$ содержит в себе множество вершин (узлов, vertices, nodes), а $E$ содержит множество ребер (связей, edges, links).
Величины $n = |V|$ и $m = |E|$ называют порядком (order of graph) и размером (size of graph) графа.
Ребра, ориентированность, соседи
Граф сверху:
Расстояние на графах
Форматов представления графов довольно много. Все форматы определяют топологию сети (т.е. её структуру), но некоторые могут не сохранять в себе все данные связанные с элементами сети (множество атрибутов ребер и вершин, динамические характеристики, рекоментованную прорисовку и тп).
Ниже мы рассмотрим наиболее распространенные форматы.
Матрица связанности, Incidence matrix, Association matrix.
Матрица связанности - это квадратная матрица размера $n \times n$. Обозначим ее буквой $\mathbf{A}$
В невзвешенном графе:
$\mathbf{A_{ij}} = 1$, если в графе есть ребро между вершинами $v_i$ и $v_j$
$\mathbf{A_{ij}} = 0$, иначе
Во взвешенном графе:
$\mathbf{A_{ij}} = w_{ij}$, если в графе есть ребро между вершинами $v_i$ и $v_j$
$\mathbf{A_{ij}} = 0$, иначе
Для графа выше матрица смежности имеет следующий вид:
Преимущества:
Недостатки:
Edge list
Другой очевидный и популярный формат.
На каждой строчке указываются идентификаторы смежных вершин (числовые признаки этих связей - веса)
Преимущества:
Недостатки:
Adjacency list
Один из самых экономичных форматов.
Каждая строчке соответствует вершине. Через запятую указываются идентификаторы смежных с ней вершин
Преимущества:
Недостатки:
Преимущества:
Недостатки:
Довольно "толстый" формат хранения данных, основанный на языке разметки XML. Представляет их себя набор тэгов, которые могут описать в сети абсолютно все.
Преимущества:
Недостатки:
GML (Graph Modelling Language) - так же гибкий формат представления графов. Однако он является чуть более "читабельным", чем GraphML
Преимущества:
Недостатки:
from IPython.display import VimeoVideo
VimeoVideo('9726202')
В языке python
чаще всего используются следующие библиотеки:
NetworkX
- подходит для работы с небольшими сетямиgraph-tool
- Библиотека для работы с большими сетями при поддержке OpenMP и Boost c API для python
python
igraph
- Библиотека для работы с большими сетями c API для python
и R