Chapter 7 Network Analysis

Written by Nicholas Martino and Paul Pickell

Networks are abstract structures commonly 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

  1. Understand what networks are and to identify the elements that compose them
  2. Categorize different types of networks according to their topologies
  3. Create spatial networks and learn how to apply them in various applications
  4. 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

7.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. Why abstracting real-world elements into networks can be useful? Network analysis facilitates the study of data sets that demand information about their behaviour in terms of connectivity, flows, direction or paths. This is especially useful to understand the behaviour of complex adaptive systems such as societies, cities, ecosystems, etc. All graphs are composed of two parts: nodes and edges (or links).

7.2 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.

7.3 Edges

Edges (or links), 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.

Figure 7.1: Graph representing connection between Metro Vancouver rapid and frequent transit lines. Interactive figure in the online format of the textbook.

Rapid and frequent transit network in Metro Vancouver [@translink_2020_2020].

Figure 7.2: Rapid and frequent transit network in Metro Vancouver (TransLink 2020).

7.4 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.

7.5 Direct

Directed graphs are networks where the order of elements change relationships between them. We represent directed connections with an arrow. The network below represents relationships between characters of Les Miserables. 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.

Figure 7.3: Example of directed graph for social relationships. Interactive figure in the online format of the textbook.

7.6 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.

7.7 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.

Abstract examples of network topologies [@wikibooks_communication_2018].

Figure 7.4: Abstract examples of network topologies (Wikibooks 2018).

7.8 Physical vs. Logical Topology

In GIS we use networks to represent spatial structures of various kinds. While all networks can be represented in an abstract space - this is, without a defined position in the real-world - some network analysis might be more useful when we attach physical properties to them, such as latitude and longitude coordinates. We call logical topology the study of how network elements are arranged in this abstract space. On the other hand, physical topology refers to the arrangemet of networks in the physical space. We can then classify “types” of networks according to the way their nodes is arranged.

7.9 Non-Hierarchical Topologies

7.9.1 Lines

Lines are when nodes are arranged in series where every node has no more than two connections, except for the two end nodes. A rail transit line, for example, can be represented as a line network. The map below portrays the SkyTrain Millenium Line in Vancouver. Each node represents a stop and the lines the connections between those stops.

Figure 7.5: Rail transit line in Vancouver (City of Vancouver n.d.b). Licensed under the Open Government License - Vancouver.

7.9.2 Rings

Rings are similar to lines except that there are no end nodes. So each and every node has two connections and the “first” and “last” nodes are connected to each other forming a circle. The spatial structure of the Stanley park seawall trail in Vancouver resembles a ring. In this example, nodes stand for intersections and view spots and edges are the connections between these spots along the seawall.

Figure 7.6: Ring of the Stanley Park seawall (City of Vancouver n.d.b). Licensed under the Open Government License - Vancouver.

7.9.3 Meshes

In a mesh, every node is also connected to more than one node. However, in this case nodes can be connected to more than two nodes. Connections in a mesh are non-hierarchical. Contrary to rings and lines where there is only one possible route from one node to another, in a mesh there are multiple routes to access other nodes in the network. A common way to generate a mesh network is using Delaunay triangulation, where nodes are connected in order to form triangles and maximize the minimum angle of all triangles (Wikimedia 2021a). Mesh configurations are commonly used in decentralized structures such as the internet.