Пространственные сети — это сетевые модели, включающие пространственные элементы, где узлы встроены в физическое пространство, а метрика определяет связи между ними. Эти сети находят применение в различных реальных системах, таких как инфраструктурные сети (транспортные, электрические, телекоммуникационные), социальные сети и синаптические сети. Как правило, вероятность соединения уменьшается с увеличением расстояния между узлами, что часто моделируется с использованием евклидова расстояния в 2D или 3D пространстве. Пространственные сети были тщательно исследованы, в результате чего было создано множество моделей с теоретическими доказательствами их сетевых свойств. Обзорная статья Марка Бартелеми 2010 г. представляет собой всесторонний обзор области и исследует несколько распространенных моделей пространственных сетей. Эти модели можно классифицировать по трем ключевым параметрам, и они реализованы в пакете networkx, что облегчает их практическое применение и анализ.
В этой статье мы будем использовать сеть Tesla North American Supercharger в качестве мотивирующего примера для демонстрации применения различных моделей пространственной сети, доступных в пакете networkx. Данные Supercharger, включающие 385 открытых Supercharger в Канаде и США по состоянию на апрель 2017 года, были собраны с сайта supercharger.info. Данные были организованы в Networkx Graph, где GPS-координаты каждого Supercharger представлены географическими хэшами и проецируются на единичный квадрат. Узлы на графике взвешены на основе населения городов, связанных с каждым Supercharger, выраженного в процентах от общего населения Северной Америки. Используя этот набор данных, мы можем применять различные модели пространственных сетей, реализованные в networkx, для анализа и моделирования сети Supercharger.
Базовая компоновка
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
# Some matplotlib settings
mpl_params = {
"axes.titlesize": 20,
"figure.figsize": (12, 4),
}
plt.rcParams.update(mpl_params)
# from networkx.readwrite import json_graph
import json
# load json-ed networkx datafile
with open("tesla_network.json") as infile:
G = nx.json_graph.node_link_graph(json.load(infile))
Далее загружаем данные и строим график.
# from networkx.readwrite import json_graph
import json
# load json-ed networkx datafile
with open("data/tesla_network.json") as infile:
G = nx.json_graph.node_link_graph(json.load(infile))
print(G)
Graph with 385 nodes and 0 edges
# extract pos and weight attributes for use in models
nodes = G.nodes()
pos = nx.get_node_attributes(G, "pos")
weight = nx.get_node_attributes(G, "weight")
node_opts = {"node_size": 50, "node_color": "blue", "alpha": 0.4}
edge_opts = {"edge_color": "k"}
Случайные геометрические графики
Случайные геометрические графы — это математические структуры, используемые для моделирования сетей или графов, в которых узлы случайным образом распределены в геометрическом пространстве. В этом типе графа положения узлов определяются случайными точками в заданном геометрическом пространстве, таком как евклидова плоскость или многомерное пространство.
Построение случайного геометрического графа обычно включает два основных параметра: количество узлов, обозначаемое «n», и радиус связности, обозначаемый «r». Каждому узлу присваивается случайное положение в геометрическом пространстве, а затем создается ребро между двумя узлами, если их евклидово расстояние меньше или равно радиусу связности r.
# Create a 2x2 grid of subplots
fig, axes = plt.subplots(2, 2, figsize=(12, 8))
# Define parameters for visualizing edges
alphas = (0.8, 0.8, 0.3, 0.1)
linewidths = (0.2, 0.2, 0.1, 0.1)
radii = (0, 0.1, 0.2, 0.3)
# Iterate over each subplot
for r, ax, alpha, lw in zip(radii, axes.ravel(), alphas, linewidths):
# Create a random geometric graph
RGG = nx.random_geometric_graph(nodes, radius=r, pos=pos)
# Draw the nodes
nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts)
# Draw the edges
nx.draw_networkx_edges(RGG, pos=pos, ax=ax, alpha=alpha, width=lw, **edge_opts)
# Set the subplot title
ax.set_title(f"$r = {r}$, {RGG.number_of_edges()} edges")
fig.tight_layout()
plt.show()
Графики географических порогов
Графы географических порогов представляют собой графовую модель, включающую географические аспекты и аспекты связности. В этой графовой модели узлы расположены в геометрическом пространстве, обычно представляющем географическую область, а ребра формируются между узлами на основе порогового расстояния.
Построение географического порогового графа включает в себя два основных параметра: пороговое расстояние, обозначаемое как «d», и положения узлов в геометрическом пространстве. Каждому узлу назначается определенное место в географическом пространстве, и между двумя узлами создается ребро, если их расстояние меньше или равно пороговому расстоянию d.
# Make edge visualization more prominent (and consistent) for the following
# examples
edge_opts["alpha"] = 0.8
edge_opts["width"] = 0.2
# Create a 1x2 grid of subplots
fig, axes = plt.subplots(1, 2)
# Custom distance metric function
dist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))
# Define distance metrics
distance_metrics = {
"Default (Euclidean) distance metric": None, # Euclidean distance
"Custom distance metric": dist,
}
# Iterate over each distance metric and subplot
for (name, metric), ax in zip(distance_metrics.items(), axes.ravel()):
# Create a geographical threshold graph
GTG = nx.geographical_threshold_graph(nodes, 0.1, pos=pos, weight=weight, metric=metric)
# Draw the nodes
nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts)
# Draw the edges
nx.draw_networkx_edges(GTG, pos=pos, ax=ax, **edge_opts)
# Set the subplot title
ax.set_title(f"{name}\n{GTG.number_of_edges()} edges")
# Adjust the spacing between subplots
fig.tight_layout()
# Display the figure
plt.show()
import math
from scipy.stats import norm
# Create a 1x2 grid of subplots
fig, axes = plt.subplots(1, 2)
# Define different p_dists
p_dists = {
"Exponential p_dist": lambda d: math.exp(-d),
"Normal p_dist": norm(loc=0.1, scale=0.1).pdf,
}
# Iterate over each p_dist and subplot
for (name, p_dist), ax in zip(p_dists.items(), axes.ravel()):
# Create a geographical threshold graph with specified p_dist
GTG = nx.geographical_threshold_graph(nodes, 0.01, pos=pos, weight=weight, metric=dist, p_dist=p_dist)
# Draw the nodes
nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts)
# Draw the edges
nx.draw_networkx_edges(GTG, pos=pos, ax=ax, **edge_opts)
# Set the subplot title
ax.set_title(f"{name}\n{GTG.number_of_edges()} edges")
fig.tight_layout()
plt.show()
Мягкие случайные геометрические графы
Мягкие случайные геометрические графы — это разновидность случайных геометрических графов, которые вводят мягкий порог связности вместо жесткого ограничения на основе расстояния. В этих графах узлы по-прежнему расположены случайным образом в геометрическом пространстве, но формирование ребер определяется вероятностной функцией, а не критерием фиксированного расстояния.
В мягком случайном геометрическом графе каждая пара узлов имеет вероятность соединения в зависимости от их расстояния. Функция вероятности обычно уменьшается по мере увеличения расстояния между узлами, отражая идею о том, что узлы, расположенные ближе друг к другу, с большей вероятностью будут связаны.
Точная форма функции вероятности в мягких случайных геометрических графах может варьироваться в зависимости от конкретной используемой модели. Обычно используемые функции включают экспоненциальное затухание, степенное затухание или распределение Гаусса. Эти функции назначают более высокие вероятности парам узлов, расположенным ближе друг к другу, и более низкие вероятности тем парам, которые находятся дальше друг от друга.
# Create a 1x3 grid of subplots
fig, axes = plt.subplots(1, 3)
# Define different PDFs
pdfs = {
"Default": None, # Default: exponential distribution with `lambda=1`
r"$e^{-10d}$": lambda d: math.exp(-10 * d),
"Normal": norm(loc=0.1, scale=0.1).pdf,
}
# Iterate over each PDF and subplot
for (title, pdf), ax in zip(pdfs.items(), axes.ravel()):
# Create a soft random geometric graph with the specified PDF
SRGG = nx.soft_random_geometric_graph(nodes, 0.1, pos=pos, p_dist=pdf)
# Draw the nodes
nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts)
# Draw the edges
nx.draw_networkx_edges(SRGG, pos=pos, ax=ax, **edge_opts)
# Set the subplot title
ax.set_title(f"p_dist={title}\n{SRGG.number_of_edges()} edges")
fig.tight_layout()
plt.show()
Пороговые случайные геометрические графики
Пороговые случайные геометрические графы — это тип модели графа, который сочетает в себе элементы как случайных геометрических графов, так и пороговой обработки. В этих графах узлы случайным образом распределяются в геометрическом пространстве, а ребра формируются на основе порогового расстояния.
Построение пороговых случайных геометрических графов включает в себя два основных параметра: количество узлов, обозначаемое как «n», и пороговое расстояние, обозначаемое как «r». Каждому узлу присваивается случайное положение в геометрическом пространстве, и между двумя узлами создается ребро, если их евклидово расстояние меньше или равно пороговому расстоянию r.
В отличие от традиционных случайных геометрических графов, где все пары узлов на фиксированном расстоянии соединены, случайные геометрические графы с пороговым значением вводят критерий бинарной связности. Узлы либо подключены, либо не подключены в зависимости от порогового расстояния. Это позволяет моделировать сети, в которых соединения устанавливаются только в том случае, если расстояние между узлами ниже определенного порога.
Пороговые случайные геометрические графы обычно используются для моделирования коммуникационных сетей, таких как беспроводные сенсорные сети, где узлы должны устанавливать надежные соединения в пределах определенного диапазона. Установив соответствующее пороговое расстояние, эти графики могут отражать ограничения подключения таких сетей и коммуникационные возможности.
# Create a 1x2 grid of subplots
fig, axes = plt.subplots(1, 2)
# Define the threshold values
thresholds = (0.0001, 0.001)
# Iterate over each threshold value and subplot
for thresh, ax in zip(thresholds, axes):
# Create a thresholded random geometric graph with the specified threshold
TRGG = nx.thresholded_random_geometric_graph(nodes, 0.1, thresh, pos=pos, weight=weight)
# Draw the nodes
nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts)
# Draw the edges
nx.draw_networkx_edges(TRGG, pos=pos, ax=ax, **edge_opts)
# Set the subplot title
ax.set_title(f"Threshold = {thresh}, {TRGG.number_of_edges()} edges")
fig.tight_layout()
plt.show()
Заключение
Пространственные сети служат ценными сетевыми моделями, которые включают пространственные элементы и нашли применение в различных реальных системах. Эти сети характеризуются узлами, встроенными в физическое пространство, и соединениями между ними, определяемыми метрикой, часто основанной на евклидовом расстоянии. Вероятность соединения обычно уменьшается с увеличением расстояния между узлами. Область пространственных сетей была тщательно исследована, что привело к разработке многочисленных моделей с теоретическими доказательствами их сетевых свойств.
