{{announcement.body}}
{{announcement.title}}

# Spectral Graph Coordinates in Python

DZone 's Guide to

# Spectral Graph Coordinates in Python

### Spectral coordinates are a natural way to draw a graph because they are determined by the properties of the graph, not arbitrary aesthetic choices. Read on to learn more.

· Web Dev Zone ·
Free Resource

Comment (0)

Save
{{ articles.views | formatCount}} Views

A graph doesn’t have any geometric structure unless we add it. The vertices don’t come with any position in space. The same graph can look very different when arranged different ways.

Spectral coordinates are a natural way to draw a graph because they are determined by the properties of the graph, not arbitrary aesthetic choices. Construct the Laplacian matrix and let x and y be the eigenvectors associated with the second and third eigenvalues. (The smallest eigenvalue is always zero and has an eigenvector of all 1’s. The second and third eigenvalues and eigenvectors are the first to contain information about a graph.) The spectral coordinates of the ith node are the ith components of x and y.

We illustrate this with a graph constructed from a dodecahedron, a regular solid with twelve vertices. You can make a dodecahedron from a soccer ball by connecting the centers of all the white hexagons. Here’s one I made from Zometool pieces for a previous post: Although we’re thinking of this graph as sitting in three dimensions, the nodes being the corners of pentagons etc., the graph simply says which vertices are connected to each other. But, from this information, we can construct the graph Laplacian and use it to assign plane coordinates to each point. And fortunately, this produces a nice picture: Here’s how that image was created using Python’s NetworkX library.

``````import networkx as nx
import matplotlib.pyplot as plt
from scipy.linalg import eigh

# Read in graph and compute the Laplacian L ...

# Laplacian matrices are real and symmetric, so we can use eigh,
# the variation on eig specialized for Hermetian matrices.
w, v = eigh(L) # w = eigenvalues, v = eigenvectors

x = v[:,1]
y = v[:,2]
spectral_coordinates = {i : (x[i], y[i]) for i in range(n)}
G = nx.Graph()

nx.draw(G, pos=spectral_coordinates)
plt.show()``````

Update: After posting this I discovered that NetworkX has a method `draw_spectral` that will compute the spectral coordinates for you.

Related:

Topics:
python ,big data

Comment (0)

Save
{{ articles.views | formatCount}} Views

Published at DZone with permission of John Cook , DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.