Generating Various Types of Graphs by Proximity

This notebook illustrates how to generate and visualize different spatial graph types based on proximity metrics (KNN, Delaunay, Gilbert, Waxman) using City2Graph, OSMnx, and NetworkX.

Overview

This notebook covers:

• Setting up the environment and importing libraries

• Retrieving points of interest around a location

• Defining helper functions for node extraction and plotting

• Generating and visualizing KNN, Delaunay, Gilbert, and Waxman graphs interactively

1. Setup and Environment

import warnings

import contextily as ctx
import matplotlib.pyplot as plt
import networkx as nx
import osmnx as ox
from IPython.display import HTML
from matplotlib import animation

import city2graph

warnings.filterwarnings("ignore")

2. Retrieve Points of Interest

Fetch restaurant POIs around Shibuya, Tokyo using OSMnx and filter to nodes only. Also, streets network is obtained for calculating network distances.

poi_tags = {
    "amenity": [
        "restaurant"]}

#poi_gdf = ox.features_from_place("Shibuya, Tokyo, Japan", poi_tags)
poi_gdf = ox.features_from_point(
    (35.658514, 139.70133),  # Tokyo Tower coordinates
    tags=poi_tags,
    dist=1000,  # Search radius in meters
    )

# Filter to include only nodes, not ways and relations
poi_gdf = poi_gdf[poi_gdf.index.get_level_values("element") == "node"]

# Reproject to a projected CRS for accurate centroids
poi_gdf = poi_gdf.to_crs(epsg=6677)

segments_G = ox.graph_from_point(
    (35.658514, 139.70133),  # Tokyo Tower coordinates
    dist=1000,  # Search radius in meters
    )

segments_gdf = ox.graph_to_gdfs(segments_G, nodes=False, edges=True)

def get_node_positions(gdf):
    """Extract node positions from GeoDataFrame."""
    node_positions = {}
    for id, geom in gdf["geometry"].items():
        if geom.geom_type == "Point":
            node_positions[id] = (geom.x, geom.y)
        else:
            centroid = geom.centroid
            node_positions[id] = (centroid.x, centroid.y)
    return node_positions

def plot_graph(graph,
               title,
               node_positions,
               add_basemap=False,
               crs=None):
    """Plot a network graph with color-coded nodes based on degree centrality."""
    # Compute degree centrality for node coloring
    node_degrees = dict(graph.degree())
    node_colors = [node_degrees.get(node, 0) for node in graph.nodes()]

    # Create the plot
    fig, ax = plt.subplots(figsize=(12, 10))

    # Set equal aspect ratio to maintain map proportions
    ax.set_aspect("equal")

    # Plot the edges with better color
    nx.draw_networkx_edges(graph, pos=node_positions,
                          edge_color="grey",
                          alpha=0.5,
                          width=0.5,
                          ax=ax)

    # Plot the POIs with beautiful color scheme
    nodes = nx.draw_networkx_nodes(graph, pos=node_positions,
                          node_size=30,
                          node_color=node_colors,
                          cmap=plt.cm.plasma,
                          alpha=0.9,
                          linewidths=0.5,
                          ax=ax)

    # Add basemap if requested - with no buffer/margin
    if add_basemap and crs:
        ctx.add_basemap(ax, crs=crs, source=ctx.providers.CartoDB.Positron)

    # Set exact limits based on node positions to avoid any buffer
    node_xs = [pos[0] for pos in node_positions.values()]
    node_ys = [pos[1] for pos in node_positions.values()]
    ax.set_xlim(min(node_xs), max(node_xs))
    ax.set_ylim(min(node_ys), max(node_ys))

    # Add a colorbar with better styling
    cbar = plt.colorbar(nodes, ax=ax, label="Degree Centrality", shrink=0.8)
    cbar.ax.tick_params(labelsize=10)

    plt.title(title, fontsize=14, fontweight="bold", pad=20)
    plt.axis("off")
    plt.tight_layout()
    plt.show()

node_positions = get_node_positions(poi_gdf)

3. K-Nearest Neighbors (KNN) Graph

Create an interactive slider to plot KNN graphs for varying \(k\) values. You can specify the distance metric from "manhattan", "euclidean", and "network". If you use network distance, you need to set the GeoDataFrame of network. You can save the output as GeoDataFrame or nx.Graph.

knn_l1 = city2graph.knn_graph(poi_gdf,
                              distance_metric="manhattan",
                              network_gdf=segments_gdf.to_crs(epsg=6677),
                              as_gdf=True)

knn_l2 = city2graph.knn_graph(poi_gdf,
                              distance_metric="euclidean",
                              network_gdf=segments_gdf.to_crs(epsg=6677),
                              as_gdf=True)

knn_net = city2graph.knn_graph(poi_gdf,
                               k=10,
                               distance_metric="network",
                               network_gdf=segments_gdf.to_crs(epsg=6677),
                               as_gdf=True)

fig, axes = plt.subplots(1, 3, figsize=(18, 6))

# Plot Manhattan distance KNN graph
knn_l1.plot(ax=axes[0], color='red', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[0], color='darkred', markersize=20, alpha=0.8)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title('KNN Graph - Manhattan Distance', fontsize=12, fontweight='bold')
axes[0].set_aspect('equal')
axes[0].axis('off')

# Plot Euclidean distance KNN graph
knn_l2.plot(ax=axes[1], color='blue', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[1], color='darkblue', markersize=20, alpha=0.8)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title('KNN Graph - Euclidean Distance', fontsize=12, fontweight='bold')
axes[1].set_aspect('equal')
axes[1].axis('off')

# Plot Network distance KNN graph
knn_net.plot(ax=axes[2], color='green', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[2], color='darkgreen', markersize=20, alpha=0.8)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title('KNN Graph - Network Distance', fontsize=12, fontweight='bold')
axes[2].set_aspect('equal')
axes[2].axis('off')

plt.tight_layout()
plt.show()

You can obtain the output as nx.Graph object.

knn_l2_G = city2graph.knn_graph(poi_gdf,
                                distance_metric="euclidean",
                                as_gdf=False)

plot_graph(knn_l2_G,
           title="KNN Graph - Euclidean Distance",
           node_positions=node_positions,
           add_basemap=True,
           crs=poi_gdf.crs)

HTML("""
<video controls style="width: 100%; max-width: 800px; height: auto;">
    <source src="../_static/knn_graph.mp4" type="video/mp4">
</video>
""")

5. Delaunay Graph

Generate and plot a Delaunay triangulation graph of the POIs.

del_l1 = city2graph.delaunay_graph(poi_gdf,
                                   distance_metric="manhattan",
                                   as_gdf=True)

del_l2 = city2graph.delaunay_graph(poi_gdf,
                                   distance_metric="euclidean",
                                   as_gdf=True)

del_net = city2graph.delaunay_graph(poi_gdf,
                                    distance_metric="network",
                                    network_gdf=segments_gdf.to_crs(epsg=6677),
                                    as_gdf=True)

plt.ion()

fig, axes = plt.subplots(1, 3, figsize=(18, 6))

# Plot Manhattan distance Delaunay graph
del_l1.plot(ax=axes[0], color='red', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[0], color='darkred', markersize=20, alpha=0.8)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title('Delaunay Graph - Manhattan Distance', fontsize=12, fontweight='bold')
axes[0].set_aspect('equal')
axes[0].axis('off')

# Plot Euclidean distance Delaunay graph
del_l2.plot(ax=axes[1], color='blue', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[1], color='darkblue', markersize=20, alpha=0.8)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title('Delaunay Graph - Euclidean Distance', fontsize=12, fontweight='bold')
axes[1].set_aspect('equal')
axes[1].axis('off')

# Plot Network distance Delaunay graph
del_net.plot(ax=axes[2], color='green', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[2], color='darkgreen', markersize=20, alpha=0.8)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title('Delaunay Graph - Network Distance', fontsize=12, fontweight='bold')
axes[2].set_aspect('equal')
axes[2].axis('off')

plt.tight_layout()
plt.show()

del_l2_G = city2graph.delaunay_graph(poi_gdf,
                                     distance_metric="euclidean",
                                     as_gdf=False)

plot_graph(del_l2_G,
           title="Delaunay Graph - Euclidean Distance",
           node_positions=node_positions,
           add_basemap=True,
           crs=poi_gdf.crs)

6. Gilbert Graph (Hard Threshold Model)

Gilbert Graph is a deterministic model to generate edges based on the Euclidean distance. Given a parameter \(r\) as radious, neighbours are connected if they are within the radious from a node.

gil_l1 = city2graph.gilbert_graph(poi_gdf,
                                  distance_metric="manhattan",
                                  radius=100,
                                  as_gdf=True)

gil_l2 = city2graph.gilbert_graph(poi_gdf,
                                  distance_metric="euclidean",
                                  radius=100,
                                  as_gdf=True)

