In this tutorial, we’ll explore the geometric network generator modelsimplemented under `networkx/generators/geometric.py`

and apply themto a real-world use case to learn how these models can be parameterized and used.

## Import packages#

%matplotlib inlineimport numpy as npimport matplotlib.pyplot as pltimport networkx as nx

## Geometric/Spatial Networks#

Many real-world complex systems have spatial components constraining thenetwork structures these types of systems can produce.Infrastructure networks such as transportation, electrical, andtelecommunication systems, social networks and even our own synaptic networksare all embedded in physical space.Spatial Networks provide a framework for network models having spacial elementswhere nodes are embedded in space and a metric is incorporated that dictatesthe conditions for connection between nodes.Typically, the probability of connection is a decreasing function of themetric, with most models assuming Euclidean distance in 2-dimensions or 3-dimensions.The intuition of most Spatial Network models propose that there exists anincreasing cost of connection between nodes that are further apart, thougharbitrary connection probability functions can be modeled.

The potential application of Spatial Networks to such a wide variety ofreal-world systems has motivated substainial research into these networks,with many unique but closely related models being proposed with theoreticalproofs for many of their network properties.The 2010 Spatial Networks review article by Marc Barthélemy [1] provides acomprehensive overview of the field and reviews many of the most importanttheoretical proofs for the most common Spatial Network models.Here we explore some of the most typical Spatial Network models which have beenimplemented in the networkx package.These models can be classified using only three model parameters used by thesedifferent models:

\(R\) - The maximum connection distance, the

`radius`

parameter in networkx\(P(d_{ij})\) - The probability of edge connection as a function of thedistance, \(d_{ij}\), between nodes \(i, j\) where \(i \neq j\), the

`p_dist`

parameter in networkx\(\theta\) - The node weight threshold for connection, the

`theta`

parameterin networkx

Typically, nodes are uniformly distributed onto the unit square and node weightsare sampled from some weight distribution.Distance, \(d_{ij}\) is typically assumed to be the Euclidean distance,but some networkx models allow custom metrics where others only allow Minkowskidistance metrics.

The figure below shows the relationships between Spatial Network Modelsconnected by their shared parameterization.

### Individual Model Definitions#

This section summarizes the various models. The notation \(E_{ij}\)indicates an edges exists between nodes \(i\) and \(j\).

#### Random Geometric Graphs (\(R\))#

A d-dimensional Random Geometric Graph (RGG) is a graph where each of the \(N\)nodes is assigned random coordinates in the box \([0, 1]^{d}\), and onlynodes “close” to each other are connected by an edge [2].Any node within or equal to the maximum connection distance, \(R\), is a connectednode and the structure of the network is fully defined by \(R\).RGGs, similar to Unit Disk Graphs [3], have been widely used to model ad-hocwireless networks.

\[ E_{ij}: d_{ij} \leq R \]

#### Waxman Graphs (\(\alpha\))#

Waxman Graphs are the spatial generalization of Erdős–Rényi random graphs, where theprobability of connection of nodes depends on a function of the distance between them[4].The original edge probabiliy function proposed by Waxman is exponential in\(d_{ij}\), providing two connection probability tuning parameters, \(\alpha\) and \(\beta\):

\[ P(d_{ij}) = \beta e^{\frac{-d_{ij}}{L \alpha}} \]

Where \(L\) is the maximum distance between each pair of nodes.

The shape of the edge probabiliy function, \(P(d_{ij})\), plays the key rolein determining the structure of a Waxman graph, but characterization of\(P(d_{ij})\) in real-world networks still seems controversial.The most commonly studied functional families are the orginal exponential above,or power laws, \(-{d_{ij}}^{-\alpha}\).

\[ E_{ij} \propto P(d_{ij}) \]

#### Threshold Graphs (\(\theta\))#

