Графики

Оригинал: Глава 2 Графы

Переводчик: Wizardforcel

Лицензия: CC BY-NC-SA 4.0

Гордо использует Google Translate

Первые три главы этой книги посвящены моделям, которые описывают системы, состоящие из компонентов и связей между ними. Например, в экологических пищевых сетях компонентами являются виды, а связи представляют собой отношения хищника и жертвы.

В данной главе я представлю библиотеку NetworkX, которая используется для создания и исследования таких моделей на языке Python. Мы начнём с модели Эрдеша-Реньи, имеющей ряд интересных математических свойств. В следующей главе мы рассмотрим более полезные модели, объясняющие реальные системы.

Код данной главы находится в файле chap02.ipynb в репозитории этой книги. Дополнительная информация о использовании кода содержится в главе (?).

2.1 Что такое граф?

Рисунок 2.1: Направленный граф, представляющий социальную сеть

В данном контексте граф представляет систему, содержащую дискретные взаимосвязанные элементы. Элементы представлены вершинами, а взаимосвязи — ребрами.Например, можно представить карту маршрутов, где каждый город является вершиной, а маршрут между двумя городами — ребром. Также можно представить социальную сеть, где каждый человек является вершиной, а если два человека друзья, то между ними есть ребро; в противном случае его нет.

У некоторых графов ребра имеют атрибуты, такие как длина, стоимость или вес. Например, в карте маршрутов длина ребра может представлять расстояние или время пути между двумя городами. В социальной сети могут быть различные типы ребер, чтобы показать разные виды отношений: друзья, деловые партнёры и так далее.

Ребра могут быть направленными или неориентированными в зависимости от того, являются ли они отношениями асимметричными или симметричными. В карте маршрутов вы можете использовать направленные ребра для представления односторонних дорог и неориентированные ребра для двухсторонних дорог. В некоторых социальных сетях, таких как Facebook, дружба симметрична: если А друг Б, то Б тоже друг А. Однако на Twitter "подписка" не является симметричной; если А подписался на Б, это не значит, что Б подписался на А. Поэтому вы можете использовать неориентированные ребра для представления сети Facebook и направленные ребра для сети Twitter. Графы имеют интересные математические свойства, и существует раздел математики, называемый теорией графов, который изучает их.Графы также полезны, так как множество реальных задач можно решить с помощью алгоритмов работы с графами. Например, алгоритм Дейкстры для поиска кратчайшего пути — это эффективный способ найти минимальное расстояние от одной вершины до всех остальных в графе. Путь представляет собой последовательность вершин между двумя узлами, соединённых ребрами.

Узлы графа обычно изображаются круглыми или прямоугольными фигурами, а ребра — прямыми линиями. В примере выше направленного графа узлы могут представлять трёх человек, взаимодействующих друг с другом через Twitter. Толстая часть линий указывает направление ребёр. В этом случае Алиса и Боб следят за каждым другим, а также за Чаком, но Чак не следит ни за кем.

Ниже приведён неориентированный граф, показывающий четыре города на восточном побережье США; метки на ребрах представляют время вождения в часах. В этом примере положение узлов приближённо соответствует географическому расположению городов, однако обычно расположение графа является произвольным.

2.2 NetworkX

Рисунок 2.2: Граф, представляющий города и автомагистрали

Для представления графа мы будем использовать библиотеку Python под названием NetworkX, которая является наиболее часто используемой сетевой библиотекой. Вы можете прочитать больше информации на https://networkx.github.io/, но мы объясним её позже.Мы можем создать ориентированный граф, импортировав NetworkX и экземпляр nx.DiGraph:

import networkx as nx
G = nx.DiGraph()

Обычно NetworkX импортируется как nx. В данный момент G является объектом типа DiGraph, не содержащим узлов и ребер. Мы можем добавить узлы с помощью метода add_node:

G.add_node('Алиса')
G.add_node('Боб')
G.add_node('Чак')

Теперь мы можем получить список узлов с помощью метода nodes:

>>> G.nodes()
['Алиса', 'Боб', 'Чак']

Добавление ребер происходит аналогичным образом:

G.add_edge('Алиса', 'Боб')
G.add_edge('Алиса', 'Чак')
G.add_edge('Боб', 'Алиса')
G.add_edge('Боб', 'Чак')

Мы можем получить список ребер с помощью метода edges:

>>> G.edges()
[('Алиса', 'Боб'), ('Алиса', 'Чак'), 
 ('Боб', 'Алиса'), ('Боб', 'Чак')]

NetworkX предоставляет несколько функций для отрисовки графа; draw_circular располагает узлы в окружности и соединяет их ребрами:

nx.draw_circular(G,
                 node_color=COLORS[0],
                 node_size=2000,
                 with_labels=True)

Это код, который я использовал для создания графа. Опция with_labels позволяет помечать узлы; в следующем примере мы рассмотрим, как помечать ребра. Чтобы создать граф, мы начинаем с словаря, который отображает название каждого города в соответствующие координаты широты и долготы:

pos = dict(
    Альбани=(-74, 43),
    Бостон=(-71, 42),
    Нью_Йорк=(-74, 41),
    Филадельфия=(-75, 40)
)

Поскольку это неориентированный граф, я создаю экземпляр nx.Graph():```py

G = nx.Graph()

Затем я могу использовать `add_nodes_from`, чтобы пройтись по ключам `pos` и добавить их как вершины.

```py

G.add_nodes_from(pos)

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

time_between_cities = {
    ('Albany', 'Boston'): 3,
    ('Albany', 'New_York'): 4,
    ('Boston', 'New_York'): 4,
    ('New_York', 'Philadelphia'): 2
}

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

G.add_edges_from(time_between_cities)

Теперь вместо использования draw_circular, которое располагает вершины в круг, я использую draw, который принимает pos как второй аргумент:

nx.draw(G, pos,
        node_color=COLORS[1],
        node_shape='s',
        node_size=2500,
        with_labels=True)

pos — это словарь, который отображает каждый город на его координаты; draw использует его для определения положения вершин.

Чтобы добавить метки к связям, мы можем использовать draw_networkx_edge_labels:

nx.draw_networkx_edge_labels(G, pos,
                             edge_labels=time_between_cities)

time_between_cities — это словарь, который отображает каждую связь на время в пути между ними, где каждая связь представлена парой названий городов. Вот так я создаю граф.

В этих двух примерах вершины являются строками, но обычно они могут быть любым хэшируемым типом.

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

Один из более интересных — модель Эрдоша-Реньи, которую Пауль Эрдош и Алфред Реньи исследовали в 1960-х годах.

Характеристика графа Эрдоша-Реньи (ГЭР) заключается в двух параметрах: n — количество вершин, p — вероятность существования связи между любой парой вершин. Подробнее см. http://en.wikipedia.org/wiki/Erdos-Renyi_model.

Эрдош и Реньи изучили свойства этих случайных графов; одним из удивительных результатов было то, что при добавлении случайных связей свойства случайного графа внезапно меняются. Показать такую трансформацию можно через свойство связности. Если существует путь от каждого узла до любого другого узла, то невзвешенный граф считается связным.

В случайных графах типа ER вероятность того, что граф будет связным, очень мала при малых значениях p, а при больших значениях p стремится к 1. Между этими состояниями существует быстрое изменение в определенной точке p, которая обозначается как p*.Эрдős и Ренье показали, что критическое значение равно p* = ln(n) / n, где n — количество узлов. Если p < p*, то случайный граф G(n, p) с большой вероятностью не будет связным, а если p > p*, то он с большой вероятностью будет связным.Для проверки этого утверждения мы будем разрабатывать алгоритмы для генерации случайных графов и проверки их связности.

2.4 Генерация графа

Сначала я создам полный граф, который представляет собой граф, где каждый узел соединён со всеми остальными.

Это генераторная функция, которая принимает список узлов и перебирает все возможные пары. Если вы не знакомы с генераторами, вам может потребоваться прочитать приложение перед тем, как продолжить.

def all_pairs(nodes):
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i > j:
                yield u, v

Вы можете использовать all_pairs для создания полного графа.