gil_net = city2graph.gilbert_graph(poi_gdf,
                                   distance_metric="network",
                                   radius=100,
                                   network_gdf=segments_gdf.to_crs(epsg=6677),
                                   as_gdf=True)

plt.ion()

fig, axes = plt.subplots(1, 3, figsize=(18, 6))

# Plot Manhattan distance Gilbert graph
gil_l1.plot(ax=axes[0], color='red', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[0], color='darkred', markersize=20, alpha=0.8)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title('Gilbert Graph - Manhattan Distance', fontsize=12, fontweight='bold')
axes[0].set_aspect('equal')
axes[0].axis('off')

# Plot Euclidean distance Gilbert graph
gil_l2.plot(ax=axes[1], color='blue', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[1], color='darkblue', markersize=20, alpha=0.8)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title('Gilbert Graph - Euclidean Distance', fontsize=12, fontweight='bold')
axes[1].set_aspect('equal')
axes[1].axis('off')

# Plot Network distance Gilbert graph
gil_net.plot(ax=axes[2], color='green', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[2], color='darkgreen', markersize=20, alpha=0.8)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title('Gilbert Graph - Network Distance', fontsize=12, fontweight='bold')
axes[2].set_aspect('equal')
axes[2].axis('off')

plt.tight_layout()
plt.show()

gil_l2_G = city2graph.gilbert_graph(poi_gdf,
                                     distance_metric="euclidean",
                                     radius=100,
                                     as_gdf=False)

plot_graph(gil_l2_G,
           title="Gilbert Graph - Euclidean Distance",
           node_positions=node_positions,
           add_basemap=True,
           crs=poi_gdf.crs)

HTML("""
<video controls style="width: 100%; max-width: 800px; height: auto;">
    <source src="../_static/gilbert_graph.mp4" type="video/mp4">
</video>
""")

7. Waxman Graph (Soft Random Geometry Model)

Waxman graph with adjustable \(r_0\) (r_0) and \(\beta\) (beta) as parameters. The probability of connection follows below:

\[H_{ij} = \beta e^{-\frac{d_{ij}}{r_0}}\]

where \(d_{ij}\) is the Euclidean distance between node \(i\) an \(j\); \(r_0\) is the maximum distance between nodes; and \(\beta\) denotes the scaling parameter.

wax_l1 = city2graph.waxman_graph(poi_gdf,
                                 distance_metric="manhattan",
                                 r0=100,
                                 beta=0.5,
                                 as_gdf=True)

wax_l2 = city2graph.waxman_graph(poi_gdf,
                                 distance_metric="euclidean",
                                 r0=100,
                                 beta=0.5,
                                 as_gdf=True)

wax_net = city2graph.waxman_graph(poi_gdf,
                                  distance_metric="network",
                                  r0=100,
                                  beta=0.5,
                                  network_gdf=segments_gdf.to_crs(epsg=6677),
                                  as_gdf=True)

plt.ion()

fig, axes = plt.subplots(1, 3, figsize=(18, 6))

# Plot Manhattan distance Waxman graph
wax_l1.plot(ax=axes[0], color='red', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[0], color='darkred', markersize=20, alpha=0.8)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title('Waxman Graph - Manhattan Distance', fontsize=12, fontweight='bold')
axes[0].set_aspect('equal')
axes[0].axis('off')

# Plot Euclidean distance Waxman graph
wax_l2.plot(ax=axes[1], color='blue', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[1], color='darkblue', markersize=20, alpha=0.8)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title('Waxman Graph - Euclidean Distance', fontsize=12, fontweight='bold')
axes[1].set_aspect('equal')
axes[1].axis('off')

# Plot Network distance Waxman graph
wax_net.plot(ax=axes[2], color='green', alpha=0.6, linewidth=0.8)
poi_gdf.plot(ax=axes[2], color='darkgreen', markersize=20, alpha=0.8)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title('Waxman Graph - Network Distance', fontsize=12, fontweight='bold')
axes[2].set_aspect('equal')
axes[2].axis('off')

plt.tight_layout()
plt.show()

wax_l2_G = city2graph.waxman_graph(poi_gdf,
                                   distance_metric="euclidean",
                                   r0=100,
                                   beta=0.5,
                                   as_gdf=False)
plot_graph(wax_l2_G,
           title="Waxman Graph - Euclidean Distance",
           node_positions=node_positions,
           add_basemap=True,
           crs=poi_gdf.crs)

HTML("""
<video controls style="width: 100%; max-width: 800px; height: auto;">
    <source src="../_static/waxman_graph.mp4" type="video/mp4">
</video>
""")