3. Маленькие миры графов

Оригинал: Глава 3 Маленькие миры графов

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

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

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

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

В этой главе я представляю знаменитый эксперимент Стэнли Милграмма (Stanley Milgram) по малым мирам, который был первой научной демонстрацией этого свойства в настоящих социальных сетях. Затем мы рассмотрим модель малого мира графа — графы Ватса-Строгаза. Я повторю эксперимент, проведённый Ватсом и Строгазом, и объясню, что он нам показывает.

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

Код данной главы находится в файле chap03.ipynb в репозитории книги. Подробнее о использовании кода см. в главе (?).

3.1 Стэнли МилгрэмСтэнли Милгрэм (Stanley Milgram) был американским социальным психологом, проводившим два самых известных эксперимента в области социальных наук: эксперимент Милгрэма, исследующий послушание людей перед авторитетом (https://en.wikipedia.org/wiki/Milgram_experiment) и эксперимент малых миров, исследующий структуру социальных сетей (https://en.wikipedia.org/wiki/Small_world_phenomenon).В эксперименте малых миров Милгрэма пакеты были отправлены нескольким случайно выбранным лицам в Уичито, штат Канзас, содержащим инструкцию передать приложенное письмо цели, указанной по имени и профессии. Ответчики были информированы, что они могут прямым образом отправить письмо цели только если они лично знают цель; в противном случае они должны были следовать указанию и отправить письмо вместе с тем же указанием другому человеку, которого считали более вероятным знакомым цели.

Многие письма никогда не достигали своей цели, но среди тех, кто дошел до конца, средняя длина пути составила около 6. Этот результат подтвердил ранее наблюдаемую (и догадывающуюся) идею, что обычно любые две персоны в социальной сети разделены "шестью степенями".Дополнительно, средний путь длился примерно шесть шагов. Этот результат подтверждает ранее сделанные наблюдения (и догадки), что обычно любые две персоны в социальной сети разделены "шестью степенями". Этот вывод был удивителен, так как большинство людей ожидают локализацию социальных сетей — люди склонны находиться ближе к своим друзьям — и в графе с локальными связями длина пути обычно пропорциональна географическому расстоянию. Например, большинство моих друзей живут недалеко от меня, поэтому я предположил, что среднее расстояние между узлами в социальной сети составляет около 50 миль. Вичита находится примерно в 1600 милях от Бостона, поэтому если письма Милгрэма прошли через типичный социальный граф, они должны были сделать 32 перехода вместо шести.### 3.2 Уоттс и Строгац

В 1998 году Дункан Уоттс и Стивен Строгац опубликовали статью "Коллективная динамика 'малых миров'" ("Collective Dynamics of 'Small-World' Networks") в журнале Nature, где была представлена модель малого мира. Вы можете скачать её по адресу http://www.nature.com/nature/journal/v393/n6684/abs/393440a0.html.

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

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

Длина пути является мерой среднего расстояния между двумя узлами, которая соответствует степени разделённости в социальной сети.Уоттс и Строганов показывают, что регулярный граф имеет высокий коэффициент кластеризации и длинное среднее расстояние, тогда как граф случайной структуры обычно имеет низкий коэффициент кластеризации и короткое среднее расстояние. Поэтому ни один из этих графов не является хорошей моделью социальной сети; должна быть комбинация высокого коэффициента кластеризации и короткого среднего расстояния.Их цель заключается в создании модели генерации социальной сети. Генерационная модель объясняет явление путём моделирования процесса его создания или возникновения. Уоттс и Строгац предложили процесс построения графа малого мира:

1. Начать с регулярного графа, содержащего n узлов, каждый из которых соединён с k соседними узлами.

2. Выбрать подмножество ребёр и заменить их случайными ребрами, чтобы "пересоединить".

Вероятность пересоединения ребра является параметром p, который контролирует степень случайности графа. Когда p = 0, граф является регулярным; когда p = 1, он становится случайным. Уоттс и Строгац обнаружили, что меньшие значения p создают графы с высокой коалесцией, такие как регулярные графы, а также графы с короткими путями, аналогичные случайным графам.

В этой главе я буду воспроизводить эксперименты Уоттса и Строгаца следующим образом:

• Мы начнём с построения кольцевого решётчатого графа (кольцевого латтиса), который является типом регулярного графа.
• Затем мы выполним перезапроску, как это сделали Уоттс и Строгац.
• Мы напишем функцию для измерения коалесции и будем использовать функции NetworkX для вычисления длин пути.
• Затем мы рассчитаем коалесцию и длину пути для значений p в указанном диапазоне.
• В конце я представлю эффективный алгоритм для вычисления кратчайшего пути, известный как алгоритм Дейкстры.## 3.3 Кольцевой латтис

Рисунок 3.1 Кольцевой латтис при n=10, k=4.

Регулярный граф — это граф, где каждый узел имеет одинаковое количество соседних узлов; это число также называется степенью узла. Кольцевой латтис представляет собой тип регулярного графа, используемый Watts и Strogatz в качестве основы модели. В кольцевом латтисе с n узлами узлы могут быть расположены в виде круга, причём каждый узел соединён с k ближайшими соседними узлами.

Например, кольцевой латтис с n = 3 и k = 2 будет иметь следующие ребра: (0, 1), (1, 2), (2, 0). Обратите внимание, что ребро начинается от узла с наибольшим номером и "обходит" обратно к нулевому узлу.

Общее правило для перечисления ребер может быть таким:

def adjacent_edges(nodes, half_k):
    n = len(nodes)
    for i, u in enumerate(nodes):
        for j in range(i + 1, i + half_k + 1):
            v = nodes[j % n]
            yield u, v

Функция adjacent_edges принимает список узлов и параметр half_k, который равен половине значения k. Это генератор, который производит одно ребро за раз. Он использует операцию взятия остатка % для перехода от узла с наибольшим номером к узлу с наименьшим номером.

Можно протестировать её так:

>>> nodes = range(3)
>>> for edge in adjacent_edges(nodes, 1):
...     print(edge)
(0, 1)
(1, 2)
(2, 0)

Теперь можно использовать adjacent_edges для создания кольцевого латтиса.```py def сделать_кольцевой_латтис(n, k): G = nx.Graph() узлы = range(n) G.add_nodes_from(узлы) G.add_edges_from(смежные_ребра(узлы, k // 2)) return G

Обратите внимание, что `сделать_кольцевой_латтис` использует целочисленное деление для вычисления `полук`, поэтому если `k` — нечётное число, то значение `полук` округляется до нижней границы, что приведёт к графу с степенью `k - 1`. Это может быть не тем, что нам нужно, но пока достаточно.

Можно протестировать функцию так:

```py
латтис = сделать_кольцевой_латтис(10, 4)

Рисунок 3.2 показывает результат.

3.4 Графы WS!

Рисунок 3.2 График модели Watts-Strogatz (WS), n=20, k=4, p=0 (слева), p=0.2 (в центре), p=1 (справа).

Для создания графиков модели Watts-Strogatz (WS) мы начинаем с кольцевой решётки и "перераспределяем" некоторые ребра. В своей работе Watts и Strogatz рассматривают ребра в определённом порядке и перераспределяют каждое ребро с вероятностью p. Если ребро перераспределено, то его первая вершина остаётся неизменной, а вторая выбирается случайным образом. Они не допускают самопетли и параллельные связи; другими словами, вершины не могут иметь связь с собой, и между двумя вершинами не может быть более одной связи.

Это реализация моего процесса.

def rewire(G, p):
    nodes = set(G.nodes())
    for edge in G.edges():
        if flip(p):
            u, v = edge
            choices = nodes - {u} - set(G[u])
            new_v = choice(tuple(choices))
            G.remove_edge(u, v)
            G.add_edge(u, new_v)
```Параметр `p` представляет вероятность перераспределения ребра. Цикл `for` перебирает все ребра и использует функцию `flip`, которая возвращает `True` с вероятностью `p`.

Если мы перераспределим ребро от вершины `u` до вершины `v`, нам потребуется выбрать новую вершину `new_v`, чтобы заменить `v`. Для вычисления возможных вариантов выбора мы начинаем с множества всех вершин, удаляем `u` и её соседей, что позволяет избежать самопетлей и параллельных связей.

Затем мы выбираем `new_v` из доступных вариантов, удаляем существующее ребро `(u, v)` и добавляем новое ребро `(u, new_v)`.

Кроме того, выражение `G[u]` возвращает словарь, ключи которого представляют соседние вершины `u`. В данном случае это быстрее, чем использование `G.neighbors()`.

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

Рисунок (3.2) показывает графики модели WS при значениях `n = 20`, `k = 4` и различных значениях `p`. Когда `p = 0`, этот график является кольцевой решёткой. При `p = 1` он становится полностью случайным. Мы заметим, что интересные вещи происходят между этими крайними случаями.


## 3.5 КластеризацияСледующий шаг — вычисление коэффициента кластеризации, который количественно характеризует склонность вершин образовывать кластеры. Кластер — это группа полностью соединённых вершин; другими словами, между всеми парами вершин внутри группы существует ребро.Предположим, что конкретная вершина `u` имеет `k` соседних вершин. Если все соседние вершины соединены друг с другом, будет `k(k-1)/2` ребра. Соотношение фактически существующих ребер к максимальному возможному количеству называется локальным коэффициентом кластеризации вершины `u`, обозначаемым как `C_u`. Он называется "коэффициентом", так как всегда находится в диапазоне от 0 до 1. Если мы вычислим среднее значение `C_u` для всех узлов, то получим "средний коэффициент группировки сети", который обозначается как `C`.

Это функция для его вычисления.

```py
def node_clustering(G, u):
    neighbors = G[u]
    k = len(neighbors)
    if k < 2:
        return 0

    total = k * (k - 1) / 2
    exist = 0
    for v, w in all_pairs(neighbors):
        if G.has_edge(v, w):
            exist += 1
    return exist / total

Аналогично, я использую G[u], которая возвращает словарь, ключами которого являются соседние узлы. Если количество соседних узлов меньше двух, коэффициент группировки не определен, но для удобства функция node_clustering возвращает 0.

Иначе, мы вычисляем возможное количество ребер между соседними узлами, total, а затем вычисляем фактическое количество существующих ребер. Результат представляет собой долю всех существующих ребер.

Можно протестировать функцию следующим образом:

>>> lattice = make_ring_lattice(10, 4)
>>> node_clustering(lattice, 1)
0.5

В кольцевой решетке с k=4, локальный коэффициент группировки каждого узла равен 0.5 (если вам это кажется неверным, вы можете взглянуть на диаграмму).Теперь можно вычислить средний коэффициент группировки сети следующим образом:

def clustering_coefficient(G):
    cc = np.mean([node_clustering(G, node) for node in G])
    return cc

np.mean — это функция NumPy, которая вычисляет среднее значение элементов списка или массива.

Затем можно протестировать следующим образом:

>>> clustering_coefficient(lattice)
0.5

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

3.6 Кратчайшее расстояние между узлами

Следующий шаг — вычисление характерной длины пути L, которая является средней длиной кратчайших путей между всеми парами узлов. Для этого вычисления я начну с использования функции shortest_path_length из библиотеки NetworkX, чтобы воспроизвести эксперимент Ваттса и Строгазца, а затем объясню её работу.

Эта функция принимает граф и возвращает список длин кратчайших путей, один для каждой пары узлов.

def path_lengths(G):
    length_map = nx.shortest_path_length(G)
    lengths = [length_map[u][v] for u, v in all_pairs(G)]
    return lengths

Результат функции nx.shortest_path_length — это вложенный словарь. Внешний словарь представляет собой отображение каждого узла u внутреннего словаря, а внутренний словарь представляет собой отображение каждого узла v на длину кратчайшего пути от u до v.Используя списки длин, полученные из функции path_lengths, можно вычислить L следующим образом:

def path_length_characteristic(G):
    return np.mean(path_lengths(G))

И мы можем использовать маленький циклический граф для проверки его.

>>> lattice = make_circular_lattice(3, 2)
>>> path_length_characteristic(lattice)
1.0

В этом примере все три узла соединены друг с другом, поэтому средняя длина пути составляет 1.

3.7 Эксперимент WS

Рисунок 3.3: Групповой коэффициент кластеризации C и характерная длина пути L для графа WS, где n=1000, k=10, а p — это диапазон значений.

Теперь мы готовы воспроизвести эксперимент WS, который показывает, что для различных значений p графы WS имеют высокий коэффициент кластеризации, как регулярные графы, и короткие длины путей, как случайные графы.

Я начну с функции run_one_graph, которая принимает n, k и p; она создает граф WS с указанными параметрами, вычисляет среднюю длину пути mpl и коэффициент кластеризации cc:

def run_one_graph(n, k, p):
    ws = make_WS_graph(n, k, p)
    mpl = path_length_characteristic(ws)
    cc = clustering_coefficient(ws)
    print(mpl, cc)
    return mpl, cc

Watts и Strogatz провели эксперименты с n = 1000 и k = 10. При этих параметрах выполнение run_one_graph занимает около секунды на моем компьютере; большую часть времени занимает вычисление средней длины пути.Теперь нам нужно рассчитать эти значения для каждого значения p в диапазоне. Я снова использую функцию NumPy logspace для расчета ps:

ps = np.logspace(-4, 0, 9)

Для каждого значения p я генерирую 3 случайных графа и буду считать среднее значение результатов. Вот функция для запуска эксперимента:

def run_experiment(ps, n=1000, k=10, iters=3):
    res = {}
    for p in ps:
        print(p)
        res[p] = []
        for _ in range(iters):
            res[p].append(run_one_graph(n, k, p))
    return res

Результат представляет собой словарь, который отображает каждое значение p в список пар (mpl, cc).

Последний шаг — агрегация результатов:

L = []
C = []
for p, t in sorted(res.items()):
    mpls, ccs = zip(*t)
    mpl = np.mean(list(mpls))
    cc = np.mean(list(ccs))
    L.append(mpl)
    C.append(cc)

Каждый раз при прохождении цикла мы получаем значение p и список пар (mpl, cc). Мы используем zip для получения двух списков, mpls и ccs, затем вычисляем их средние значения и добавляем их в L и C, которые являются списками длин пути и коэффициентов кластеризации соответственно.

Чтобы нарисовать L и C на одном графике, мы нормируем их делением на первый элемент. График показывает результаты. По мере увеличения p средняя длина пути быстро снижается, поскольку даже небольшое количество случайных перелинков создает маршруты между различными частями графа, которые находятся далеко друг от друга в сетке. С другой стороны, удаление локальных соединений медленно снижает коэффициент кластеризации.

Поэтому в определённом диапазоне WS-сети обладают характеристиками малого мира — высоким коэффициентом кластеризации и короткой длиной пути.

Это именно то, что привело Watts и Strogatz к созданию модели WS, чтобы продемонстрировать реальные сети, обладающие свойствами малого мира.## 3.8 Как это объяснить?

Если бы вы спросили меня, почему орбиты планет являются эллиптическими, я начал бы с моделирования одной планеты и одного звезды; я нашёл бы закон всемирного тяготения на http://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation и использовал бы его для записи дифференциального уравнения движения планеты. Затем я расширил бы уравнение орбиты, либо просто нашёл бы его на http://en.wikipedia.org/wiki/Orbit_equation. После небольших алгебраических преобразований я смог бы установить условия, при которых образуется эллиптическая орбита. Затем я бы показал, что объекты, рассматриваемые как планеты, удовлетворяют этим условиям.

Люди, или по крайней мере учёные, обычно довольны таким объяснением. Одной из причин этого является то, что гипотезы и аппроксимации в модели кажутся разумными. Планеты и звёзды не являются истинными материальными точками, но расстояние между ними так велико, что их реальные размеры можно игнорировать. Планеты в одной солнечной системе могут влиять друг на друга, но эффекты обычно малы. Мы также игнорируем влияние относительности, снова предполагая, что они малы.Это также потому, что это основано на уравнениях. Мы можем записать уравнение орбиты в замкнутой форме, что позволяет нам эффективно вычислять орбиты. Это также означает, что мы можем выводить общие выражения для скорости орбиты, периода орбиты и других величин.Наконец, я считаю, что это связано с тем, что это имеет форму математического доказательства. Оно начинается с набора аксиом и выводит результаты через логику и анализ. Однако важно помнить, что доказательство относится к модели, а не к реальному миру. То есть, мы можем доказать, что идеальная модель планеты создает эллиптическую орбиту, но мы не можем доказать, что эта модель связана с реальными планетами (то есть, она этого не делает).

• Чем эти модели полезны? Они предсказывают или объясняют, или оба?
• Эта модель менее удовлетворительна, чем традиционные модели? Почему?
• Как мы должны характеризовать различия между этими моделями и традиционными? Они отличаются типом или степенью?

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

3.9 Широтное первенство поиска

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

В разделе (?), я представил reachable_nodes, который находит все узлы, доступные от данного начального узла:```py 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

Я тогда не сказал этого, но он выполняет поиск в глубину (DFS). Теперь мы будем модифицировать его, чтобы он выполнял поиск в ширину (BFS).

Чтобы понять различие, вообразите, что вы исследуете замок. Вы начинаете в одной комнате, имеющей три двери, помеченных A, B и C. Вы открываете дверь C и находите другую комнату, двери которой помечены D, E и F.

Какую следующую дверь вы откроете? Если вы хотите рискнуть, вы можете захотеть погрузиться глубже в замок, выбрав D, E или F. Это поиск в глубину.

Но если вы хотите более систематический подход, вы можете вернуться и исследовать A и B перед тем, как исследовать D, E и F, что будет являться поиском в ширину.

В `reachable_nodes` мы используем `list.pop` для выбора следующего узла для "исследования". По умолчанию, `pop` возвращает последний элемент списка, который был добавлен последним. В этом примере это дверь F.

Если бы мы хотели выполнить BFS, самым простым решением было бы использовать первый элемент из стека:

```py
node = stack.pop(0)

Это работает, но очень медленно. В Python удаление первого элемента списка требует линейного времени относительно длины списка. В худшем случае, когда длина стека составляет O(n), это делает реализацию BFS со сложностью O(nm) намного менее эффективной по сравнению с O(n + m). ```Мы можем использовать двустороннюю очередь (также известную как deque) для решения этой проблемы. Одним из важнейших свойств deque является возможность добавления и удаления элементов как с начала, так и с конца. Чтобы узнать, как это реализуется, обратитесь к https://en.wikipedia.org/wiki/Double-ended_queue. Python предоставляет deque в модуле `collections`, поэтому мы можем импортировать его следующим образом:

from collections import deque

Можно использовать его для написания эффективного BFS:

def reachable_nodes_bfs(G, start):
    seen = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in seen:
            seen.add(node)
            queue.extend(G.neighbors(node))
    return seen

Разница заключается в том, что:

• Я заменил список с названием stack на deque с названием queue.
• Я заменил pop на popleft, который удаляет и возвращает самый левый элемент очереди, то есть первый добавленный элемент.

Этот вариант снова имеет сложность O(n + m). Теперь мы готовы найти самые короткие пути.

3.10 (Упрощенный) Алгоритм Дейкстры

Эдсгер В. Дейкстра был голландским компьютерным ученым, создателем эффективного алгоритма для нахождения кратчайшего пути (см. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). Он также придумал семафор — это структура данных, используемая для координации программ, которые взаимодействуют друг с другом (см. http://en.wikipedia.org/wiki/Semaphore_(programming) и Дауни, "Маленькая книга о семафорах".Как автор серии научных работ по информатике, Дейкстра известен как прославленный (или злополучный) человек. Некоторые работы, такие как "Против использования оператора goto" (A Case Against the GO TO Statement), оказали значительное влияние на практику программирования. Другие, такие как "О жестокости настоящего преподавания вычислительной науки" (On the Cruelty of Really Teaching Computing Science), были забавными, но малоэффективными.

Алгоритм Дейкстры решает задачу "кратчайшего пути от одного источника", то есть он находит минимальное расстояние от данного "источника" до каждого другого связанного узла графа.

Для начала рассмотрим упрощённую версию этого алгоритма, где все ребра имеют одинаковую длину. Более общая версия применима к любому набору невригативных длин ребер.

Упрощённая версия аналогична BFS из первой части, за исключением того, что вместо множества seen используется словарь dist, который связывает каждый узел с расстоянием до источника:

def shortest_path_dijkstra(G, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        new_dist = dist[node] + 1

        neighbors = set(G[node]) - set(dist)
        for n in neighbors:
            dist[n] = new_dist

Это как это работает:+ Начально, очередь содержит один элемент start, а dist отображает расстояние от start до 0 (это расстояние от start до самого себя).

• В каждом цикле мы используем popleft, чтобы получить узел в том порядке, в котором они были добавлены в очередь.
• Далее мы находим всех соседей этого узла, которые ещё не присутствуют в dist.
• Поскольку расстояние от начальной точки до текущего узла равно dist[node], то расстояние до любого непосещённого соседа будет dist[node] + 1.
• Для каждого соседа мы добавляем запись в dist и добавляем соседа обратно в очередь.Этот алгоритм работает только при использовании BFS вместо DFS. Почему?

В первом цикле узел является началом, а новое_расстояние равно 1. Таким образом, соседи начала имеют расстояние 1 и попадают в очередь.

Когда мы обрабатываем соседей начала, все их соседи имеют расстояние 2. Мы знаем, что ни один из них не имеет расстояния 1, так как если бы это было так, мы нашли бы их во время первой итерации.

Аналогично, когда мы обрабатываем узлы с расстоянием 2, мы устанавливаем расстояние их соседей в 3. Мы знаем, что ни один из них не имеет расстояний 1 или 2, потому что если бы это было так, мы нашли бы их во время предыдущих итераций.

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

Однако, этот аргумент становится верным только после того, как мы обработали все узлы с расстоянием 1 перед тем, как начать обрабатывать узлы с расстоянием 2, и так далее. Именно это делает BFS.

В упражнении в конце этой главы вы напишите версию алгоритма Дijkstra, используя DFS, чтобы увидеть, какие проблемы возникают.

3.11 Упражнения

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

В кольцевой решётке каждый узел имеет одинаковое количество соседей. Количество соседей называется степенью узла, а граф, где степень всех узлов одинакова, называется регулярным графом.Все кольцевые решётки являются регулярными, но не все регулярные графы являются кольцевыми решётками. В частности, если k — нечётное число, то невозможно создать кольцевую решётку, но можно создать регулярный граф.Напишите функцию make_regular_graph, которая принимает n и k и возвращает регулярный граф с n узлами, где каждый узел имеет k соседей. Если невозможно создать регулярный граф с данными значениями n и k, функция должна выбросить ValueError.

Упражнение 2: Моя реализация reachable_nodes_bfs эффективна, так как её сложность составляет O(n + m), но она создаёт значительные затраты, добавляя и удаляя узлы из очереди. Библиотека NetworkX предоставляет простую и быструю реализацию BFS, которую можно найти в репозитории NetworkX на GitHub по адресу https://github.com/networkx/networkx/blob/master/networkx/algorithms/components/connected.py. Вот отредактированная версия, которая возвращает набор узлов:

def _plain_bfs(G, source):
    seen = set()
    nextlevel = {source}
    while nextlevel:
        thislevel = nextlevel
        nextlevel = set()
        for v in thislevel:
            if v not in seen:
                seen.add(v)
                nextlevel.update(G[v])
    return seen

Сравните этот метод с reachable_nodes_bfs, чтобы узнать, какой из них работает быстрее. После этого попробуйте модифицировать этот метод, чтобы сделать более эффективной версию shortest_path_dijkstra.

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

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

def bfs(top_node, visit):
    """Поиск в ширину графа, начиная с узла top_node."""
    visited = set()
    queue = [top_node]
    while len(queue):
        curr_node = queue.pop(0)    # Выталкивание из очереди
        visit(curr_node)            # Посещение узла
        visited.add(curr_node)
```        # Добавление непосещённых и ещё не добавленных потомков в очередь
        queue.extend(c for c in curr_node.children 
                     if c not in visited and c not in queue)

Упражнение 4: В разделе (?) я указал, что алгоритм Дейкстры может работать только при использовании BFS. Напишите версию `shortest_path_dijkstra`, использующую DFS, и протестируйте её на примерах, чтобы выявить ошибки.

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

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

Чтобы ответить на этот вопрос, выберите вариант модели WS и повторите эксперимент. Возможно, стоит рассмотреть следующие варианты:

+   Начать не с обычного графа, а с другого графа с высокой кластеризацией. Например, можно расположить узлы случайным образом в двумерном пространстве и соединять каждый узел с его ближайшими `k` соседями.
+   Попробуйте различные виды переключения.

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

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

Алгоритм Дейкстры решает задачу "однопунктовых кратчайших путей", но для вычисления среднего пути графа нам требуется решение задачи "многопунктовых кратчайших путей".Конечно, один из способов — запустить алгоритм Дейкстры `n` раз, начиная с каждого узла. Для некоторых применений этого может быть достаточно, однако существуют более эффективные подходы. Найдите алгоритм для решения задачи многозвездной минимальной длины и реализуйте его. См. <https://en.wikipedia.org/wiki/Shortest_path_problem#All-pairs_shortest_paths>.

Сравните время выполнения с запуском алгоритма Дейкстры `n` раз. Какой алгоритм лучше теоретически? А практически? Какой алгоритм используется в NetworkX?

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