def make_complete_graph(n):
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(all_pairs(nodes))
    return G

Функция make_complete_graph принимает число узлов n и возвращает новый граф Graph, содержащий n узлов, между которыми есть ребра.

Ниже приведён пример кода, создающий полный граф с OnClickListener 10 узлами и выводящий его.

complete = make_complete_graph(10)
nx.draw_circular(complete,
                 node_color=COLORS[2],
                 node_size=1000,
                 with_labels=True)

Граф показывает результат. В скором времени мы модифицируем этот код для генерации графов ER, но прежде чем это сделать, мы разработаем функцию для проверки связности графа.

2.5 Связный граф

Если существует путь от каждого узла до любого другого узла, то граф называется связным. Подробнее см. http://en.wikipedia.org/wiki/Connectivity_(graph_theory).Для многих приложений, использующих графы, проверка связности является важной задачей. К счастью, существует простой алгоритм для её выполнения.

Можно начать с любого узла и проверить, можно ли достичь всех других узлов. Если можно достичь узла v, то можно также достичь любого соседнего узла v, который связан с ним ребром. Класс Graph предоставляет метод с названием neighbors, который возвращает список соседних узлов для данного узла. Например, в полностью созданном графе из предыдущего раздела:

>>> complete.neighbors(0)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Предположим, что мы начинаем с узла s. Мы можем пометить s как "посещённый", а затем помечаем его соседей. Затем мы помечаем соседей этих соседей и так далее до тех пор, пока больше нельзя достичь никаких узлов. Если все узлы были посещены, то граф является связным.

Это выглядит следующим образом на Python:

def достижимые_узлы(G, начальный_узел):
    посещенные = set()
    стек = [начальный_узел]
    while стек:
        узел = стек.pop()
        if узел not in посещенные:
            посещенные.add(узел)
            стек.extend(G.neighbors(узел))
    return посещенные

Функция достижимые_узлы принимает объект Graph и начальный узел начальный_узел, и возвращает множество всех узлов, доступных от начального_узла.Начально, множество посещённых узлов пустое, и мы создаём список под названием stack, чтобы отслеживать узлы, которые мы нашли, но ещё не обработали. В начале, стек содержит только один узел — start_node.Теперь, каждый раз, когда мы проходим через цикл, мы:

• Удаляем узел из стека.
• Если узел уже находится в посещенных, мы возвращаемся к шагу 1.
• В противном случае, мы добавляем узел в посещенные, а также добавляем его соседей в стек.

Когда стек становится пустым, нам больше нельзя достичь никаких узлов, поэтому мы завершаем цикл и возвращаем результат.

Например, мы можем найти все узлы, доступные от узла 0 в полностью созданном графе:

>>> достижимые_узлы(complete, 0)
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Начально, стек содержит узел 0, а посещенные — пустое множество. В первый проход цикла, узел 0 добавляется в посещенные, а все остальные узлы добавляются в стек (так как они являются соседями узла 0).

На втором проходе цикла, pop возвращает последний элемент стека, то есть узел 9. Таким образом, узел 9 добавляется в посещенные, а его соседи добавляются в стек.

Обратите внимание, что тот же узел может появиться несколько раз в стеке; фактически, узел с k соседними узлами будет добавлен в стек k раз. Позже мы будем искать способы сделать этот алгоритм более эффективным.

Мы можем использовать достижимые_узлы для написания функции is_connected:

def is_connected(G):
    начальный_узел = next(G.nodes_iter())
    достижимые = достижимые_узлы(G, начальный_узел)
    return len(достижимые) == len(G)
```Функция `is_connected` выбирает начальный узел, вызывая `nodes_iter`, которая возвращает итератор объекта, а затем передаёт результат в `next`, чтобы вернуть первый узел. `reachable` получает набор узлов, которые могут быть достигнуты от `start`. Если размер этого множества равен размеру графа, это означает, что мы можем получить доступ ко всем узлам, то есть этот граф является связным.

Полностью связный граф является связным, что неудивительно:

```py
>>> is_connected(complete)
True

В следующей секции мы будем генерировать графы ER и проверять, являются ли они связными.

