Часть IV - Основы сетевой теории
Наконец, наш путь в этой серии статей по теории графов ведет нас к сердцу развивающейся подотрасли теории графов: теории сетей.
Теория сетей - это применение принципов теории графов к изучению сложных динамических взаимодействующих систем
Он предоставляет методы для дальнейшего анализа структуры взаимодействующих агентов, когда предоставляется дополнительная релевантная информация. Приложения теории сетей, как указано в статьях, предшествующих этой статье (3), имеют далеко идущие последствия и не зависят от отрасли. Основы теории сетей - от информатики до электротехники, теории игр и анализа социальных сетей - предлагают мощную ментальную модель для улучшения нашего понимания современных систем.
Не портя слишком много будущих статей, возможно, имеет смысл дать краткий обзор типа проблем, для решения которых обычно используется теория сетей. Среди прочего, это несколько примеров классических задач теории сетей:
- Задача кратчайшего пути. Какой самый короткий (с точки зрения затрат) путь между любыми двумя узлами в графе?
- Сетевой поток - Достаточно ли пропускной способности направленного пути для переноса «потока», который он получает на каждом узле по пути?
- Проблема сопоставления - содержит ли граф пару или более совпадающих независимых наборов ребер?
- Анализ критического пути - Какой самый длинный путь зависимой природы в системе взаимозависимых действий?
Кратко - сети социальных сетей
Изучая сходства и различия основных социальных сетей с помощью принципов теории графов, мы можем углубить наше понимание и понимание этих повседневных сущностей. Давайте разберем структуру Medium и Facebook с помощью мини-графических представлений.
Середина
Как выглядит график, представляющий Medium (этот самый сайт)? Начните с зонирования отношений между пользователями. На Medium пользователь может следовать за другим пользователем, причем второй пользователь не обязательно следует за первым пользователем - это означает, что каждое ребро на графе Medium имеет направление. Таким образом, сеть Medium имеет форму ориентированного графа. Например, как показано ниже, я и мой друг Тони Старк можем подписаться на Джули Чжуо (безумно талантливый дизайнер продуктов в Facebook и плодовитый писатель на Medium, за которым я подписан на IRL); однако, поскольку ей неинтересно видеть то, что мы пишем, она не идет за нами в ответ - нет пути назад от Джули к Тони и мне. Наглядно это выражено в следующем примере:
Давайте теперь сравним вышеупомянутое представление Medium со скандальным «виноватым удовольствием» Big-Blue - Facebook. За исключением относительно недавней функции «подписки», пользователи Facebook должны быть друзьями, чтобы делиться доступом к контенту друг друга. Один пользователь Facebook просит второго пользователя Facebook стать друзьями . Однако, как только этот запрос будет принят, уже не имеет значения, кто и кому его отправил. Направленность больше не существует: оба пользователя будут видеть контент друг друга на своей временной шкале. Давайте продолжим наш пример влиятельной женщины Джули с двумя обычными пользователями - мной и Тони Старком. На Facebook очень вероятно, что Тони и я друзья; однако никто из нас не дружит с Джули:
Мы провели два мысленных эксперимента с основными социальными сетями в качестве упражнения, чтобы визуально понять их соответствующую графоподобную структуру. Давайте отправимся в захватывающий мир криптовалют, чтобы просмотреть еще два примера.
Кратко - криптовалюты
Теперь мы проанализируем еще одно современное чудо в виде графа: криптовалюты. Ниже, вместо того, чтобы обдумывать примеры, мы проанализируем буквально скриншоты поддерживающих сетей как для Bitcoin Lightning Network, так и для механизма консенсуса Tangle IOTA.
Сеть Lightning
На приведенном выше графике показан снимок экрана Lightning Network, p2p-уровня расчетов вне сети для Биткойн - одного из самых многообещающих решений масштабирования для мгновенных, почти бесплатных транзакций Биткойн. Lightning Network - это сеть, состоящая из узлов и платежных каналов (также называемых краями). Платежные каналы строго состоят из двух конечных узлов, которые, отправляя начальную сумму для открытия платежного канала, позволяют осуществлять чрезвычайно быстрые биткойн-транзакции между обоими соединяющимися узлами. Чтобы присоединиться к Lightning Network, узел должен иметь как минимум один платежный канал, открытый с другим узлом.
Узлы и платежные каналы, как было сказано выше, объединяются в классический пример графоподобной структуры. Когда платежный канал открыт, оба пользователя могут отправлять транзакции туда и обратно бесконечное количество раз - направление идет в обоих направлениях, что означает, что Lightning Network представляет собой неориентированный граф.
IOTA Клубок
С другой стороны, проект IOTA запустил своеобразный механизм консенсуса для своей версии блокчейна, основанный на DAG - Directed Acyclic Graph.
В Клубке, показанном выше, каждая транзакция представлена в виде вершины на графике. Когда новая транзакция присоединяется к Tangle, она выбирает две ранее неподтвержденные транзакции для подтверждения, добавляя к графу два новых ребра и узла. После подтверждения подтвержденные транзакции больше не могут быть подтверждены входящими неподтвержденными транзакциями; но недавно присоединившаяся неподтвержденная транзакция может и, скорее всего, будет подтверждена следующей входящей неподтвержденной транзакцией. Таким образом, в зависимости от того, были ли транзакции подтверждены или неподтверждены, это приводит к направленности внутри графа. Наблюдая выше, мы можем проверить это, заметив, что у большинства особых вершин около нижней части графа есть два ребра и вершины, свисающие с них (неподтвержденные транзакции, ожидающие подтверждения).
В заключение
Начиная с самых основ истории теории графов с «Семи мостов Кенигсберга», мы сейчас продвинулись до самого центра теории сетей. Тем не менее, это только стартовая площадка для реальных приложений теории графов и сетей - следующий шаг - поэкспериментировать со многими хорошо сделанными инструментами графической и сетевой визуализации и анализа, такими как те, которые указаны ниже:
изначально опубликовано
источники
