The Banbury projectSpectral clustering of Banbury's streets: 2,747 junctions, one eigenvector
Build the graph, compute the Fiedler vector, cut where it changes sign, and compare with simpler cuts.
One Overpass request returns the roads in a box around Banbury, from trunk roads down to residential streets, along with the railway lines, rivers and canals. The learner keeps the largest connected road network, 229.7 km of it, and simplifies it to the places where roads meet or end: 2,747 junctions joined by 3,129 links. From that comes the Laplacian matrix, a table with one row per junction that records how many links each junction has and which junctions it touches. Its eigenvector for the second-smallest eigenvalue is the Fiedler vector. Junctions that are well connected to each other receive similar values, and the values drift from negative on one side of the network to positive on the other.
Ways of splitting Banbury's street graph in two, our Python run on OpenStreetMap data| How the split was made | Junctions on each side | Links cut |
|---|
| Fiedler vector, by sign | 1,515 and 1,232 | 12 |
| Fiedler vector, at its median | 1,373 and 1,374 | 12 |
| Straight line, east and west halves | 1,373 and 1,374 | 27 |
| Straight line, north and south halves | 1,373 and 1,374 | 44 |
| Random halves | 1,349 and 1,398 | 1,535 |
The spectral split severs 12 links out of 3,129. A ruler-straight cut through the middle of the map severs 27 one way and 44 the other, and picking junctions at random breaks about half of all links. The eigenvector knows nothing about geography; it was given only the list of which junction connects to which, and it still found a line through the network far thinner than the obvious ones. The second-smallest eigenvalue itself, 0.00035, is a measure of how weakly the two sides hold together: the closer to zero, the easier the network is to pull apart.
Here is the part the learner usually gets wrong in advance. Most people guess the cut will follow the railway, the river or the canal. We checked. Only 14 road links in the box cross one of those three, and not one of the 12 links in the spectral cut is among them. Removing all 14 crossings does separate the network, but into very unequal parts of 2,289 and 409 junctions. The method is looking for balance as well as a small cut, so it passed over the visible barrier and chose a different, less obvious seam. A prediction was made, tested against data and found wrong, which is how the project is meant to go.
Ages 8 to 11
On a drawn network of dots and lines, find the fewest lines to snip to make two equal teams.
Ages 11 to 15
Build a small graph in Python, try straight-line and random splits, and count the broken links.
Ages 15 and up
Form the Laplacian with NumPy, compute the Fiedler vector and test the railway guess on the real graph.
Map data credit and caveats
Roads, railways and waterways are © OpenStreetMap contributors, under the Open Database Licence. The graph, the eigenvector and the counts are our work. The network ends at the edge of our box and omits the motorway, and a different box would give different numbers. Nothing here describes a real plan or boundary.