A simple graph G is a threshold graph if we can assign weights to the verticessuch that a pair of distinct vertices is adjacent exactly when the sum of theirassigned weights equals or exceeds a specified threshold, \(\theta\) [6].Threshold Graphs are not themselves Spatial Networks, as they do not incorporatea specific geometry or metric, but they introduce the ability to consider nodeweights as part of the network model which is utilized by other Spatial Networkmodels such as Geometric Threshold Graphs.

\[ E_{ij}: (w_i + w_j) \geq \theta \]

#### Geographical Threshold Graphs (\(P(d_{ij}), \theta\))#

Geographical Threshold Graphs are the geographical generalization of ThresholdGraphs, where a pair of vertices with weights \(w_i, w_j\),and distance \(d_{ij}\) are connected if and only if the product betweenthe sum of weights \(w_i\) and \(w_j\) with the edge connectionfunction, \(P(d_{ij})\), is greater than or equal to a threshold value, \(\theta\). [8]

\[ E_{ij}: (w_i + w_j) P(d_{ij}) \geq \theta \]

#### Soft Random Geometric Graphs (\(R, P(d_{ij})\))#

A recent extention of Random Geometric Graphs couples the influence of distancebetween nodes that are within the maximum connection distance, \(R\), to better modelreal-world systems where node proximity does not necessarily guarantee aconnection between “close” nodes.In Soft Random Geometric Graphs, the probability of connection between nodes \(i\)and \(j\) is a function of their distance, \(d_{ij}, if \)d_{ij} \leq R$.Otherwise, they are disconnected [7].

\[ E_{ij} \propto P(d_{ij}) \textrm{ if } d_{ij} \leq R \]

#### Thresholded Random Geometric Graphs (\(R, \theta\))#

Thresholded Random Geometric Graphs extend RGGs to incorporate node weights intothe model, where connections are only made between nodes with sufficientlypowerful weights, up to a maximum connection distance between nodes [9].

\[ (w_i + w_j) \geq \theta \textrm{ if } d_{ij} \leq R \]

### A Motivating Example#

For this tutorial, we’ll use the Tesla North American Supercharger network tohighlight how the various spatial network models implemented in networkx canbe parameterized and used.

The Supercharger data is obtained from supercharger.info, filtered for theCanadian and American Supercharger locations, totaling 385 Opened Superchargersas of April 2017.The collected data has been structured into a Networkx Graph which is made up ofnested dictionaries keyed on the geohash of each Supercharger’s GPS coordinateswhich have been converted into a projected embedding onto the unit square.Node weights are the population of cities for each Supercharger, as a percentof total North American population.With this dataset, we can model the supercharger network with the various spatialnetworks implemented in networkx.

# Some matplotlib settingsmpl_params = { "axes.titlesize": 20, "figure.figsize": (12, 4),}plt.rcParams.update(mpl_params)

Next, we load the data and construct the graph.

# from networkx.readwrite import json_graphimport json# load json-ed networkx datafilewith 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

# example node data structure keyed on geohash of GPS cordsG.nodes["dr7k46ycwwb8"]

{'SC_index': 173, 'geohash': 'dr7k46ycwwb8', 'weight': 0.00014093906625032375, 'GPS_lon_lat': [-74.07126104459167, 41.49977498687804], 'lat': 41.49977498687804, 'lon': -74.07126104459167, 'population': 28101, 'pos': [0.8123107474668945, 0.42622282744786055], 'GPS': [41.49977498687804, -74.07126104459167]}

# extract pos and weight attributes for use in modelsnodes = G.nodes()pos = nx.get_node_attributes(G, "pos")weight = nx.get_node_attributes(G, "weight")

Since we’ll be visualizing a lot of graphs, let’s define some generalplotting options for consistent visualizations.

node_opts = {"node_size": 50, "node_color": "r", "alpha": 0.4}edge_opts = {"edge_color": "k"}

## Random Geometric Graphs#

For RGGs, we see the impact of increasing the maximum connection distanceparameter `radius`

in increasing the number of connections.

