Сетевой анализ улично-дорожной сети

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

Теперь перейдём непосредственно к задачам сетевого анализа. С помощью библиотеки networkx мы выполним несколько ключевых типов анализа:

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

0. Импорт библиотек и подготовка данных¶

0.1 Импорт библиотек¶

import osmnx as ox
import pandas as pd
import geopandas as gpd
import networkx as nx
import matplotlib.pyplot as plt

0.2 Подготовка данных¶

Загрузим граф улично-дорожной сети из OSM

# Указываем район
area_name = "Ленинский район, Екатеринбург"

# Получаем граф улично-дорожной сети из OpenStreetMap
# network_type='drive' — автомобильная сеть (учитываются дороги, доступные для движения на машине)
graph = ox.graph_from_place(area_name, network_type='drive')

# Визуализируем граф
ox.plot_graph(graph)

(<Figure size 800x800 with 1 Axes>, <Axes: >)

Загрузим кафе из OSM для того же района

cafes = ox.features_from_place(area_name, tags={"amenity": "cafe"})

cafes.explore(tiles="cartodbpositron")

1. Кратчайший путь¶

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

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

Построим кратчайшее расстояние между двумя ресторанами в рассматриваемом районе.

1.1. Проверка системы координат¶

Проверим, совпадают ли системы координат у точек с ресторанами и графа УДС

graph.graph["crs"] == cafes.crs

True

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

1.2. Выбор точек¶

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

random_points = cafes.sample(n=2, random_state=42) 
cafe_1 = random_points.iloc[0].geometry
cafe_2 = random_points.iloc[1].geometry

1.3. Поиск ближайших узлов графа¶

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

orig_node = ox.distance.nearest_nodes(graph, X=cafe_1.x, Y=cafe_1.y)
dest_node = ox.distance.nearest_nodes(graph, X=cafe_2.x, Y=cafe_2.y)

1.4. Построение кратчайшего маршрута¶

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

Используем функцию shortest_path из библиотеки networkx.

В качестве веса указываем длину рёбер (length), поэтому маршрут будет минимальным по расстоянию.

Отдельно рассчитаем общую длину маршрута с помощью shortest_path_length.

Функция shortest_path возвращает последовательность узлов, через которые проходит маршрут, а shortest_path_length — его суммарную длину (в метрах, так как атрибут length хранится в метрах).

shortest_path = nx.shortest_path(graph, source=orig_node, target=dest_node, weight="length")
shortest_distance = nx.shortest_path_length(graph, source=orig_node, target=dest_node, weight="length")

print("Path:", shortest_path)
print("Distance (meters):", shortest_distance)

Path: [713222572, 10798749439, 10798749434]
Distance (meters): 549.606519888634

1.5. Визуализация маршрута¶

Визуализируем найденный маршрут на графе с помощью функции plot_graph_route из библиотеки osmnx.

ox.plot_graph_route(graph, shortest_path, route_linewidth=2, node_size=0, bgcolor="white")

(<Figure size 800x800 with 1 Axes>, <Axes: >)

2. Центральность¶

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

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

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

2.1. Центральность по степени¶

Центральность по степени (Degree Centrality) — это показатель, который измеряет количество связей (ребер) узла.

В контексте улично-дорожной сети степень узла соответствует числу дорог, сходящихся в данной точке.

Узлы с высокой степенью центральности считаются более «связанными» и часто соответствуют крупным перекрёсткам или транспортным узлам.

В библиотеке networkx этот показатель можно получить с помощью функции nx.degree_centrality().

Рассчитаем центральность по степени для всех узлов графа.

# Рассчитываем центральность по степени
degree_centrality = nx.degree_centrality(graph)

# Визуализируем результат
fig, ax = plt.subplots(figsize=(10, 10))
node_sizes = [v * 1000 for v in degree_centrality.values()] 

ox.plot_graph(graph, node_size=node_sizes, node_color='red', bgcolor='white', ax=ax, show=False)
plt.title("Центральность по степени")

ax.set_axis_off()

plt.show()

2.2. Центральность по посредничеству¶

