Network Analysis

Practicalities of network analysis

Thinking outside the map with networks

Key ideas in network analysis

“In short, our argument for a new science is based on the notion that to understand place, we must understand flows, and to understand flows we must understand networks.”

Batty 2013, The New Science of Cities, 2-3

Graph measures

(i) path length centrality, (ii) betweenness centrality, (iii) communities (or clusters).
Source: Andris C, D O’Sullivan. 2019. Spatial Network Analysis In Handbook of Regional Science eds. MM Fischer & P Nijkamp. Berlin, Heidelberg: Springer.

Centrality using a space syntax axial graph

Community detection regionalization of the U.S. based on ACS commuter flows

Source: Dash Nelson G and A Rae. 2016. An Economic Geography of the United States: From Commutes to Megaregions. PLOS ONE 11(11):e0166083.

source complexification.net
by Jared Tarbell

Defining networks

Mathematicians consider graphs $$G=\{V,E\}$$ where $V$ is a collection of vertices, and
$E$ is a collection of edges

Vertices

Vertices (or nodes), can be anything of interest

Bus stops, airports, cities, people, buildings, firms, proteins, etc.

A lot of early work was done with social networks where each vertex represents a person

Edges

Edges are pairs of vertices, $E=\{e_{ij}\}$ that exist where there is some relation between vertex $v_i$ and vertex $v_j$

Again, what edges represent is quite open: the existence of a connection, friendship, regular scheduled flight, trade flow, immigration flow, communications link, etc.

Refinements are possible

Edges may be directed ($e_{ij}\ne e_{ji}$), or undirected ($e_{ij}\equiv e_{ji}$)

Edges may be weighted, in which case some weight $w_{ij}$ is associated with each edge, denoting its strength, or length, or capacity, or some other attribute of interest

Self-loops $e_{ii}$ may be permitted or not depending on context

Formats

Graphs show up in all kinds of data formats

Dense networks may be stored as an adjacency matrix $$ \left[\begin{array}{rrrrr} 1 & 2 & 7 & 23 \\ 3 & 2 & 3 & 9 \\ 4 & 0 & 2 & 13 \\ 1 & 7 & 7 & 0 \end{array}\right] $$

Most networks are sparse so that lots of matrix entries would be zeros, when it is more efficient to store an edge list

Network analysis in GIS

Essentially all operations on networks provided in GIS are based on shortest paths

Dijkstra’s algorithm

Edsger W. Dijkstra, 2002 commons.wikimedia.org by Hamilton Richards

Set distance to source to 0 and mark it known

Set distance to other nodes to $\infty$ and mark them unknown

While there any nodes still unknown:

Get the unknown node $u$ with lowest distance

Mark it known, then:

For each unknown node $v$ connected to $u$:

If (current distance to $u$ + distance from $u$ to $v$) is less than (current distance to $v$) then update distance to $v$ to this value

Extras

Storing the ‘previous’ node from which shortest path connection was made to allows back-tracing of any required shortest path

Often, heuristics are applied to narrow the search, for example not allowing the shortest path to deviate too far from a straight line connecting source and target nodes

A popular alternative algorithm is called A*

Armed with shortest path...

Driving routes

Allocation of customers to facilities

Service area calculation

Most of the work...

... is in building and maintaining datasets

In a street network: nodes=intersections, edges=street segments

You get these from a line layer

Although... it’s not really that simple...

What about: lanes? one-ways? turn restrictions? speed limits? traffic lights? crossings? bridges? etc.

Finally, some food for thought

From this

To this

For more on these lines see

Bergmann LR and D O’Sullivan. 2018. Reimagining GIScience for relational spaces. The Canadian Geographer / Le Géographe canadien. 62(1) 7-14.

O’Sullivan D, LR Bergmann, and JE Thatcher. 2018. Spatiality, maps, and mathematics in critical human geography: toward a repetition with difference. The Professional Geographer 70(1) 129-139.

Network Analysis

Key ideas in network analysis

What is a network?

Practicalities of network analysis

Thinking outside the map with networks

Key ideas in network analysis

“In short, our argument for a new science is based on the notion that to understand place, we must understand flows, and to understand flows we must understand networks.”

Batty 2013, The New Science of Cities, 2-3

Graph measures

Centrality using a space syntax axial graph

Community detection regionalization of the U.S. based on ACS commuter flows

Source: Dash Nelson G and A Rae. 2016. An Economic Geography of the United States: From Commutes to Megaregions. PLOS ONE 11(11):e0166083.

Defining networks

Mathematicians consider graphs $$G=\{V,E\}$$ where \(V\) is a collection of vertices, and \(E\) is a collection of edges

Vertices

Vertices (or nodes), can be anything of interest

Bus stops, airports, cities, people, buildings, firms, proteins, etc.

A lot of early work was done with social networks where each vertex represents a person

Edges

Edges are pairs of vertices, \(E=\{e_{ij}\}\) that exist where there is some relation between vertex \(v_i\) and vertex \(v_j\)

Again, what edges represent is quite open: the existence of a connection, friendship, regular scheduled flight, trade flow, immigration flow, communications link, etc.

Refinements are possible

Edges may be directed (\(e_{ij}\ne e_{ji}\)), or undirected (\(e_{ij}\equiv e_{ji}\))

Edges may be weighted, in which case some weight \(w_{ij}\) is associated with each edge, denoting its strength, or length, or capacity, or some other attribute of interest

Self-loops \(e_{ii}\) may be permitted or not depending on context

Formats

Graphs show up in all kinds of data formats

Dense networks may be stored as an adjacency matrix $$ \left[\begin{array}{rrrrr} 1 & 2 & 7 & 23 \\ 3 & 2 & 3 & 9 \\ 4 & 0 & 2 & 13 \\ 1 & 7 & 7 & 0 \end{array}\right] $$

Most networks are sparse so that lots of matrix entries would be zeros, when it is more efficient to store an edge list

Network analysis in GIS

Essentially all operations on networks provided in GIS are based on shortest paths

Dijkstra’s algorithm

Set distance to source to 0 and mark it known

Set distance to other nodes to \(\infty\) and mark them unknown

While there any nodes still unknown:

Get the unknown node \(u\) with lowest distance

Mark it known, then:

For each unknown node \(v\) connected to \(u\):

If (current distance to \(u\) + distance from \(u\) to \(v\)) is less than (current distance to \(v\)) then update distance to \(v\) to this value

Extras

Storing the ‘previous’ node from which shortest path connection was made to allows back-tracing of any required shortest path

Often, heuristics are applied to narrow the search, for example not allowing the shortest path to deviate too far from a straight line connecting source and target nodes

A popular alternative algorithm is called A*

Armed with shortest path...

Driving routes

Allocation of customers to facilities

Service area calculation

Most of the work...

... is in building and maintaining datasets

In a street network: nodes=intersections, edges=street segments

You get these from a line layer

Although... it’s not really that simple...

What about: lanes? one-ways? turn restrictions? speed limits? traffic lights? crossings? bridges? etc.

Finally, some food for thought

From this

To this

For more on these lines see

Bergmann LR and D O’Sullivan. 2018. Reimagining GIScience for relational spaces. The Canadian Geographer / Le Géographe canadien. 62(1) 7-14.

O’Sullivan D, LR Bergmann, and JE Thatcher. 2018. Spatiality, maps, and mathematics in critical human geography: toward a repetition with difference. The Professional Geographer 70(1) 129-139.

Mathematicians consider graphs $$G=\{V,E\}$$ where \(V\) is a collection of vertices, and
\(E\) is a collection of edges