Network Analysis. London Tube

Network Analysis. London Tube

The study of networks is useful to understand the dynamics of agents and interactions in complex systems.

1. Introduction

These dynamics can be applied to different kind of systems, such as social networks of friends and family, airline networks, academic citations, economy, metabolic and protein networks, internet (Bales and Johnson, 2005), and transport networks - like the London underground tube network, analysed in this paper.

This paper will compare betweenness and closeness centrality measures by removing principal nodes in the network and analysing its impact to the system. Using the method of detection in the Girvan-Newman algorithm, this paper will explore whether if there are communities in the network.

2. Analysis

2.1 London network

The combined network of London underground, overground and DLR will be analysed. The network has a total of 404 nodes or stations, 538 edges and 1 island. The diameter of the original network is 50535.06 (Fig. 13).

 

Fig 13: The original network has 404 nodes or stations, 538 edges, 1 island and a diameter of 50535.06

2.2 Betweenness

Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest (Newman, 2005). It means that measures the shortest paths passing through a node

Fig 14: Betweenness centrality analysis: map of most important nodes, considering weight. Gradient from red (higher values) to blue (lower values).

Fig 15: Betweenness centrality analysis: list of most important stations (with Id number and betweenness.

2.3 Closeness

By measuring the closeness in the network, we can calculate the distance between each station and the rest of the stations in the network. As result, the network has nodes with higher centrality values.

Fig 16: Closeness centrality analysis: map of most important nodes. Gradient from red (higher values) to blue (lower values).

 

The stations in the closeness and the betweenness analysis are different: in the first one, the stations are King’s Cross St. Pancras, Oxford Circus, Euston, Baker Street, Bond Street and Euston Square. The stations Surrey Quays, Canada Water and Stratford are not listed in the closeness analysis (Fig. 16).

 

Fig 17: Betweenness centrality analysis: list of most important stations (with Id number and betweenness).

 

Topological betweenness
If we calculate the topological betweenness, without considering the weights, the most relevant stations are Bank, Canada Water, Green Park, Surrey Quays, Waterloo and King’s Cross St. Pancras (Fig.18 and 19).

Fig 18: Topological betweenness centrality analysis: list of most important stations (with Id number and betweenness).

Fig 19: Topological betweenness centrality analysis: map of most important nodes. Gradient from red (higher values) to blue (lower values).

 

To find out the impact of nodes, we will calculate its diameter after removing the 5 most important nodes, which is the longest shortest-path of the network, as well as computing the number of islands.

In this new scenario of betweenness, after removing the 5 most important nodes, the diameter is 70873.54 – compared to the original, 50535.06. To show the results in a map, see Fig. 20.

Fig 20: Map with betweenness Centrality after the most important 5 nodes were removed. Gradient from red (higher values) to blue (lower values).

If we recalculate the diameter with closeness removal, the result is 51435.82 (in the betweenness removal scenario was 70873.54 and, in the original, 50535.06). The unweighted diameter results are as follows: 51 for Closeness removal, 61 for betweenness removal and 46 for the original diameter) (Fig. 21).

 

 

Fig. 21. Comparison of diameters between weighted and unweighted; ‘3’ values are with closeness removal; ‘2’ values are with betweenness removal; ‘1’ values are the diameters of the original network.

2.4 Communities

In order to calculate the number of communities, we are going to divide the vertices of the network into clusters using the Girvan-Newman algorithm, based in edge betweenness. The edge betweenness centrality is defined as the number of the shortest paths that go through an edge in a graph or network (Girvan and Newman 2002).

Applying this method, a total of 12 communities were found (Fig. 22)

 

Fig. 22: Plot of 12 communities in the London underground tube network calculated by the Girvan-Newman algorithm.

 

We can visualise the formation of the different communities by breaking the network down in a dendogram (Fig. 23)

Fig. 23: Dendogram of 12 communities in the London underground tube network calculated by the Girvan-Newman algorithm.

 

If we introduce a removal of the nodes with highest betweenness, then the network will be clustered in islands, making a total of 21 communities in the whole system (Fig. 24)

Fig. 24: Plot of 21 communities in the London underground tube network after betweenness removal.

 

The next dendogram (Fig. 25) shows the removal of edges, forming new communities:

 

Fig. 25: Dendogram of 21 communities in the London underground tube network after betweenness removal.

 

The modularity found in the network with betweenness removal (21 communities) is 0.8464864, higher value than modularity of 0.8175924 found in the Girvan-Newman method (12 communities). This means that the 12 communities network is a less divided network, process than we can visualise in the dendograms above.

 

3. Bibliography

Bales, M.E., Johnson, S.B., 2006. Graph theoretic modeling of large-scale semantic networks. Journal of Biomedical Informatics 39, 451–464. doi:10.1016/j.jbi.2005.10.007

Newman,J., 2003. The Structure and Function of Complex Networks. SIAM REVIEW, 42(2), pp. 167-256.

Newman, M.E., Girvan, M., 2004. Finding and evaluating community structure in networks. Physical review E 69, 026113.

Newman, M.E.J., 2005. A measure of betweenness centrality based on random walks. Social Networks 27, 39–54. doi:10.1016/j.socnet.2004.11.009

Tore Opsahl, 2010. Node Centrality in Weighted Networks. [Online] Available at: https:// toreopsahl.com/tnet/weighted-networks/node-centrality/ [Accessed 23/04/2016].

 

Edaimon De Juan

Urban Data Analysis

Data analysis and visualisation

Smart Cities Articles

 

CONTACT

Get in touch

Signup to my newsletter: