Network analysis
Petr Kubíček
kubicek@geogr.muni.cz
Laboratory on Geoinformatics and Cartography (LGC)
Institute of Geography
Masaryk University
Czech Republic
The importance of networks
• Networks are all around us.
• The techniques have been developed to analyse
these most geographical phenomena. 2Friday, 07 April 2017
Data requirements for network
analysis
Data requirements (Clausen 1991, road analysis):
• Accurate
• Up to date
• Topologically correct
• Attributes:
– road conditions
– classification
– speed restrictions
– one way streets
– turning restrictions
– width and height restrictions
– junctions
– roundabouts
– reference landmarks
Networks and GIS
Cost:
• What is the impact of an object
flowing through the network?
• Types
-Time
-Distance
• Based on connectivity, flow, and
rules
Network characteristics –
formal description
• A network can be defined as a set of linear features
through which resources flow.
• A network is referred to as a pure network if only
its topology and connectivity are considered.
• If a network is characterised by its topology and
flow characteristics (such as capacity constraints,
path choice and link cost functions) it is referred to
as a flow network.
• A transportation network is a flow network
representing the movement of people, vehicles or
goods (Bell and Iida, 1997).
Nodes and links
Building stones - nodes (the end points of lines)
are used as origins and destinations, and links
(lines) travers from one node to the other.
A classification of networks (adapted from Laurini
& Thompson, 1992).
Directed links are referred to as arcs while
undirected links as edges.
Which one fits for
the river network?
Network data model -
conceptual
• A data model is an abstract representation of
some real-world situation used to organise
data in a database.
• three different levels of abstraction:
conceptual, logical and physical levels.
• The entity-relationship and the extended entityrelationship
models are the most widely used
conceptual data models.
• The network data model (vector) is built around
two core entities: the Node (a zero-dimensional
entity) and the Arc (a one dimensional entity).
Network data model - logical
• logical data model that supports the node-arc
representation of networks is the georelational
model.
• separates spatial (geometry) and attribute
data into different data models.
Arc – node data
model
Connectivity and planar
networks
• standard fully intersected planar network data
model has been extended by adding a new
structure, called the turn-table – node rules.
Turn table examples
Barriers
Barrier represents certain limitations within the
network. Different geometry types – point, line, polygon
• Restrictions
(complete closures of
the street/road
segment),
• Scaled cost (traffic
lights, one way
closure, traffic
accident, traffic signs).
Horák a kol. 2015
Barriers and
shortest path
Data for network analysis
• ZABAGED, OpenStreetNet,
JSDI
• StreetNet (CEDA) –
updated 2x year; seamless
and fully routable road
network supplemented
by additional topographic
layers and layers of
administrative boundaries.
• Road DB – its descriptive
information (number,
international number and
class of the road, street
name etc.), attributes
describing technical and
functional state of
individual segments and
basic attributes for
movement on the network.
Street Net sample
Streetnet
ZABAGED
Horák a kol. 2015
Street Net
selection
of roads
Real Time data for network
analysis
• Rodos http://rodos.vsb.cz/
• Dynamic Mobility Model (DMM) integrating the
movement of persons, vehicles, and goods.
Detail view on Brno with traffic
delays
Algorithms for network
operations
• Search procedure – alternations - no
turning back, fewest number of
nodes, minimum cost.
• A common question is "what is the
shortest path?„ - Dijkstra algorith,
mathematically designed to find the
lowest cost route between two locations
when a measure of cost is attached to
each link.
• Simplification - one way, no loops.
Dijkstra algorithm I
Task: find the shortest path between an origin (A) and
a destination (G). Trial and error method 
Dijkstra algorithm II
• List all the nodes of the graph that link directly to the
starting node and label each link with its cost value.
Dijkstra algorithm III
Find the node with the lowest link value and label the node
with this value. This is the lowest cost path between the origin
and this node.
Dijkstra algorithm IV
Extend the search from this node. Brown and green lines.
Dijkstra algorithm V
• Find the node with the lowest cumulative cost and label the
node with this value.
• If there is more than one node that has been reached in
the same cumulative cost so we label them both
Dijkstra algorithm VI
• Extend the search again. Add new linked nodes to the list of
nodes and calculate the cumulative cost to each.
Dijkstra algorithm VII
Node G is reached from B which is reached from A
i.e. shortest path = A B G.
the node with the lowest cumulative
cost
Applications of network
analysis
• Routing - Finding shortest routes is probably the
commonest routing problem to occupy GIS users.
Finding the shortest route from A to B through a
road network is crucial for emergency services,
business journeys, or simply planning routes for
holiday makers touring a region.
• Service area - The objective is to create service
areas around a centre and optimise the distribution
of the resources based on the capacity of each
facility.
Isochrones
• 15 – 60 min
Finding Service Areas Using
ArcGIS Network Analyst
• Create Isochrone Maps – How Far Can Firefighters
Service?
• that each facility will have it’s own service area –
or extent for how far firefighters can reach in a
given amount of time (isochrone).
• different scenarios – including setting up lengths
and time.
What You Will Need
• Network Analyst Extension
• Road Network – topologically correct.
• Facilities Layer (Fire stations, police stations,
hospitals, etc)
Start new Service area
Adding facilities
• Load facilities point
data
• Visualize and check
for errors
Service area problem set up
Variables:
• Impedance
• Breaks (m,
min)
• Direction
Polygon generation table option
Line generation options – the use of
linear referencign system.
Generate the service area
polygons and lines/road
segments
Using bariers
Transportation of dangerous goods –
case study (Leitgeb 2015)
• Goal: Minimise the potential impact on
inhabitants during the transportation of
dangerous substances (flammable,
explosive…).
• ADR classification, Police and army internal
legislation.
• Alternative criterion:
– Population concentration based on street/road
segments;
– Buildings (POIs) with high concentration of
inhabitants and sensitive objects.
Criterion 1 – street segments
Criterion 2 – sensitive objects
and PoI
• A- shortest
path
• B – criterion 1
• C – criterion 2