Dibujar un gráfico con NetworkX en un mapa base

Quiero trazar una gráfica en un mapa donde los nodos se definirían por coordenadas (lat, long) y tendrían algún valor asociado.

He podido trazar puntos como un diagrama de dispersión en un mapa base, pero parece que no puedo encontrar la forma de trazar una gráfica en el mapa.

Gracias.

EDITAR: Agregué código sobre cómo trazé los puntos en un mapa base. La mayor parte ha sido adaptado de código enesta artículo.

from mpl_toolkits.basemap import Basemap
from shapely.geometry import Point, MultiPoint
import pandas as pd
import matplotlib.pyplot as plt

m = Basemap(
        projection='merc',
        ellps = 'WGS84',
        llcrnrlon=-130,
        llcrnrlat=25,
        urcrnrlon=-60,
        urcrnrlat=50,
        lat_ts=0,
        resolution='i',
        suppress_ticks=True)

# Create Point objects in map coordinates from dataframe lon
# and lat values
# I have a dataframe of coordinates
map_points = pd.Series(
                [Point(m(mapped_x, mapped_y)) 
                 for mapped_x, mapped_y in zip(df['lon'],
                                               df['lat'])])
amre_points = MultiPoint(list(map_points.values)) 

plt.clf()
fig = plt.figure()
ax = fig.add_subplot(111, axisbg='w', frame_on=False)
fig.set_size_inches(18.5, 10.5)

# Create a scatterplot on the map
dev = m.scatter(
            [geom.x for geom in map_points],
            [geom.y for geom in map_points],
            20, marker='o', lw=.25,
            facecolor='#33ccff', edgecolor='w',
            alpha=0.9,antialiased=True,
            zorder=3)

m.fillcontinents(color='#555555')

Me sale esta imagen:

Respuestas a la pregunta(2)

Su respuesta a la pregunta