2.6 Генерация графов ER

Рисунок 2.4: Граф ER, n=10, p=0.3

Граф ER G(n, p) состоит из n узлов, каждая пара которых соединена ребром с вероятностью p. Генерация графа ER аналогична генерации полного графа.

Ниже приведён генератор, который перебирает все возможные пары узлов и использует вспомогательную функцию flip, чтобы выбрать, какие пары должны быть добавлены в граф:

def random_pairs(nodes, p):
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i > j and flip(p):
                yield u, v

Функция flip возвращает True с вероятностью p и False с вероятностью 1 - p.

from numpy.random import random

def flip(p):
    return random() < p

Наконец, функция make_random_graph создаёт и возвращает граф ER G(n, p).

def make_random_graph(n, p):
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(random_pairs(nodes, p))
    return G
```Функция `make_random_graph` почти так же работает как `make_complete_graph`, единственное отличие заключается в использовании `random_pairs` вместо `all_pairs`.

Вот пример при `p=0.3`:

```py
random_graph = make_random_graph(10, 0.3)

Рисунок 2.5 показывает результат. Этот граф является связным; фактически, большинство графов ER при n=10 и p=0.3 являются связными. В следующей секции мы рассмотрим, сколько именно.

2.7 Вероятность связности

Рисунок 2.5: Вероятность связности, n=10, p — диапазон значений. Вертикальная линия показывает прогнозируемое критическое значение.

Рисунок 2.6: Вероятность связности, n — несколько значений, p — диапазон значений.

Для заданных значений n и p нам интересно узнать вероятность того, что граф G(n, p) будет связным. Мы можем оценить её, сгенерировав большое количество случайных графов. Вот как это делается:

def prob_connected(n, p, iters=100):
    count = 0
    for i in range(iters):
        random_graph = make_random_graph(n, p)
        if is_connected(random_graph):
            count += 1
    return count / iters

Параметр iters представляет собой количество сгенерированных случайных графов. Чем больше мы увеличиваем iters, тем более точной становится наша оценка вероятности.```py

prob_connected(10, 0.3, iters=10000) 0.6454 ```Из 10000 графов ER с этими параметрами 6498 являются связными, поэтому мы оцениваем, что около 65% из них являются связными. Таким образом, значение 0.3 близко к критическому значению, при котором вероятность соединённости переходит от значения, близкого к нулю, к значению, близкому к единице. По данным Эрдоша и Реньи, p* = ln(n) / n = 0.23.Мы можем более подробно исследовать переход, если будем оценивать вероятность соединённости для последовательности значений `p`:

import numpy as np

n = 10
ps = np.logspace(-2.5, 0, 11)
ys = [prob_connected(n, p) for p in ps]

Это первый пример использования NumPy в этом руководстве. В соответствии с традицией, я импортировал NumPy как np. Функция logspace возвращает массив из 11 элементов, начиная с 10 ** -2.5 до 10 ** 0 = 1, равномерно распределённых по логарифмической шкале.

Для вычисления y я использую списковое включение, чтобы пройтись по элементам ps и рассчитать вероятность соединённости случайного графа для каждого значения p.

График (не указан) показывает результаты, где вертикальная линия представляет собой p*. Переход от 0 до 1 происходит рядом с прогнозируемым критическим значением. На логарифмической шкале этот переход примерно симметричен.

Для больших значений n график (не указан) демонстрирует аналогичные результаты. При увеличении n критическое значение становится всё меньше, а переход становится всё более резким.

Эти эксперименты согласуются с теоремами Эрдоша и Реньи, представленными в их статьях.

2.8 Анализ алгоритмов графовВ этой главе я представил алгоритм проверки связности графа; в следующих главах мы еще больше встретимся с алгоритмами работы с графами. Мы будем анализировать производительность этих алгоритмов и понимать, как время выполнения зависит от размера графа.Если вы ещё не знакомы с анализом алгоритмов, вам следует прочитать приложение 1 перед продолжением.

Уровень роста алгоритмов графов обычно выражается через количество вершин n и количество ребёр m.

Как пример, давайте проанализируем алгоритм reachable_nodes из предыдущего раздела:

def reachable_nodes(G, start):
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in seen:
            seen.add(node)
            stack.extend(G.neighbors(node))
    return seen

Каждый раз, когда выполняется цикл, мы извлекаем узел из стека; по умолчанию метод pop удаляет и возвращает последний элемент списка, что является операцией постоянного времени.

Затем мы проверяем, был ли узел уже посещён; это множество, так что проверка принадлежности является операцией постоянного времени.

Если узел ещё не был посещён, добавление его является операцией постоянного времени, затем соседи добавляются в стек, что является операцией линейной сложности относительно количества соседей.

Чтобы использовать n и m для представления времени выполнения, мы можем сложить общее количество добавлений каждого узла в seen и stack.

Каждый узел добавляется всего один раз, поэтому общее количество добавлений равно n. ```Однако узлы могут быть добавлены несколько раз в стек, что зависит от того, сколько у них соседей. Если у узла есть k соседей, то он будет добавлен в стек `k` раз. Разумеется, если у него есть `k` соседей, это значит, что у него есть `k` ребер.Поэтому общее количество добавлений в стек равно удвоенному количеству ребер `m`, поскольку мы рассматриваем каждое ребро дважды.

Следовательно, уровень роста этой функции равен O(n + m), и мы можем сказать, что время выполнения пропорционально большему из n или m.

Если нам известна связь между n и m, мы можем упростить этот выражение. Например, в полной графе количество ребер равно n(n - 1) / 2, что принадлежит к O(n^2). Поэтому для полного графа reachable_nodes является квадратичной функцией относительно n.

2.9 Упражнения

Код текущего раздела находится в файле chap02.ipynb, который является Jupyter-блокнотом в репозитории книги. Дополнительная информация о том, как использовать этот код, представлена в разделе (?).

Упражнение 1: Запустите chap02.ipynb и запустите код. В блокноте встроены простые упражнения, которые вы можете попробовать.

Упражнение 2: Мы уже проанализировали производительность функции reachable_nodes и классифицировали её как O(n + m), где n — число вершин, а m — число ребёр. Продолжайте анализ: какой уровень роста имеет функция is_connected?

def is_connected(G):
    start = next(G.nodes_iter())
    reachable = reachable_nodes(G, start)
    return len(reachable) == len(G)

Упражнение 3: При реализации функции reachable_nodes вы могли заметить низкую эффективность, так как проверка того, были ли соседние вершины ранее посещены, происходит после добавления всех соседних вершин в стек. Напишите версию этой функции, которая будет проверять соседние вершины перед тем, как добавить их в стек. Изменяет ли эта "оптимизация" уровень роста? Быстрее ли станет функция?

Примечание переводчика: при удалении вершины она добавляется в seen, а при переборе соседних вершин проверяется, была ли она уже посещена.

Упражнение 4:

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

Другое определение представляет собой G(n, m), которое также имеет два параметра: число вершин n и число ребер m. В этом случае количество ребер фиксировано, но их расположение случайно.Используйте этот альтернативный определённый метод, чтобы повторить эксперименты данной главы. Вот несколько рекомендаций по этому поводу:

1. Напишите функцию с именем m_pairs, которая принимает список вершин и количество ребёр m и возвращает случайно выбранные m пар ребёр. Одним из простых способов является создание списка всех возможных ребёр и использование random.sample.

Используйте этот альтернативный определенный метод, чтобы повторить эксперименты данной главы. Вот несколько рекомендаций по этому поводу:

1. Напишите функцию с именем `m_pairs`, которая принимает список вершин и количество ребер `m` и возвращает случайно выбранные `m` пар ребер. Одним из простых способов является создание списка всех возможных ребер и использования `random.sample`.
```2. Напишите функцию с именем `make_m_graph`, которая принимает `n` и `m` и возвращает случайный граф с `n` вершинами и `m` ребрами.

3. Создайте версию `prob_connected`, используя `make_m_graph` вместо `make_random_graph`.

4. Вычислите вероятность соединения для последовательности значений `m`.

Каковы результаты этого эксперимента по сравнению с результатами первой категории ER-графа?