Пространствените мрежи са мрежови модели, които включват пространствени елементи, където възлите са вградени във физическо пространство и метрика определя връзките между тях. Тези мрежи намират приложения в различни системи от реалния свят като инфраструктурни мрежи (транспортни, електрически, телекомуникационни), социални мрежи и синаптични мрежи. Обикновено вероятността за свързване намалява с увеличаване на разстоянието между възлите, често моделирано с помощта на евклидово разстояние в 2D или 3D пространство. Пространствените мрежи са широко изследвани, което води до множество модели с теоретични доказателства за техните мрежови свойства. Рецензната статия на Марк Бартелеми от 2010 г. предоставя изчерпателен преглед на областта и изследва няколко често срещани модела на пространствена мрежа. Тези модели могат да бъдат класифицирани с помощта на три ключови параметъра и са внедрени в пакета networkx, което улеснява тяхното практическо приложение и анализ.

В тази статия ще използваме мрежата Tesla North American Supercharger като мотивиращ пример, за да демонстрираме приложението на различни пространствени мрежови модели, налични в пакета networkx. „Данните за Supercharger“, включващи 385 отворени Superchargers в Канада и Съединените щати към април 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()

Заключение

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