Chapter 8 Network Analysis
Networks are abstract structures used to represent patterns of relationships among sets of various “things” (Ajorlou 2018). Such structures can be used to represent social connections, spatial patterns, ecological relationships, etc. In GIS, the elements that compose geospatial networks are geolocated – in other words: they have latitude and longitude values attached to them. Network analysis encompasses a series of techniques used to interpret information from those networks. This chapter introduces basic concepts for building, analyzing and applying spatial networks to real-world problems.
Learning Objectives
By the end of the chapter, students will be able:
- To understand what networks are and to identify the elements that compose them;
- To categorize different types of networks according to their topologies;
- To create spatial networks and learn how to apply them in various applications;
- To extract relevant information from spatial networks about the relationship between their elements, such as routes, distances and centralities.
Key Terms
Network analysis, Spatial networks, Graph theory
8.1 Introduction to graph theory
Graphs are the abstract language of networks (Systems Innovation 2015a). Graph theory is the area of mathematics that study graphs. By abstracting networks into graphs, one is able to measure different kinds of indicators that represents information about relationships that exist within a certain system. This is especially useful to assess the state of complex adaptive systems such as societies, cities, ecosystems, etc. All graphs are composed of two parts: nodes and edges.
8.1.1 Nodes
A node (or vertex) may represent any thing that can be connected with other things. For example, it can represent people in social networks, street intersections in road networks, or chemical compounds in molecular networks, among others.
8.1.2 Edges
Edges, on the other hand, represent how vertices are interconnected to each other. So it may represent the vertices’ social connections, street segments, molecular bindings, etc. The graph below represents rapid and frequent transit lines in Metro Vancouver. Each node represents a transit line and the edges represents connections between those lines.
Graph representing Metro Vancouver rapid and frequent transit network
.(images/metro_vancouver_transit_network.jpeg){.center}
8.2 Connectivity and order
There are two major types of connections within the graphs: directed and undirected. Connections are directed when they have a specific node of origin and destination.
8.2.1 Direct
Directed graphs are networks where the order of elements change relationships between them. We represent directed connections with an arrow. For example, in the case of the transit network we could use a directed graph to represent the path one has to take in order to shift from one line to another.
8.2.2 Undirect
On the other hand, in an undirected graph, connections are represented as simple lines instead of arrows. The order of elements does not matter.
8.3 Network topologies
Topology is the study of how network elements are arranged. The same elements arranged in different ways can change the network structure and dynamics. A very common example is the arrangement of computer networks (Wikibooks 2018).
8.3.1 Physical versus logical topology
8.3.2 Lines
Nodes are arranged in series where every node has no more than two connections. (Example: Skytrain transit line)
8.3.3 Rings
Every node has no mode than two connections and the “first” and “last” nodes are connected to each other forming a circle. (Example: Stanley park seawall trail)
8.3.4 Meshes
Every node is connected to more than one node. (Example: Tree canopy)
8.3.5 Stars
Two or more nodes arranged around a central node. (Example: Courtyard apartment)
8.3.6 Trees
Nodes are structured from a root node arranged into a number of smaller nodes. (Example: Boat marinas)
8.3.7 Buses
Nodes are structured with one connection around a central path. (Example: Building-street connections)
8.3.8 Fully connected
Every node is connected to every other node. (Example: Soccer field visibility)
8.4 Spatial Network Analysis
8.4.1 Network tracing
8.4.2 Linear referencing
(Ramsey 2012).
8.4.3 Routing
8.4.4 Least cost paths
8.4.5 Least cost corridors
8.5 Network Centrality
(Ajorlou 2018).
8.5.1 Degree centrality
The number of connections of each node.
8.5.2 Closeness centrality
How close the node is to every other node of the graph in logical distance.
8.5.3 Betweenness centrality
How likely a node is to be passed through when going from every node to every other node of the graph.