fig, axes = plt.subplots(2, 2, figsize=(12, 8))# Params for visualizing edgesalphas = (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)for r, ax, alpha, lw in zip(radii, axes.ravel(), alphas, linewidths): RGG = nx.random_geometric_graph(nodes, radius=r, pos=pos) nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts) nx.draw_networkx_edges(RGG, pos=pos, ax=ax, alpha=alpha, width=lw, **edge_opts) ax.set_title(f"$r = {r}$, {RGG.number_of_edges()} edges")fig.tight_layout()

# Make edge visualization more prominent (and consistent) for the following# examplesedge_opts["alpha"] = 0.8edge_opts["width"] = 0.2

## Geographical Threshold Graphs#

The GTG model allows for a wide range of custom parameters including custom nodepositioning, weights, and a metric between nodes and the probability of connection,\(P(d_{ij})\).The default \(P(d_{ij})\) model is the metric value, \(r\), for the two connectingnodes raised to the \(-\alpha\) parameter, which has a default value of 2.

fig, axes = plt.subplots(1, 2)# Custom distance metricdist = lambda x, y: sum(abs(a - b) for a, b in zip(x, y))distance_metrics = { "Default (Euclidean) distance metric": None, # Euclidean distance "Custom distance metric": dist,}for (name, metric), ax in zip(distance_metrics.items(), axes.ravel()): GTG = nx.geographical_threshold_graph( nodes, 0.1, pos=pos, weight=weight, metric=metric ) nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts) nx.draw_networkx_edges(GTG, pos=pos, ax=ax, **edge_opts) ax.set_title(f"{name}\n{GTG.number_of_edges()} edges")fig.tight_layout()

fig, axes = plt.subplots(1, 2)# Evaluate different p_distsimport mathfrom scipy.stats import normp_dists = { "p_dist=Exponential": lambda d: math.exp(-d), "p_dist=Normal": norm(loc=0.1, scale=0.1).pdf,}for (name, p_dist), ax in zip(p_dists.items(), axes.ravel()): GTG = nx.geographical_threshold_graph( nodes, 0.01, pos=pos, weight=weight, metric=dist, p_dist=p_dist ) nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts) nx.draw_networkx_edges(GTG, pos=pos, ax=ax, **edge_opts) ax.set_title(f"{name}\n{GTG.number_of_edges()} edges")fig.tight_layout()

## Soft Random Geometric Graphs#

SRGGs utilize the maximum connection distance parameter, \(R\), of RGGs but providethe ability to input an arbitrary connection probability function, \(P(d_{ij})\),for nodes within the maximum connection distance.The default \(P(d_{ij})\) function for SRGGs in networkx is an exponentialdistribution with rate parameter `lambda=1`

.

fig, axes = plt.subplots(1, 3)pdfs = { "default": None, # default: exponential distribution with `lambda=1` r"$e^{-10d}$": lambda d: math.exp(-10 * d), "norm": norm(loc=0.1, scale=0.1).pdf,}for (title, pdf), ax in zip(pdfs.items(), axes.ravel()): SRGG = nx.soft_random_geometric_graph(nodes, 0.1, pos=pos, p_dist=pdf) nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts) nx.draw_networkx_edges(SRGG, pos=pos, ax=ax, **edge_opts) ax.set_title(f"p_dist={title}\n{SRGG.number_of_edges()} edges")fig.tight_layout()

## Thresholded Random Geometric Graphs#

TRGGs allow for the coupling of the maximum connection distance and threshold parameters.The default weights for TRGG are drawn from an exponential distribution withrate parameter `lambda=1`

.

fig, axes = plt.subplots(1, 2)# Increased threshold parameter, theta, reduces graph connectivitythresholds = (0.0001, 0.001)for thresh, ax in zip(thresholds, axes): TRGG = nx.thresholded_random_geometric_graph( nodes, 0.1, thresh, pos=pos, weight=weight ) nx.draw_networkx_nodes(G, pos=pos, ax=ax, **node_opts) nx.draw_networkx_edges(TRGG, pos=pos, ax=ax, **edge_opts) ax.set_title(f"Threshold = {thresh}, {TRGG.number_of_edges()} edges")fig.tight_layout()