Центральность по посредничеству (Betweenness Centrality) — это показатель, который отражает, как часто узел находится на кратчайших путях между другими узлами сети.

Иными словами, он показывает, через какие узлы проходит наибольшее количество маршрутов.

Узлы с высокой центральностью по посредничеству играют роль «мостов», соединяющих разные части сети. В улично-дорожной сети такие узлы часто соответствуют ключевым перекрёсткам, через которые проходит значительный поток движения. Центральность по посредничеству рассчитывается на основе кратчайших путей между всеми парами узлов. В библиотеке networkx для этого используется функция nx.betweenness_centrality().

# Рассчитываем центральность по посредничеству
betweenness_centrality = nx.betweenness_centrality(graph, weight='length')

# Визуализируем результат
fig, ax = plt.subplots(figsize=(10, 10))
node_sizes = [v * 1000 for v in betweenness_centrality.values()]

ox.plot_graph(graph, node_size=node_sizes, node_color='blue', bgcolor='white', ax=ax, show=False)

ax.set_axis_off()

plt.title("Центральность по посредничеству ")
plt.show()

2.3 Центральность по близости¶

Центральность по близости (Closeness Centrality) — это показатель, который отражает, насколько близко узел расположен ко всем остальным узлам сети с точки зрения кратчайших путей.

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

Узлы с высокой центральностью по близости имеют минимальные суммарные расстояния до остальных узлов и обеспечивают хороший доступ к различным участкам территории.

Центральность по близости рассчитывается на основе длин кратчайших путей от узла до всех остальных узлов. В библиотеке networkx для этого используется функция nx.closeness_centrality().

# Рассчитываем центральность по близости
closeness_centrality = nx.closeness_centrality(graph, distance='length')


# Визуализация центральности по близости
fig, ax = plt.subplots(figsize=(10, 10))

node_sizes = [v * 100000 for v in closeness_centrality.values()]

ox.plot_graph(graph, node_size=node_sizes, node_color='green', bgcolor='white', ax=ax, show=False)

ax.set_axis_off()
plt.title("Центральность по близости")
plt.show()

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

3. Матрица расстояний¶

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

Она позволяет ответить на вопрос: насколько далеко объекты расположены друг от друга с учётом реальной улично-дорожной сети, а не «по прямой».

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

3.1. Выбор подмножества точек¶

Для примера возьмём несколько случайных кафе

sample_cafes = cafes.sample(n=5, random_state=42)

3.2. Привязка к узлам графа¶

Для каждой выбранной точки найдём ближайший узел улично-дорожной сети. Таким образом мы «привязываем» объекты к графу, чтобы затем можно было рассчитывать расстояния между ними.

nodes = [
    ox.distance.nearest_nodes(graph, X=geom.x, Y=geom.y)
    for geom in sample_cafes.geometry
]

3.3. Расчёт матрицы расстояний¶

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

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

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

В нашем случае мы действуем следующим образом:

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

distance_matrix = {}

for i, node_i in enumerate(nodes):
    distances = nx.single_source_dijkstra_path_length(graph, node_i, weight='length')
    
    for j, node_j in enumerate(nodes):
        distance_matrix[(i, j)] = distances.get(node_j, None)

Здесь:

single_source_dijkstra_path_length вычисляет кратчайшие расстояния от одного узла (node_i) до всех достижимых узлов графа;
weight='length' означает, что в качестве веса используется длина рёбер (в метрах);
во внутреннем цикле мы выбираем расстояния только до нужных узлов и сохраняем их;
в результате получаем структуру, содержащую расстояния между всеми парами точек.

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

3.4. Матрица в виде таблицы¶

Полученную матрицу расстояний удобно представить в виде таблицы.

Для этого преобразуем словарь с расстояниями в объект DataFrame из библиотеки pandas, где строки и столбцы будут соответствовать выбранным точкам:

мы создаём пустую таблицу заданного размера (len(nodes) × len(nodes));
ключи словаря (i, j) соответствуют индексам строки и столбца;
с помощью .loc записываем рассчитанные расстояния в соответствующие ячейки;
в результате получаем матрицу расстояний в табличном виде.

matrix_df = pd.DataFrame(index=range(len(nodes)), columns=range(len(nodes)))

