Введение в сетевую науку с NetworkX

Часть 1. Понимание математики, лежащей в основе теории графов

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

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

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

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

Математика, лежащая в основе графиков

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

Графы могут описывать многие реляционные системы. А именно, приведенный выше график может отображать воздушное движение между разными аэропортами:

Ссылки представляют собой прямые маршруты между аэропортами. А именно, чтобы попасть из Рима в Сан-Франциско, нужно обязательно проехать через Нью-Йорк.

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

Строки и столбцы представляют узлы: если элемент, соответствующий записи i, j, равен 1, это означает, что существует связь между узлами i и j , иначе элемент равен 0.

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

вы можете видеть, что из Сан-Франциско вы не можете вернуться в Рим. В этом случае соседняя матрица больше не симметрична:

Эти типы графиков называются ориентированными.

Независимо от его природы (направленный или неориентированный) граф размера N (то есть граф с N узлами) может иметь не более N (N-1) / 2 ребер. Граф с таким количеством ребер называется полным. С другой стороны, когда количество ребер E приблизительно равно N ^ a (с a ‹2), граф называется разреженным.

Я уже упоминал об особенностях размера графа: это количество узлов системы. Однако это не единственная метрика, которую мы можем использовать для описания нашего графика. Мы можем сгруппировать все эти показатели по трем категориям:

метрики расстояния
метрики центральности
статистические свойства

Итак, давайте рассмотрим их все.

Метрики расстояния

Понятие расстояния можно перевести в понятие «путь» в рамках сетевой структуры. Путь - это просто набор ссылок, соединяющих два или более узлов. Что еще более интересно, мы можем определить для каждой пары узлов i, j кратчайший путь l_ij, соединяющий эти узлы. А именно, в приведенном выше примере (с небольшими изменениями для этой цели) кратчайший путь между Лондоном и Сан-Франциско:

Имея в виду эту меру, мы можем определить диаметр сети, который является максимальным значением среди всех возможных кратчайших путей:

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

Сан-Франциско ‹-› Нью-Йорк = 1
Сан-Франциско ‹-› Рим = 2
Сан-Франциско ‹-› Лондон = 3
Сан-Франциско ‹-› Милан = 3
Сан-Франциско ‹-› Париж = 3
Нью-Йорк ‹-› Рим = 1
Нью-Йорк ‹-› Милан = 2
Нью-Йорк ‹-› Лондон = 2
Нью-Йорк ‹-› Париж = 2
Рим ‹-› Лондон = 1
Рим ‹-› Милан = 1
Рим ‹-› Париж = 1

Показатели центральности

Среди этих мер мы можем выделить следующие:

Степень центральности: измеряет количество ребер, попадающих в узел i. А именно, на приведенном выше рисунке степень центральности узла Rome равна 4. Обратите внимание, что, если мы имеем дело с ориентированными графами, каждый узел будет иметь меру центральности по внутренней и внешней степени, подсчитывая количество ребер, приходящих к и, соответственно, от целевого узла.
Центральность близости: это относится к среднему расстоянию от вершины i до всех остальных и вычисляется как:

Где l_ij, как определено выше, - это кратчайший путь между вершинами i и j. Например, давайте вычислим центральность близости для узла Рим:

Если вместо этого мы вычислим Милан:

Мы можем сделать вывод, что Рим более «центральный» (он же хорошо связан), чем Милан.

Централизация посредничества: этот показатель оценивает важность узла с точки зрения «моста», который он может создать среди других узлов. Действительно, один узел может быть плохо связан, но он может удерживать всю сеть вместе. Рассмотрим следующий пример:

Узел A имеет степень центральности 2 (довольно низкая), но при удалении вся сеть разваливается. Узел A действительно объединяет два кластера узлов. Чтобы учесть это важное свойство, на помощь приходит центральность промежуточности:

Поясним эту формулу:

σ_hj представляет собой общее количество кратчайших путей между h и j
σ_hj (i) - общее количество кратчайших путей между h и j, проходящих через i.

Интуитивно понятно, что чем больше кратчайших путей проходит через i, тем ближе это значение к 1. Рассмотрим следующий график:

И давайте вычислим центральность промежуточности узла A:

Таким образом, в этом случае центральность по промежуточности узла A равна 9 (сумма последнего столбца), в то время как его центральность по степени равна 2, а центральность по близости равна 0,1 (1/10).

Статистические свойства

Мы можем дополнительно охарактеризовать сеть с помощью распределения. А именно, мы можем вычислить распределение степеней: это распределение вероятностей P (k), которое сообщает нам вероятность того, что любой случайно выбранный узел будет иметь степень = k. Это можно визуализировать, просто подсчитав количество узлов, имеющих заданную степень, и построив соответствующую гистограмму. А именно, рассмотрим следующий график:

Соответствующая гистограмма:

Как видите, наиболее частая степень среди узлов равна 2. Обратите внимание, что те же рассуждения можно применить к метрике центральности промежуточности, получив распределение промежуточности.

Последние мысли

В этой первой статье я познакомил вас с некоторыми основными функциями и показателями для характеристики сетей. В следующих статьях я познакомлю вас с пакетом Python NetworkX и выделю различные типы графиков.

Надеюсь, вам понравилось чтение, следите за обновлениями Часть 2!

Введение в сетевую науку с NetworkX