[Перевод] Теория графов и сетевой анализ на основе Python

• Оригинальный адрес:An Introduction to Graph Theory and Network Analysis (with Python codes)
• Оригинальный автор:Srivatsa
• Перевод с:Программа перевода самородков
• Постоянная ссылка на эту статью:GitHub.com/rare earth/gold-no…
• Переводчик:EmilyQiRabbit
• Корректор:xionglong58,kasheemlew

Введение

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

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

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

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

Вы готовы? Тогда приступим к обучению!

содержание

• Диаграммы и приложения диаграмм
• История графов и почему мы выбрали графы?
• Термины, которые нужно знать
• Основные понятия теории графов
• Ознакомьтесь с графиками в Python
• Анализ на основе набора данных

Диаграммы и приложения диаграмм

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

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

V = {v1, v2, v3, v4, v5}

E = {(v1,v2), (v2,v5), (v5, v5), (v4,v5), (v4,v4)}

Edge(u,v) и edge(v,u) одинаковы — это неупорядоченные пары.

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

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

Формально:

• рисунокСостоит из двух наборов.G = (V,E). V — это набор вершин. E представляет собой набор ребер. E представляет собой комбинацию пар элементов в V (неупорядоченные пары).
• ориентированный графЭто также сопряжение наборов.D = (V,A). V — множество вершин. A — множество дуг. A — попарная комбинация (упорядоченная пара) элементов V.

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

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

from IPython.display import Image
Image('images/network.PNG')

Image('images/usecase.PNG')

Как видно из приведенных выше примеров, графики широко используются в анализе данных. Рассмотрим несколько случаев:

• Анализ рынка- Графики можно использовать для поиска самых влиятельных людей в социальных сетях. Рекламодатели и маркетологи могут попытаться максимизировать свои маркетинговые преимущества, направляя сообщения самым влиятельным людям в социальной сети.
• банковская операция- Графики можно использовать для выявления необычных трейдеров и сокращения количества мошеннических транзакций. Во многих случаях террористическая деятельность выявляется путем анализа денежных потоков в международных банковских сетях.
• цепочка поставок- Карты могут помочь найти оптимальный маршрут доставки товаров, а также могут помочь определить расположение складов и центров доставки.
• Фармацевтическая— Фармацевтические компании могут использовать теорию графов для оптимизации маршрутов продавцов. Это может помочь продавцу снизить затраты и сократить время в пути.
• телекоммуникации- Телекоммуникационные компании обычно используют графики (диаграммы Вороного) для расчета количества и расположения вышек, а также для обеспечения максимального покрытия.

История графов и почему мы выбрали графы?

История графа

Хотите узнать, как строилась теория графов — читайте дальше!

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

• Нет повторяющихся путей
• Где заканчивается путь, там же, где вы начали

Этот вопрос эквивалентен тому, может ли граф с четырьмя узлами и семью ребрами иметь эйлеров круг (эйлеров круг относится к пути Эйлера с той же начальной и конечной точками. Путь Эйлера относится к пути в графе, который проходит через каждое ребро ровно один раз. Дополнительные термины вводятся ниже). Этот вопрос приводит к понятию графа Эйлера. Что же касается вопроса о Кенигсбергском мосту, то ответ отрицательный, первым, кто ответил на этот вопрос, как вы, должно быть, догадались, был Эйлер.

В 1840 году А. Ф. Мебиус дал понятие полного графа и двудольного графа, а Куратовский с помощью развлекательной задачи доказал, что все они являются планарными графами. Понятие дерева (ациклический полносвязный граф) было предложено Густавом Кирхгофом в 1845 году, и он использовал идею теории графов при расчете тока в сети или цепи.

В 1852 году Томас Гутери создал знаменитую задачу о четырех красках. Затем в 1856 году Томас П. Киркман и Уильям Р. Гамильтон совместно изучали тор на многогранниках и создали концепцию гамильтонова графа, изучая, как найти путь, который проходит через каждую точку, указанную только один раз. В 1913 г. Х. Дьюдени также упомянул проблему. Хотя проблема четырех цветов была поставлена ​​очень рано, она была решена лишь столетие спустя Кеннетом Аппелем и Вольфгангом Хакеном. Это время считается временем рождения теории графов.

Кейли изучал особую аналитическую форму дифференциального исчисления и, следовательно, древовидную структуру. Это имеет много приложений в теоретической химии. Это также вдохновило на создание теории перечислимых графов. А в 1878 году Сильвестр использовал термин «граф», когда проводил аналогию между «квантовыми инвариантами» и ковариатами алгебраических и молекулярных графов.

В 1941 году Рэмси изучил проблему раскраски, что привело к определению другой ветви теории графов, экстремальной теории графов. В 1969 году Генрих решил задачу о четырех красках с помощью компьютера. Изучение инкрементных графов также вдохновило на развитие теории случайных графов. История теории графов и топологии также тесно связана со многими общими концепциями и теориями между ними.

Image('images/Konigsberg.PNG', width = 800)

Почему выбирают графики?

Следующие пункты могут мотивировать вас использовать теорию графов в повседневных задачах науки о данных:

1. Графы — лучший подход при работе с абстрактными понятиями, такими как реляционные проблемы и задачи взаимодействия. В то же время он также обеспечивает более интуитивно понятный и наглядный способ осмысления этих концепций. При анализе социальных отношений графы естественным образом становятся основой.
2. База данных Graph стала очень распространенным компьютерным инструментом, это альтернатива базам данных SQL и NoSQL.
3. Тип графика: DAG (направленный ациклический график), который можно использовать для моделирования аналитических потоков.
4. Некоторые платформы нейронных сетей также используют DAG для моделирования отдельных операций на разных уровнях.
5. Теория графов используется для изучения и моделирования социальных сетей, моделей мошенничества, моделей власти, виральности и влияния в социальных сетях. Анализ социальных сетей (SNA), пожалуй, самое известное применение теории графов в науке о данных.
6. Он используется в алгоритмах кластеризации, наиболее известным из которых является алгоритм K-Means.
7. В системной динамике также применяются некоторые концепции теории графов, самые известные из которых — циклы.
8. Оптимизация пути — это подмножество задач оптимизации, в которых также используется концепция графов.
9. С точки зрения компьютерных наук графы делают вычисления более эффективными. По сравнению с табличными данными некоторые алгоритмы могут быть менее сложными, если данные представлены в виде графика.

Термины, которые нужно знать

Прежде чем двигаться дальше, мы рекомендуем вам ознакомиться с приведенными ниже условиями.

1. вершинаuиvназывается краем(u,v)изконечная точка(end vertices)
2. Если два ребра имеют одинаковыеконечная точка, то они называютсяВ параллели
3. В форме(v,v)сторона представляет собойзвенеть
4. Если графнет параллельных ребер и петель, это называетсяПростая диаграмма
5. Если графнет края, то назовите этот график какнулевой(Empty). этоEпусто
6. график, еслинет вершины, затем назовите егопустая карта(Null Graph). этоVиEвсе пусто
7. Граф, имеющий только одну вершину, называетсятривиальный граф(Trivialграфик)
8. Если два ребра имеют общую вершину, то онисоседний(Adjacent)боковая сторона. Если две вершины имеют общее ребро, то онисоседнийвершина
9. вершинаТратить,письмоd(v), что указывает на то, что вершина является конечной точкойбоковая сторонаколичество. По соглашению степень соответствующей конечной точки кольца в два раза больше, чем степень ребра, и следует добавить степени двух конечных точек, соответствующих параллельному ребру.
10. Вершина со степенью 1 называетсяизолированная вершина(Изолированные вершины).d(1)вершины изолированы.
11. Граф называется графом, если множество ребер содержит все возможные ребра конечных точек.полный граф(Полный)
12. Точки и ребра в графе конечны, а подставляемая последовательность ViEiViEi называется графомG = (V,E)один издорожка(Walk)
13. Путь называется открытым, если его начальная и конечная вершины различны (Open). А если начальная вершина и конечная вершина совпадают, то она называется закрытой (Closed)
14. Трассы, которые проходят каждое ребро не более одного раза (Trail) называется путем
15. Пути, проходящие через каждую вершину не более одного раза (Path) называется трассой (кроме замкнутых цепей)
16. Замкнутый путь — это замкнутый цикл (Circuit) - аналогично схеме

Основные понятия теории графов

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

средняя длина пути

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

БФС и ДФС

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

Цель BFS — пройти по графу путем последовательного поиска узлов, ближайших к корневому узлу, а цель DFS — пройти по графу путем последовательного поиска узлов, максимально удаленных от корневого узла.

центральность

Это самый универсальный и самый важный концептуальный инструмент для сетевого анализа. Цель центральности — найти самые важные узлы в сети. Есть много способов определить «важный», поэтому есть много основных показателей. Сама мера центральности имеет категории (или категории мер центральности). Некоторые измеряются потоком ребер, а другие — структурой пути графа.

Вот некоторые из наиболее распространенных приложений:

1. степень центральности— Первое и концептуально самое простое определение центральности. Он представляет собой количество ребер, соединенных точкой. В случае ориентированного графа у нас может быть две меры степени центральности. Центральность исходящей степени и внутренней степени.
2. центральная близость- От этого узла средняя длина пути до всех узлов наименьшая.
3. промежуточность- Сколько раз узел появляется на кратчайшем пути между двумя другими узлами.

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

плотность сети

Мера количества ребер в графе. Определения различаются в зависимости от типа диаграммы и контекста, в котором существует проблема. Для полностью неориентированного графа плотность сети равна 1, а для пустого графа степень равна 0. Плотность сети графа также может быть больше единицы в некоторых сценариях (например, когда граф содержит циклы).

Графическая рандомизация

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

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

Ознакомьтесь с графиками в Python

Мы будем использовать PythonnetworkxИнструментарий. Если вы используете дистрибутив Python Anaconda, его можно установить в корневой среде Anaconda. вы также можете использоватьpip installустановить.

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

Создать график

import networkx as nx

# 创建一个图
G = nx.Graph() # 现在 G 是空的

# 添加一个节点
G.add_node(1)
G.add_nodes_from([2,3]) # 你也能通过传入一个列表来添加一系列的节点

# 添加边
G.add_edge(1,2)

e = (2,3)
G.add_edge(*e) # * 表示解包元组
G.add_edges_from([(1,2), (1,3)]) # 正如节点的添加，我们也可以这样添加边

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

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

subgraph(G, nbunch)      - 生成由节点集合 nbunch 组成的 G 的子图
union(G1,G2)             - 求图的并集
disjoint_union(G1,G2)    - 图中所有不同节点组成的单元
cartesian_product(G1,G2) - 返回笛卡尔积图（Cartesian product graph）
compose(G1,G2)           - 两图中都有的点所组成的图
complement(G)            - 补图
create_empty_copy(G)     - 返回同一个图的空副本
convert_to_undirected(G) - 返回图的无向形式
convert_to_directed(G)   - 返回图的有向形式

Существуют отдельные классы для разных классов графов. Например классnx.DiGraph()Поддерживаются новые ориентированные графы. Графики, содержащие определенные пути, также можно создавать напрямую одним из методов. См. документацию для всех способов создания графиков. Список литературы дан в конце текста.

Image('images/graphclasses.PNG', width = 400)

Получить ребра и узлы

Все ребра и узлы графа могут использовать методG.nodes()иG.edges()Получать. Отдельные ребра и узлы можно получить с помощью круглых скобок/индексов.

G.nodes()

NodeView((1, 2, 3))

G.edges()

EdgeView([(1, 2), (1, 3), (2, 3)])

G[1] # 与 G.adj[1] 相同

AtlasView({2: {}, 3: {}})

G[1][2]

{}

G.edges[1, 2]

{}

Графическая визуализация

Networkx предоставляет базовые возможности визуализации графов, но его основная цель — анализ графиков, а не визуализация графов. Визуализация графиков сложна, и мы будем использовать специальные инструменты, предназначенные для этого.MatplotlibПредусмотрено множество удобных функций. ноGraphVizвероятно, лучший инструмент, потому что он начинается сPyGraphVizпредоставляет интерфейс Python в виде (ссылка на его документацию приведена ниже).

%matplotlib inline
import matplotlib.pyplot as plt
nx.draw(G)

Сначала вам нужно установить Graphviz с веб-сайта (ссылка для скачивания ниже). затем бегиpip install pygraphviz --install-option=" <>. В параметрах установки необходимо указать адреса библиотеки Graphviz и папки зависимостей.

import pygraphviz as pgv
d={'1': {'2': None}, '2': {'1': None, '3': None}, '3': {'1': None}}
A = pgv.AGraph(data=d)
print(A) # 这是图的字符串形式或者简单展示形式

Output:

strict graph "" {
	1 -- 2;
	2 -- 3;
	3 -- 1;
}

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

# 让我们创建另一个图，我们可以控制它每个节点的颜色
B = pgv.AGraph()

# 设置所有节点的共同属性
B.node_attr['style']='filled'
B.node_attr['shape']='circle'
B.node_attr['fixedsize']='true'
B.node_attr['fontcolor']='#FFFFFF'

# 创建并设置每个节点不同的属性（使用循环）
for i in range(16):
	B.add_edge(0,i)
	n=B.get_node(i)
	n.attr['fillcolor']="#%2x0000"%(i*16)
	n.attr['height']="%s"%(i/16.0+0.5)
	n.attr['width']="%s"%(i/16.0+0.5)