for (i, j), dist in distance_matrix.items():
    matrix_df.loc[i, j] = dist

matrix_df

4. Зоны доступности¶

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

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

Частным случаем зон доступности являются изохроны — области, которые можно достичь за заданное время (например, за 5, 10 или 15 минут).

Определим, какую территорию можно достичь от заданной точки, пройдя 1.5 км

4.1. Выбор начальной точки¶

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

# Выбираем одно случайное кафе
start_cafe = cafes.sample(n=1, random_state=20).iloc[0].geometry

# Находим ближайший узел графа к этому кафе
start_node = ox.distance.nearest_nodes(graph, X=start_cafe.x, Y=start_cafe.y)

Здесь:

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

4.2. Определение радиуса¶

Зададим максимальное расстояние, которое определяет зону доступности.

max_dist = 1500  # например, 1.5 км

4.3. Построение зоны доступности (subgraph)¶

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

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

алгоритм проходит по сети от исходного узла,
находит все узлы, до которых можно добраться с суммарной длиной пути ≤ max_dist,
формирует новый граф (подграф), содержащий только эти узлы и соединяющие их рёбра.

subgraph = nx.ego_graph(graph, start_node, radius=max_dist, distance='length')

Чтобы лучше понять, как формируется зона доступности, визуализируем:

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

# Преобразуем весь граф в GeoDataFrame, чтобы получить его границы
nodes_all, edges_all = ox.graph_to_gdfs(graph)

# Границы всего графа
xmin, ymin, xmax, ymax = edges_all.total_bounds

# Создаём фигуру
fig, ax = plt.subplots(figsize=(10, 10))

# Рисуем весь граф
ox.plot_graph(
    graph,
    ax=ax,
    node_size=0,
    edge_color="lightgray",
    edge_linewidth=1,
    show=False,
    close=False
)

# Рисуем подграф поверх
ox.plot_graph(
    subgraph,
    ax=ax,
    node_size=0,
    edge_color="red",
    edge_linewidth=2,
    show=False,
    close=False
)

# Получаем координаты стартового узла
x = graph.nodes[start_node]["x"]
y = graph.nodes[start_node]["y"]

# Отмечаем стартовую точку
ax.scatter(x, y, c="blue", s=80, zorder=5)

# Фиксируем границы по всему графу
ax.set_xlim(xmin, xmax)
ax.set_ylim(ymin, ymax)

# Оформление
ax.set_axis_off()

plt.show()

4.4. Преобразование подграфа в геометрию¶

Подграф — это всё ещё граф (узлы и рёбра), а не геометрия, поэтому напрямую отобразить его как область нельзя. Чтобы работать с ним как с пространственным объектом, преобразуем его в GeoDataFrame.

edges = ox.convert.graph_to_gdfs(subgraph, nodes=False, edges=True)

Теперь у нас есть линии (рёбр графа), представляющие доступную часть сети.

Объединим их в одну геометрию:

service_area = edges.geometry.union_all()

На этом этапе мы получаем набор линий, но зона доступности обычно представляется в виде полигона.

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

4.5. Построение полигона зоны доступности¶

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

isochrone = service_area.convex_hull

Это упрощённое приближение зоны доступности — реальная зона может иметь более сложную форму.

4.6. Визуализация¶

Чтобы отобразить зону и исходную точку на интерактивной карте, создадим GeoDataFrame

from shapely.geometry import Point

iso_gdf = gpd.GeoDataFrame(geometry=[isochrone], crs=edges.crs)
point_gdf = gpd.GeoDataFrame(geometry=[Point(x, y)], crs=edges.crs)

Посмотрим на карте

m = iso_gdf.explore(color="red", alpha=0.5, tiles="cartodbpositron")
point_gdf.explore(m=m, color="blue", markersize=100)

Итог¶

В этом разделе мы познакомились с основными задачами сетевого анализа улично-дорожной сети

Мы научились:

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

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

В следующем разделе мы познакомимся с альтернативным подходом — использованием специализированных сервисов маршрутизации (например, OpenRouteService, OSRM и других), которые выполняют расчёты на своей стороне.