The Network and Graph
Transportation is an essential aspect of planning at every scale. The main motive behind the study is to find a way to connect one place to another, and every place to every other often referred to as connectivity. This is achieved by creating a network. We use these road, rail, cycle, bus and numerous other networks, to reach our destinations. Conventional transportation studies heavily deal with data from TVC, Origin-Destination and other survey data. Another aspect in this study is Mathematical side, where we use mathematical tools to analyse the Network. This is where Graph theory and Indices come in.
Graph theory is a branch of mathematics concerned about how networks can be encoded and their properties measured. A graph of a network is the abstraction of network which is topologically identical to actual network, with all the properties of network embedded in it. This embedding is done on the two elements that form the graph: nodes/vertices and links/edges. Hence Graph G is as well represented by: G (v, e)
A Node or vertex is a terminal point or an intersection point on a graph. It is the abstraction of a location such as a city, an administrative division, a road intersection, a dead end or a transport hub which connect to another network (stations, terminals, harbours and airports) depending on the scale. We can embed the altitude, the volume, or any other location specific data into the node.
An edge e is a link between two nodes. A link is the abstraction of a transport infrastructure supporting movements between nodes. Edge is represented by where I & j are the two nodes the link connects. We can embed length, directionality, resistance (speed limits, filtered permeability, slope) or any other infrastructure related data into the link.
Other Important Terms
- Sub Graph: It’s a subset of Graph. Every Graph is a sub-graph of itself (similar to every set is subset to itself). No. of Sub graphs is denoted by “p“
- Planar Graphs: A graph where all the intersections of two edges are a vertex. Hence, it’s a 2D graph with no 3rd dimension. Country side roads, without any flyovers, or power lines where every intersection is a Node
Non-Planar Graphs: A Graph, where at least 2 edges intersect without forming a vertex. E.g.: A Flyover, where Roads do overlap each other, but don’t intersect to form junction.
Network Level Indices:
To analyse the network, there are numerous Indices that are used at different levels. Few of them here are discussed, which can be easily found through GIS, without the need for any programming. However, there are a few more that are mentioned in the end, which will require you to get into Python, or R where you can model the entire Network and get the results. These indices Look at Network as whole to give out the analysis. These are usually used to compare different Graphs.
Finding Basic Information From GIS
Make sure you have digitised the entire network/links along with intersection/nodes and cleaned it along with marking the study area. You can then easily find the following from GIS:
- Nodes / edges
- Use select by location, to select all nodes/edges in the network that intersect with the Study area.
- Find the number of selected nodes from attribute table
- Total Network Length (L) / Study Area
- In the attribute table of the network/study area, in an empty field, calculate geometry to find length/area
- Summaries the Field in attribute table to get the total Road length (L)/Study Area
Network Density (ND):
Network density measures the territorial occupation of a transport. It is the length of the network per unit area. The higher the network Density, the more the network is developed. It is simply given by the formula:
Consider the above networks, where the road network for a 200m X 200m area. the ND for a smaller block sized grid is higher, but ND alone cannot give a complete picture of the network. both A and C have same ND but are very different. while A&B are found in plain areas, networks such as C can be found in hilly regions. To give a clearer idea, need a few more indices.
Advanced Exploration: By creating a Fishnet on study area, and using Spatial join to sum the road lengths in every cell, you can visualize the ND throughout the study area, and even see how it has changed for in the area over time if historic data is available
Eta Index (η)
Eta index gives the average link length. Complex networks will tend to have a lower eta value. one can as well imagine it as how frequently a node will appear on average. it is given by the formula:
For arterial roads, you would want to keep high Eta index, to allow smoother flow of traffic. Also, a reason why we see overpasses over intersections. However, for a busy, walkable neighbourhood, it’s important for eta index to be lower, not only allowing pedestrians more options for movement, but significantly reducing traffic speeds too. You can now as well see why typical American suburbs with dead ends are not as walkable compared to the traditional city centres.
For the graphs A and B, the eta index is same as the block size in grid. higher the grid sizes tend to reduce walkability. However, for Graph D, Eta index as increased by adding a flyover over the intersection. Further, for suburbs in Graph E, you can see the eta index is even higher. if, however, the collector road, had Cul-de-sacs on both sides, the Eta index reduces but still higher than a 50m grid.
Beta Index (β)
Beta index is the ratio of Number of edges to that of vertices. Trees (graphs which have no loops in them) and simple networks have Beta value of less than one. A connected network with one cycle has a value of 1. More complex networks have a value greater than 1. Consider graphs with fixed number of nodes. the higher the number of links, more the paths are possible.
When the beta index is less than 1, any link if removed from the graph, will break the graph into 2 sub-graphs. You can see it by removing any link in Graph E of F. This is important to keep in mind for maintenance and construction of roads. One can as well see the index as a representation of how many links on average each node has. since every link is shared by 2 nodes each node shares half the weight. Since every node on grid has higher number of links, and no dead ends, they will have a high beta Index as can be Seen for Graph A and B.
Alpha Index is the measure of connectivity which evaluates the number of cycles. It is the ratio of number of cycles present in graph to that of possible number of cycles. It hence lies between 0 and 1. Simple graphs and trees have a value of 0.
Higher alpha index provides the users of the network multiple options for going from one place to another. This helps in distributing the traffic to different routes reducing the pressure on roads. Since grids have numerous cycles, they always have a higher alpha value. By changing a node to Flyover, you reduce the alternatives and hence reduce the alpha index. Further, when the Beta index is <1, the Alpha index will always be 0, which means there aren’t any other alternative routes. That’s why, only half the road section is closed and worked upon by creating a diversion in road, to still allow movement in the network. this is evident in graph E & F.
Detour Index (DI)
Detour index is measures the efficiency of a transport network in terms of how well it overcomes distance or the friction of distance. It is the ratio of displacement (DS) (straight line distance) to that of distance traveled (DT) between 2 nodes. It is given by the formula:
Detours are a reality, because not every place can be connected to every other directly through straight lines. However, we can try to minimise it. Detours are done to reduce cost of construction of roads in hilly areas, to avoid tunnels, or bridges. Another reason for detours in cities is presence of physical barriers like rivers, railways, or a highway. Other times it’s just systematically embedded into the network. Filtered permeability and one way on certain streets, cause cars to take longer detours than pedestrians and cyclist.
Advanced Exploration: Every set of vertices have 2 networks important networks called Minimum spanning tree (MST) and a network formed by Greedy Triangulation (GT). These can be generated through their specific algorithms. While comparing detours in two networks, a DIrel is considered, which is the ratio of difference of Detour in actual network and its MST; and the actual network and the GT.
Nearest Neighbour Index (NNI)
The Nearest Neighbour Index (NNI) is a complicated tool to measure precisely the spatial distribution of a patter and see if it is regularly dispersed (=probably planned), randomly dispersed, or clustered. A nearest neighbour is a node which is spatially closest the original node. You need at least 30 nodes to have a meaningful result. It is then given by the formula:
Node Level Indices
These Indices differ for every node in the graph. These are very useful in Major road networks and at regional level, where cities are themselves nodes.
This offers a level of importance to every node. It is the number of links attached to that node. The order may be calculated at different depths: adjacent nodes (depth 1), adjacent nodes of adjacent nodes (depth 2), etc. We can further give weights to the links. The node order would then be the sum of the weights associated to the node.
A weighted node order for a road network which has a hierarchy embedded in it, can bring out the major intersections in the network. For example, for a simple grid network, every node has a node order of 4. However, once we take the hierarchy into consideration, giving higher weights to arterial and sub arterial roads, and lower weights to local and semi-permeable streets, we fill start finding the major intersections. In Barcelona’s Super blocks, the main through streets can be given a weight of 2, and the local access streets weight of 1. We start seeing which are the major nodes.
Koenig number for a node is given by the number links it takes to reach the farthest node on the shortest path possible. The lower the Koenig number, the more the central a node is in the network.
Often the most geographically central area may not be the most central area in the network due to the topography. Koenig’s number can in such cases be used to find the most central nodes.
These are just a few more indices that you can look at which include:
- Pi Index: It’s the ratio of the total length of network to the diameter (smallest path between the farthest nodes)
- Theta Index: It’s the traffic/volume per node in the network
- Hierarchy: It’s related to the frequency distribution of the node order in graph, which gives the slope to the logarithmic graph of the frequency distribution
- Assortative coefficient: This coefficient is the Pearson correlation between the Node order at both ends of each link in the network.
- Average Shortest path length: It’s the average of the shortest paths between any two points in the network.
These indices, if not taken into the context, would become meaningless to study. These are the tools that one can use to answer the questions, that you may come across. Its just a matter of knowing that there exists an index, or a way of analysis, which can be used to get this information. Sometimes, these might not completely answer them, but these are the building blocks that you can start working on.
To get a hang of it, its necessary that you look at different types of networks, not just different road networks, but electric grid, river networks, fibre optic networks, rail network etc. Each of these have certain limitations, and want to optimise certain index or parameter. See the indices and you will start linking every index to a certain property of a network.
Further, understanding of these indices, will help you create methodologies to extract answers to very particular queries, from the network.
Editor-In-Chief of NOSPlan
School of Planning and Architecture, Bhopal