B.draw('star.png',prog="circo") # 这行代码会在本地创建一个 .png 格式的文件。如下所示。

Image('images/star.png', width=650) # 我们所创建的图的可视化图片

Обычно визуализацию считают отдельной задачей от анализа графов. Анализируемый график экспортируется в виде файла точек. Затем этот точечный файл визуализируется отдельно, чтобы показать точку, которую мы пытаемся доказать.

Анализ на основе набора данных

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

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

1. Каково кратчайшее расстояние от А до В? Какое самое короткое расстояние? У кого самое короткое время?
2. Есть ли путь от C к D, который проходит?
3. В каких аэропортах больше всего загружено движение?
4. Какой аэропорт находится среди большинства аэропортов? тогда он может действовать как локальный концентратор

import pandas as pd
import numpy as np

data = pd.read_csv('data/Airlines.csv')

data.shape
(100, 16)

data.dtypes

year                int64
month               int64
day                 int64
dep_time          float64
sched_dep_time      int64
dep_delay         float64
arr_time          float64
sched_arr_time      int64
arr_delay         float64
carrier            object
flight              int64
tailnum            object
origin             object
dest               object
air_time          float64
distance            int64
dtype: object

1. Мы заметили, что это хороший выбор, чтобы начальная и конечная точки были узлами. Таким образом, вся информация может использоваться как атрибуты узлов или ребер. Край можно рассматривать как путешествие. Путешествие будет связано с другим временем, номером рейса, бортовым номером самолета и т. д.
2. Мы заметили, что год, месяц, день и другая информация о времени были разбросаны по нескольким столбцам. Мы хотим создать временную шкалу, которая будет содержать всю эту информацию, нам также нужно отдельно сохранить предполагаемое и фактическое время прибытия и отправления. В конечном итоге у нас должно быть 4 временных бара (расчетное и фактическое время прибытия и отправления).
3. Кроме того, формат шкалы времени не подходит. 16:30 представлено как 16:30 вместо 16:30. В этом столбце нет разделителя для разделения информации. Один из способов — использовать строковые методы библиотеки pandas и регулярные выражения.
4. Также следует отметить, что sched_dep_time и sched_arr_time имеют тип данных int64, а dep_time и arr_time — тип данных float64.
5. Еще одним усложняющим фактором являются значения NaN.

# 将 sched_dep_time 转化为 'std' —— 预计起飞时间
data['std'] = data.sched_dep_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_dep_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'

# 将 sched_arr_time 转化为 'sta' —— 预计抵达时间
data['sta'] = data.sched_arr_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_arr_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'

# 将 dep_time 转化为 'atd' —— 实际起飞时间
data['atd'] = data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'

# 将 arr_time 转化为 'ata' —— 实际抵达时间
data['ata'] = data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'

Теперь у нас есть шкала времени в ожидаемом формате. Наконец, мы ожидаемyear,monthиdayОбъединены в один таймбар. Этот шаг необязателен, но после преобразования времени вdatetimeФормат, мы можем легко получить год, месяц, день и другую информацию.

data['date'] = pd.to_datetime(data[['year', 'month', 'day']])

# 最后，我们删除掉不需要的栏
data = data.drop(columns = ['year', 'month', 'day'])

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

import networkx as nx
FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True,)

FG.nodes()

вывод:

NodeView(('EWR', 'MEM', 'LGA', 'FLL', 'SEA', 'JFK', 'DEN', 'ORD', 'MIA', 'PBI', 'MCO', 'CMH', 'MSP', 'IAD', 'CLT', 'TPA', 'DCA', 'SJU', 'ATL', 'BHM', 'SRQ', 'MSY', 'DTW', 'LAX', 'JAX', 'RDU', 'MDW', 'DFW', 'IAH', 'SFO', 'STL', 'CVG', 'IND', 'RSW', 'BOS', 'CLE'))

FG.edges()

вывод:

EdgeView([('EWR', 'MEM'), ('EWR', 'SEA'), ('EWR', 'MIA'), ('EWR', 'ORD'), ('EWR', 'MSP'), ('EWR', 'TPA'), ('EWR', 'MSY'), ('EWR', 'DFW'), ('EWR', 'IAH'), ('EWR', 'SFO'), ('EWR', 'CVG'), ('EWR', 'IND'), ('EWR', 'RDU'), ('EWR', 'IAD'), ('EWR', 'RSW'), ('EWR', 'BOS'), ('EWR', 'PBI'), ('EWR', 'LAX'), ('EWR', 'MCO'), ('EWR', 'SJU'), ('LGA', 'FLL'), ('LGA', 'ORD'), ('LGA', 'PBI'), ('LGA', 'CMH'), ('LGA', 'IAD'), ('LGA', 'CLT'), ('LGA', 'MIA'), ('LGA', 'DCA'), ('LGA', 'BHM'), ('LGA', 'RDU'), ('LGA', 'ATL'), ('LGA', 'TPA'), ('LGA', 'MDW'), ('LGA', 'DEN'), ('LGA', 'MSP'), ('LGA', 'DTW'), ('LGA', 'STL'), ('LGA', 'MCO'), ('LGA', 'CVG'), ('LGA', 'IAH'), ('FLL', 'JFK'), ('SEA', 'JFK'), ('JFK', 'DEN'), ('JFK', 'MCO'), ('JFK', 'TPA'), ('JFK', 'SJU'), ('JFK', 'ATL'), ('JFK', 'SRQ'), ('JFK', 'DCA'), ('JFK', 'DTW'), ('JFK', 'LAX'), ('JFK', 'JAX'), ('JFK', 'CLT'), ('JFK', 'PBI'), ('JFK', 'CLE'), ('JFK', 'IAD'), ('JFK', 'BOS')])

nx.draw_networkx(FG, with_labels=True) # 图的快照。正如我们期望的，我们看到了三个很繁忙的机场

nx.algorithms.degree_centrality(FG) # Notice the 3 airports from which all of our 100 rows of data originates
nx.algorithms.degree_centrality(FG) # 从一百多行的所有源数据中标注出这三个机场
nx.density(FG) # 图的平均边度

вывод:

0.09047619047619047

nx.average_shortest_path_length(FG) # 图中所有路径中的最短平均路径

вывод:

2.36984126984127

nx.average_degree_connectivity(FG) # 对于一个度为 k 的节点 —— 它的邻居节点的平均值是什么？

вывод:

{1: 19.307692307692307, 2: 19.0625, 3: 19.0, 17: 2.0588235294117645, 20: 1.95}

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

1. кратчайший путь
2. кратчайший путь

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

мы начинаем сJAX и DFWПример аэропорта:

# 找到所有可用路径
for path in nx.all_simple_paths(FG, source='JAX', target='DFW'):
	print(path)

# 站到从 JAX 到 DFW 的 dijkstra 路径
# 你可以在这里阅读更多更深入关于 dijkstra 是如何计算的信息 —— https://courses.csail.mit.edu/6.006/fall11/lectures/lecture16.pdf
dijpath = nx.dijkstra_path(FG, source='JAX', target='DFW')
dijpath

вывод:

['JAX', 'JFK', 'SEA', 'EWR', 'DFW']

# 我们来试着找出飞行时间的 dijkstra 路径（近似情况）
shortpath = nx.dijkstra_path(FG, source='JAX', target='DFW', weight='air_time')
shortpath

вывод:

['JAX', 'JFK', 'BOS', 'EWR', 'DFW']

Суммировать

Эта статья — очень краткое введение в очень интересную область теории графов и сетевого анализа. Знание теории графов и пакетов Python может быть бесценным инструментом для любого специалиста по данным. Существует также ряд вопросов, которые можно задать об использованном выше наборе данных, например:

1. Найдите кратчайшее расстояние между двумя аэропортами, учитывая стоимость, время полета и доступные рейсы?
2. Если вы управляете авиакомпанией и у вас есть парк самолетов. Вы можете знать спрос людей на полеты. Вы имеете право эксплуатировать еще два самолета (или добавить еще два к своему флоту), какие два маршрута вы будете использовать для получения максимальной прибыли?
3. Можете ли вы изменить расписание рейсов и графиков, чтобы оптимизировать определенный параметр (например, разумность времени или прибыльность)

Если вы решите эти проблемы, сообщите нам об этом, оставив комментарий в разделе комментариев!

Сетевой анализ поможет нам решить некоторые распространенные проблемы науки о данных и визуализировать их в более крупном и абстрактном виде. Если вы хотите узнать больше о конкретном аспекте, пожалуйста, оставьте нам сообщение.

Библиография и цитаты

1. History of Graph Theory || S.G. Shrinivas et. al
2. Big O Notation cheatsheet
3. Networkx reference documentation
4. Graphviz download
5. Pygraphvix
6. Star visualization
7. Dijkstra Algorithm

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

---

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,внешний интерфейс,задняя часть,блокчейн,продукт,дизайн,искусственный интеллектЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.