# Notebook 2.1 - Introduction to NetworkX¶

### Part 1 - Creating graphs¶

We begin by importing our packages. It is usually a good practice to import all the packages that we are using in a notebook at the very beginning.

There are quite a few packages that we will be using, but to keep things simple, on this occasion we will be only importing networkx.

In [1]:
import networkx as nx


The above command imported networkx, and created an alias (shortcut) named nx to the package. This will allow us to call all commands that are provided by the package, usingnx instead of networkx as a qualifier.

We did not select nx arbitarily - if you look online, you will notice that it is a common convention in most python codes to use nx when importing networkx.

In [2]:
G = nx.Graph()


With the above command we are creating a new empty graph.

Let's explore how it works by adding a few nodes and edges.

In [3]:
G.add_node(1)



Now that we have populated our graph, we can visualise it using the nx.draw() command.

Remember, since we used the as keyword when we imported networkx, this is exactly the same as calling networkx.draw()

In [4]:
nx.draw(G)


Which is exactly what we were expecting! No surprises here.

At any time we can view the nodes and edges in a graph by invoking the .nodes() and .edges() functions that are provided by the Graph object.

In [5]:
G.nodes()

Out[5]:
NodeView((1, 2, 3, 4))
In [6]:
G.edges()

Out[6]:
EdgeView([(1, 2), (2, 3), (2, 4)])

### Part 2 - Graph visualisations¶

It is always helpful to visualise the graph. To make it a bit easier to understand, we can also add lalels by passing the with_labels=True parameter.

In [7]:
nx.draw(G, with_labels = True)


The nx.draw() function is itself a shortcut to another function provided by networkx, called networkx.drawing.nx_pylab.draw_networkx().

I guess we can all agree that nx.draw() is simpler to write!

The nx.draw() function has many more useful parameters that you can use to customise the appearance of your drawings. You can find a full list and more guidance on this page.

For instance, the default font color in the labels is black, which makes them rather difficult to read. Let's try something different:

In [8]:
nx.draw(G, with_labels = True, font_color = 'white')


What if we wanted to use square nodes?

In [9]:
nx.draw(G, with_labels = True, font_color = 'white', node_shape='s')


I would encourage you to expariment a bit more with the parameters at your own time. nx.draw() draws its functionality from the matplotlib.pyplot library, which we will be using quite a lot in this course - therefore quite a lot of the features that you use are more widely applicable.

It would be nice now to experiment with some larger graphs, however it would be tedious to define them manually. Thankfully, networkx provides some built-in graph generators which you can use in order to quickly create graphs that you can experiment with.

One of these is the Petersen graph generator, a graph instance that is used quite widely in graph theory. You can find more about it here.

In [10]:
G = nx.petersen_graph()


In theory, our graph should look like this:

Let's see what networkx draws...

In [11]:
nx.draw(G,with_labels = True, font_color = 'white')


Upon first sight, they do not appear to be quite the same!

Look closer - they have the same number of nodes and edges, and the same connectivity pattern. It is in fact the same graph as the above - it simply lacks information regarding the position of the nodes.

Whenever a graph lacks infromation regarding node positions, networkx will pick some on its own. These are calculated afresh every time that the nx.draw() command is called:

In [12]:
nx.draw(G,with_labels = True, font_color = 'white')


### Part 3 - Shortest Paths¶

Now let us experiment with the built-in shortest path algorithms that are provided by networkx.

In the first instance we will try the nx.shortest_path() command:

In [13]:
path = nx.shortest_path(G, source=0, target=9)
path

Out[13]:
[0, 4, 9]

It would be nice if we could draw the path in the table. To do that, we will have first to convert the sequence of nodes, to a sequence of links.

In [14]:
edges_path = list(zip(path,path[1:]))
edges_path

Out[14]:
[(0, 4), (4, 9)]

There are quite a few things happening on the first line of the above block, but we will not be going into detail right now. You will get the hang of the the list() and zip() functions quite soon!

Now, we will create a list that assigns the color of an edge depending on whether it is included in the shortest path that we determined.

We are going to do this by going through the list of edges and checking whether each specific edge belongs to our path. If it does, it will be given a red color.

In [15]:
edge_colors = ['black' if not edge in edges_path else 'red' for edge in G.edges()]
edge_colors

Out[15]:
['black',
'red',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'red',
'black',
'black',
'black',
'black',
'black']

The sequence of colors follows the sequence of the edges in the graph, therefore we can provide it directly to nx.draw() and it will be able to highlight the correct edges.

In [16]:
nx.draw(G, with_labels = True, edge_color= edge_colors, font_color = 'white')


### Part 4 - Working with external files¶

Now that we have covered the basics of networkx, and we can start experimenting with "real" network files. In this section, we will be using the classical Sioux Falls network layout, which is very frequently used as a 'toy' network in the academic transportation literature.

To proceed, we need to import another library, pandas, which will help us manipulate datasets. A common convention when importing pandas is to use the pd acronym.

In [17]:
import pandas as pd


I have placed the relevant datasets in the datasets/ folder. The network structure is expressed as a series of csv files, which we can easily read using the pd.read_csv() command, which returns a "dataframe" that contains the information in the file.

In [18]:
links = pd.read_csv('datasets/siouxfalls_links.csv')

Out[18]:
from_node to_node length
0 1 2 6
1 1 3 4
2 2 1 6
3 2 6 5
4 3 1 4
... ... ... ...
71 23 22 4
72 23 24 2
73 24 13 4
74 24 21 3
75 24 23 2

76 rows × 3 columns

As you can notice above, pandas is able to recognise the labels in our csv file, and uses them to name the columns. Its algorithms, however, is not foolproof - occasionally you might need to intervene.

In [19]:
nodes = pd.read_csv('datasets/siouxfalls_nodes.csv')
nodes

Out[19]:
node x y
0 1 -96.770420 43.612828
1 2 -96.711251 43.605813
2 3 -96.774303 43.572962
3 4 -96.747168 43.563654
4 5 -96.731569 43.564034
5 6 -96.711644 43.587586
6 7 -96.693423 43.563844
7 8 -96.711382 43.562324
8 9 -96.731241 43.548596
9 10 -96.731438 43.545271
10 11 -96.746841 43.544131
11 12 -96.780137 43.543941
12 13 -96.793377 43.490707
13 14 -96.751035 43.529306
14 15 -96.731504 43.529401
15 16 -96.711382 43.546744
16 17 -96.711382 43.541280
17 18 -96.694078 43.546744
18 19 -96.711316 43.529591
19 20 -96.711185 43.515334
20 21 -96.730979 43.510485
21 22 -96.731241 43.514858
22 23 -96.750904 43.514858
23 24 -96.749200 43.503164

We don't need to add all these edges to a graph one by one - we can simply create a list of edges and supply them to networkx.

To do this, we will use the zip() command which is used to take separate lists of objects (with the same number of items) and join them in a single object. The two lists that we wish to join is the sequence of origin nodes (from_node)and the sequence of destination nodes (to_node) in our pandas dataframe.

The resulting object that is returned by th zip function cannot be used directly, but must rather converted into a list using the list() command.

In [20]:
new_links = list(zip(links['from_node'], links['to_node']))

Out[20]:
[(1, 2),
(1, 3),
(2, 1),
(2, 6),
(3, 1),
(3, 4),
(3, 12),
(4, 3),
(4, 5),
(4, 11),
(5, 4),
(5, 6),
(5, 9),
(6, 2),
(6, 5),
(6, 8),
(7, 8),
(7, 18),
(8, 6),
(8, 7),
(8, 9),
(8, 16),
(9, 5),
(9, 8),
(9, 10),
(10, 9),
(10, 11),
(10, 15),
(10, 16),
(10, 17),
(11, 4),
(11, 10),
(11, 12),
(11, 14),
(12, 3),
(12, 11),
(12, 13),
(13, 12),
(13, 24),
(14, 11),
(14, 15),
(14, 23),
(15, 10),
(15, 14),
(15, 19),
(15, 22),
(16, 8),
(16, 10),
(16, 17),
(16, 18),
(17, 10),
(17, 16),
(17, 19),
(18, 7),
(18, 16),
(18, 20),
(19, 15),
(19, 17),
(19, 20),
(20, 18),
(20, 19),
(20, 21),
(20, 22),
(21, 20),
(21, 22),
(21, 24),
(22, 15),
(22, 20),
(22, 21),
(22, 23),
(23, 14),
(23, 22),
(23, 24),
(24, 13),
(24, 21),
(24, 23)]

We are now ready too proceed:

In [21]:
G = nx.Graph()


This is a lot more compact than the first graph that we generated. In the first instance we passed a list of node IDs to the add_nodes_from function, that were contained in the nodes['node'] column. NetworkX used these IDs to create new node objects.

The list of links was also passed to NetworkX. The resulting network is:

In [22]:
nx.draw(G, with_labels = True, font_color = 'white')


Contrary to the abstract graphs that we experimented with earlier, this relates to a civil infrastructure network and it would be therefore quite important to represent its spatial structure accurately.

To achieve this, we need to create a list of node parameters. We can do that by zipping the relevant columns in the nodes dataframe. In contrast to the sequence of edge colors that we used before, this needs to be served to networkx as a dictionary, with the keys being the node IDs and the values being the coordinates.

In [23]:
coords = list(zip(nodes['x'], nodes['y']))
pos = dict(zip(nodes['node'], coords))
pos

Out[23]:
{1: (-96.77041974, 43.61282792),
2: (-96.71125063, 43.60581298),
3: (-96.77430341, 43.572961600000006),
4: (-96.74716843, 43.56365362),
5: (-96.73156909, 43.56403357),
6: (-96.71164389, 43.58758553),
7: (-96.69342281, 43.5638436),
8: (-96.71138171, 43.56232379),
9: (-96.73124137, 43.54859634),
10: (-96.73143801, 43.54527088),
11: (-96.74684071, 43.54413068),
12: (-96.78013678, 43.54394065),
13: (-96.79337655, 43.49070718),
14: (-96.75103549, 43.52930613),
15: (-96.73150355, 43.52940117),
16: (-96.71138171, 43.54674361),
17: (-96.71138171, 43.54128009),
18: (-96.69407825, 43.54674361),
19: (-96.71131617, 43.52959125),
20: (-96.71118508, 43.515333500000004),
21: (-96.73097920000001, 43.51048509),
22: (-96.73124137, 43.51485818),
23: (-96.75090441, 43.51485818),
24: (-96.74920028, 43.50316422)}
In [24]:
nx.draw(G, pos, with_labels = True, font_color = 'white')


We can now start experimenting with the paths again - we pick two nodes (13 and 7), and can call the nx.dijkstra_path_length() command to get the length of the shortest path, as calculated by the Dijkstras algorithm implementation provided by networkx.

In [25]:
nx.dijkstra_path_length(G, source=13, target=7)

Out[25]:
5

The algorithm reports that the length of the shortest path is 5. Looking at the list of edges that we loaded, it is reasonable to suspect that something is not right.

### Part 5 - Visualizing shortest paths¶

Let's visualize the path:

In [26]:
path = nx.dijkstra_path(G, source=13, target=7)
path

Out[26]:
[13, 24, 21, 20, 18, 7]

We can now plot it using the same approach that we followed above.

In [27]:
edges_path = list(zip(path,path[1:]))
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors, font_color = 'white')


We can only see one highlighted line in the graph, and this certainly does not suffice to connect 13 to 7. After all, the shortest path had several nodes, and we would have expected to see several edges highlighted.

Let us look at the variables one by one.

In [28]:
edges_path

Out[28]:
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7)]

Everything appears to be OK here.

In [29]:
edge_colors

Out[29]:
['black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'red',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black',
'black']

We are getting closer - only one node is highlighted. The problem must be located at the command used to generate this list:

edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]


Let's look at the lists of variables that we are comparing, G.edges() and edges_path.

In [30]:
G.edges()

Out[30]:
EdgeView([(1, 2), (1, 3), (2, 6), (3, 4), (3, 12), (4, 5), (4, 11), (5, 6), (5, 9), (6, 8), (7, 8), (7, 18), (8, 9), (8, 16), (9, 10), (10, 11), (10, 15), (10, 16), (10, 17), (11, 12), (11, 14), (12, 13), (13, 24), (14, 15), (14, 23), (15, 19), (15, 22), (16, 17), (16, 18), (17, 19), (18, 20), (19, 20), (20, 21), (20, 22), (21, 22), (21, 24), (22, 23), (23, 24)])
In [31]:
edges_path

Out[31]:
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7)]

Here is the problem - the edges_path list starts with the edge (13,12). The list returned by G.edges() does not contain such an edge - it does, however have (12,13)!

We have spotted the problem. Even though our graph is bidirectional, the code that we wrote to highlight the edges does not "understand" the concepts of bi-directionality. It simply checks the edges as reported by networkx.

There are many ways to resolve this - for the time being we will use something quick and dirty: we will add to the edges_path the reversed versions of all edges. This way we will ensure that the edge will be highlighted.

We can start by creating a list of the reversed edges:

In [32]:
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path_reversed

Out[32]:
[(24, 13), (21, 24), (20, 21), (18, 20), (7, 18)]

We now append them to the list:

In [33]:
edges_path = edges_path + edges_path_reversed
edges_path

Out[33]:
[(13, 24),
(24, 21),
(21, 20),
(20, 18),
(18, 7),
(24, 13),
(21, 24),
(20, 21),
(18, 20),
(7, 18)]

Let's try again!

In [34]:
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors)


Success!

But this is only one of the problems that we encountered... If you might recall, we also need to find out why the shortest path is so short.

The Dijkstra's algorithm provided by networkx calculates the paths using the weight property of each edge. We can inspect this using this following command:

In [35]:
G.edges.data("weight")

Out[35]:
EdgeDataView([(1, 2, None), (1, 3, None), (2, 6, None), (3, 4, None), (3, 12, None), (4, 5, None), (4, 11, None), (5, 6, None), (5, 9, None), (6, 8, None), (7, 8, None), (7, 18, None), (8, 9, None), (8, 16, None), (9, 10, None), (10, 11, None), (10, 15, None), (10, 16, None), (10, 17, None), (11, 12, None), (11, 14, None), (12, 13, None), (13, 24, None), (14, 15, None), (14, 23, None), (15, 19, None), (15, 22, None), (16, 17, None), (16, 18, None), (17, 19, None), (18, 20, None), (19, 20, None), (20, 21, None), (20, 22, None), (21, 22, None), (21, 24, None), (22, 23, None), (23, 24, None)])

Uh, but of course! We never added the lenghts that were included in the links dataframe to the graph.

We can provide these using a dictionary, that has the actual edges as keys and the lengths as values:

In [36]:
weights = dict(zip(G.edges,links['length']))
weights

Out[36]:
{(1, 2): 6,
(1, 3): 4,
(2, 6): 6,
(3, 4): 5,
(3, 12): 4,
(4, 5): 4,
(4, 11): 4,
(5, 6): 4,
(5, 9): 2,
(6, 8): 6,
(7, 8): 2,
(7, 18): 4,
(8, 9): 5,
(8, 16): 5,
(9, 10): 4,
(10, 11): 2,
(10, 15): 3,
(10, 16): 2,
(10, 17): 2,
(11, 12): 3,
(11, 14): 10,
(12, 13): 5,
(13, 24): 5,
(14, 15): 10,
(14, 23): 3,
(15, 19): 3,
(15, 22): 5,
(16, 17): 6,
(16, 18): 4,
(17, 19): 8,
(18, 20): 6,
(19, 20): 5,
(20, 21): 6,
(20, 22): 4,
(21, 22): 4,
(21, 24): 6,
(22, 23): 3,
(23, 24): 3}
In [37]:
nx.set_edge_attributes(G, values = weights, name = 'weight')
G.edges.data("weight")

Out[37]:
EdgeDataView([(1, 2, 6), (1, 3, 4), (2, 6, 6), (3, 4, 5), (3, 12, 4), (4, 5, 4), (4, 11, 4), (5, 6, 4), (5, 9, 2), (6, 8, 6), (7, 8, 2), (7, 18, 4), (8, 9, 5), (8, 16, 5), (9, 10, 4), (10, 11, 2), (10, 15, 3), (10, 16, 2), (10, 17, 2), (11, 12, 3), (11, 14, 10), (12, 13, 5), (13, 24, 5), (14, 15, 10), (14, 23, 3), (15, 19, 3), (15, 22, 5), (16, 17, 6), (16, 18, 4), (17, 19, 8), (18, 20, 6), (19, 20, 5), (20, 21, 6), (20, 22, 4), (21, 22, 4), (21, 24, 6), (22, 23, 3), (23, 24, 3)])

Much better. Let's try again.

In [38]:
nx.dijkstra_path_length(G, source=13, target=7)

Out[38]:
19

This looks more like it! Let's visualise the shortest path:

In [39]:
path = nx.dijkstra_path(G, source=13, target=7)
path

Out[39]:
[13, 12, 11, 10, 16, 8, 7]
In [40]:
edges_path = list(zip(path,path[1:]))
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path = edges_path + edges_path_reversed
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors)


So, the path is actually different from the one that we obtained before - it turns out that when a weight is not provided, Dijkstra's uses a default weight of 1.

### Part 6 - All-to-all shortest paths¶

What if we wanted to obtain all the shortest paths in our network?

In [41]:
all_paths = dict(nx.all_pairs_dijkstra_path(G))
all_paths

Out[41]:
{1: {1: [1],
2: [1, 2],
3: [1, 3],
4: [1, 3, 4],
12: [1, 3, 12],
6: [1, 2, 6],
11: [1, 3, 12, 11],
13: [1, 3, 12, 13],
5: [1, 3, 4, 5],
10: [1, 3, 12, 11, 10],
14: [1, 3, 12, 11, 14],
8: [1, 2, 6, 8],
24: [1, 3, 12, 13, 24],
9: [1, 3, 4, 5, 9],
15: [1, 3, 12, 11, 10, 15],
16: [1, 3, 12, 11, 10, 16],
17: [1, 3, 12, 11, 10, 17],
18: [1, 3, 12, 11, 10, 16, 18],
19: [1, 3, 12, 11, 10, 15, 19],
22: [1, 3, 12, 11, 10, 15, 22],
7: [1, 2, 6, 8, 7],
21: [1, 3, 12, 13, 24, 21],
23: [1, 3, 12, 13, 24, 23],
20: [1, 3, 12, 11, 10, 15, 19, 20]},
2: {2: [2],
1: [2, 1],
6: [2, 6],
3: [2, 1, 3],
5: [2, 6, 5],
8: [2, 6, 8],
4: [2, 6, 5, 4],
12: [2, 1, 3, 12],
9: [2, 6, 5, 9],
7: [2, 6, 8, 7],
16: [2, 6, 8, 16],
10: [2, 6, 5, 9, 10],
11: [2, 1, 3, 12, 11],
13: [2, 1, 3, 12, 13],
18: [2, 6, 8, 7, 18],
15: [2, 6, 5, 9, 10, 15],
17: [2, 6, 5, 9, 10, 17],
14: [2, 1, 3, 12, 11, 14],
20: [2, 6, 8, 7, 18, 20],
19: [2, 6, 5, 9, 10, 15, 19],
24: [2, 1, 3, 12, 13, 24],
22: [2, 6, 5, 9, 10, 15, 22],
21: [2, 6, 5, 9, 10, 15, 22, 21],
23: [2, 1, 3, 12, 13, 24, 23]},
3: {3: [3],
1: [3, 1],
4: [3, 4],
12: [3, 12],
2: [3, 1, 2],
11: [3, 12, 11],
13: [3, 12, 13],
5: [3, 4, 5],
10: [3, 12, 11, 10],
14: [3, 12, 11, 14],
24: [3, 12, 13, 24],
6: [3, 4, 5, 6],
9: [3, 4, 5, 9],
15: [3, 12, 11, 10, 15],
16: [3, 12, 11, 10, 16],
17: [3, 12, 11, 10, 17],
8: [3, 4, 5, 9, 8],
18: [3, 12, 11, 10, 16, 18],
19: [3, 12, 11, 10, 15, 19],
22: [3, 12, 11, 10, 15, 22],
21: [3, 12, 13, 24, 21],
23: [3, 12, 13, 24, 23],
7: [3, 4, 5, 9, 8, 7],
20: [3, 12, 11, 10, 15, 19, 20]},
4: {4: [4],
3: [4, 3],
5: [4, 5],
11: [4, 11],
6: [4, 5, 6],
9: [4, 5, 9],
10: [4, 11, 10],
12: [4, 11, 12],
14: [4, 11, 14],
1: [4, 3, 1],
8: [4, 5, 9, 8],
15: [4, 11, 10, 15],
16: [4, 11, 10, 16],
17: [4, 11, 10, 17],
13: [4, 11, 12, 13],
2: [4, 5, 6, 2],
18: [4, 11, 10, 16, 18],
19: [4, 11, 10, 15, 19],
22: [4, 11, 10, 15, 22],
7: [4, 5, 9, 8, 7],
24: [4, 11, 12, 13, 24],
20: [4, 11, 10, 15, 19, 20],
23: [4, 11, 14, 23],
21: [4, 11, 10, 15, 22, 21]},
5: {5: [5],
4: [5, 4],
6: [5, 6],
9: [5, 9],
8: [5, 9, 8],
10: [5, 9, 10],
3: [5, 4, 3],
11: [5, 4, 11],
2: [5, 6, 2],
15: [5, 9, 10, 15],
16: [5, 9, 10, 16],
17: [5, 9, 10, 17],
7: [5, 9, 8, 7],
12: [5, 4, 11, 12],
14: [5, 4, 11, 14],
18: [5, 9, 10, 16, 18],
19: [5, 9, 10, 15, 19],
1: [5, 4, 3, 1],
22: [5, 9, 10, 15, 22],
13: [5, 4, 11, 12, 13],
20: [5, 9, 10, 15, 19, 20],
21: [5, 9, 10, 15, 22, 21],
23: [5, 9, 10, 15, 22, 23],
24: [5, 9, 10, 15, 22, 23, 24]},
6: {6: [6],
2: [6, 2],
5: [6, 5],
8: [6, 8],
4: [6, 5, 4],
9: [6, 5, 9],
1: [6, 2, 1],
7: [6, 8, 7],
16: [6, 8, 16],
10: [6, 5, 9, 10],
3: [6, 5, 4, 3],
11: [6, 5, 4, 11],
18: [6, 8, 7, 18],
15: [6, 5, 9, 10, 15],
17: [6, 5, 9, 10, 17],
12: [6, 5, 4, 11, 12],
14: [6, 5, 4, 11, 14],
20: [6, 8, 7, 18, 20],
19: [6, 5, 9, 10, 15, 19],
22: [6, 5, 9, 10, 15, 22],
13: [6, 5, 4, 11, 12, 13],
21: [6, 5, 9, 10, 15, 22, 21],
23: [6, 5, 9, 10, 15, 22, 23],
24: [6, 5, 9, 10, 15, 22, 23, 24]},
7: {7: [7],
8: [7, 8],
18: [7, 18],
6: [7, 8, 6],
9: [7, 8, 9],
16: [7, 8, 16],
20: [7, 18, 20],
5: [7, 8, 9, 5],
10: [7, 8, 16, 10],
17: [7, 8, 16, 10, 17],
2: [7, 8, 6, 2],
4: [7, 8, 9, 5, 4],
11: [7, 8, 16, 10, 11],
15: [7, 8, 16, 10, 15],
19: [7, 18, 20, 19],
21: [7, 18, 20, 21],
22: [7, 18, 20, 22],
12: [7, 8, 16, 10, 11, 12],
14: [7, 18, 20, 22, 23, 14],
3: [7, 8, 9, 5, 4, 3],
1: [7, 8, 6, 2, 1],
23: [7, 18, 20, 22, 23],
13: [7, 8, 16, 10, 11, 12, 13],
24: [7, 18, 20, 22, 23, 24]},
8: {8: [8],
6: [8, 6],
7: [8, 7],
9: [8, 9],
16: [8, 16],
18: [8, 7, 18],
5: [8, 9, 5],
10: [8, 16, 10],
17: [8, 16, 10, 17],
2: [8, 6, 2],
20: [8, 7, 18, 20],
4: [8, 9, 5, 4],
11: [8, 16, 10, 11],
15: [8, 16, 10, 15],
12: [8, 16, 10, 11, 12],
14: [8, 16, 10, 11, 14],
19: [8, 16, 10, 15, 19],
22: [8, 16, 10, 15, 22],
3: [8, 9, 5, 4, 3],
1: [8, 6, 2, 1],
21: [8, 7, 18, 20, 21],
13: [8, 16, 10, 11, 12, 13],
23: [8, 16, 10, 15, 22, 23],
24: [8, 16, 10, 15, 22, 23, 24]},
9: {9: [9],
5: [9, 5],
8: [9, 8],
10: [9, 10],
4: [9, 5, 4],
6: [9, 5, 6],
11: [9, 10, 11],
15: [9, 10, 15],
16: [9, 10, 16],
17: [9, 10, 17],
7: [9, 8, 7],
3: [9, 5, 4, 3],
2: [9, 5, 6, 2],
12: [9, 10, 11, 12],
14: [9, 10, 11, 14],
18: [9, 10, 16, 18],
19: [9, 10, 15, 19],
22: [9, 10, 15, 22],
13: [9, 10, 11, 12, 13],
20: [9, 10, 15, 19, 20],
1: [9, 5, 4, 3, 1],
21: [9, 10, 15, 22, 21],
23: [9, 10, 15, 22, 23],
24: [9, 10, 15, 22, 23, 24]},
10: {10: [10],
9: [10, 9],
11: [10, 11],
15: [10, 15],
16: [10, 16],
17: [10, 17],
4: [10, 11, 4],
12: [10, 11, 12],
14: [10, 11, 14],
8: [10, 16, 8],
18: [10, 16, 18],
19: [10, 15, 19],
22: [10, 15, 22],
5: [10, 9, 5],
3: [10, 11, 12, 3],
13: [10, 11, 12, 13],
7: [10, 16, 8, 7],
20: [10, 15, 19, 20],
6: [10, 9, 5, 6],
21: [10, 15, 22, 21],
23: [10, 15, 22, 23],
1: [10, 11, 12, 3, 1],
24: [10, 15, 22, 23, 24],
2: [10, 9, 5, 6, 2]},
11: {11: [11],
4: [11, 4],
10: [11, 10],
12: [11, 12],
14: [11, 14],
9: [11, 10, 9],
15: [11, 10, 15],
16: [11, 10, 16],
17: [11, 10, 17],
3: [11, 12, 3],
13: [11, 12, 13],
5: [11, 4, 5],
8: [11, 10, 16, 8],
18: [11, 10, 16, 18],
19: [11, 10, 15, 19],
22: [11, 10, 15, 22],
1: [11, 12, 3, 1],
24: [11, 12, 13, 24],
6: [11, 4, 5, 6],
7: [11, 10, 16, 8, 7],
20: [11, 10, 15, 19, 20],
23: [11, 14, 23],
21: [11, 10, 15, 22, 21],
2: [11, 12, 3, 1, 2]},
12: {12: [12],
3: [12, 3],
11: [12, 11],
13: [12, 13],
4: [12, 11, 4],
10: [12, 11, 10],
14: [12, 11, 14],
1: [12, 3, 1],
24: [12, 13, 24],
9: [12, 11, 10, 9],
15: [12, 11, 10, 15],
16: [12, 11, 10, 16],
17: [12, 11, 10, 17],
5: [12, 11, 4, 5],
8: [12, 11, 10, 16, 8],
18: [12, 11, 10, 16, 18],
19: [12, 11, 10, 15, 19],
2: [12, 3, 1, 2],
22: [12, 11, 10, 15, 22],
21: [12, 13, 24, 21],
23: [12, 13, 24, 23],
6: [12, 11, 4, 5, 6],
7: [12, 11, 10, 16, 8, 7],
20: [12, 11, 10, 15, 19, 20]},
13: {13: [13],
12: [13, 12],
24: [13, 24],
3: [13, 12, 3],
11: [13, 12, 11],
21: [13, 24, 21],
23: [13, 24, 23],
4: [13, 12, 11, 4],
10: [13, 12, 11, 10],
14: [13, 24, 23, 14],
22: [13, 24, 23, 22],
1: [13, 12, 3, 1],
9: [13, 12, 11, 10, 9],
15: [13, 12, 11, 10, 15],
16: [13, 12, 11, 10, 16],
17: [13, 12, 11, 10, 17],
20: [13, 24, 23, 22, 20],
5: [13, 12, 11, 4, 5],
8: [13, 12, 11, 10, 16, 8],
18: [13, 12, 11, 10, 16, 18],
19: [13, 12, 11, 10, 15, 19],
2: [13, 12, 3, 1, 2],
6: [13, 12, 11, 4, 5, 6],
7: [13, 12, 11, 10, 16, 8, 7]},
14: {14: [14],
11: [14, 11],
15: [14, 15],
23: [14, 23],
22: [14, 23, 22],
24: [14, 23, 24],
20: [14, 23, 22, 20],
21: [14, 23, 22, 21],
13: [14, 23, 24, 13],
4: [14, 11, 4],
10: [14, 11, 10],
12: [14, 11, 12],
19: [14, 15, 19],
18: [14, 23, 22, 20, 18],
9: [14, 11, 10, 9],
16: [14, 11, 10, 16],
17: [14, 11, 10, 17],
3: [14, 11, 12, 3],
5: [14, 11, 4, 5],
8: [14, 11, 10, 16, 8],
7: [14, 23, 22, 20, 18, 7],
1: [14, 11, 12, 3, 1],
6: [14, 11, 4, 5, 6],
2: [14, 11, 12, 3, 1, 2]},
15: {15: [15],
10: [15, 10],
14: [15, 14],
19: [15, 19],
22: [15, 22],
9: [15, 10, 9],
11: [15, 10, 11],
16: [15, 10, 16],
17: [15, 10, 17],
20: [15, 19, 20],
21: [15, 22, 21],
23: [15, 22, 23],
4: [15, 10, 11, 4],
12: [15, 10, 11, 12],
8: [15, 10, 16, 8],
18: [15, 10, 16, 18],
5: [15, 10, 9, 5],
24: [15, 22, 23, 24],
3: [15, 10, 11, 12, 3],
13: [15, 10, 11, 12, 13],
7: [15, 10, 16, 8, 7],
6: [15, 10, 9, 5, 6],
1: [15, 10, 11, 12, 3, 1],
2: [15, 10, 9, 5, 6, 2]},
16: {16: [16],
8: [16, 8],
10: [16, 10],
17: [16, 10, 17],
18: [16, 18],
9: [16, 10, 9],
11: [16, 10, 11],
15: [16, 10, 15],
7: [16, 8, 7],
20: [16, 18, 20],
4: [16, 10, 11, 4],
12: [16, 10, 11, 12],
14: [16, 10, 11, 14],
19: [16, 10, 15, 19],
6: [16, 8, 6],
22: [16, 10, 15, 22],
5: [16, 10, 9, 5],
3: [16, 10, 11, 12, 3],
13: [16, 10, 11, 12, 13],
21: [16, 10, 15, 22, 21],
23: [16, 10, 15, 22, 23],
2: [16, 8, 6, 2],
1: [16, 10, 11, 12, 3, 1],
24: [16, 10, 15, 22, 23, 24]},
17: {17: [17],
10: [17, 10],
16: [17, 10, 16],
19: [17, 19],
9: [17, 10, 9],
11: [17, 10, 11],
15: [17, 10, 15],
4: [17, 10, 11, 4],
12: [17, 10, 11, 12],
14: [17, 10, 11, 14],
8: [17, 10, 16, 8],
18: [17, 10, 16, 18],
22: [17, 10, 15, 22],
5: [17, 10, 9, 5],
3: [17, 10, 11, 12, 3],
13: [17, 10, 11, 12, 13],
20: [17, 19, 20],
7: [17, 10, 16, 8, 7],
6: [17, 10, 9, 5, 6],
21: [17, 10, 15, 22, 21],
23: [17, 10, 15, 22, 23],
1: [17, 10, 11, 12, 3, 1],
24: [17, 10, 15, 22, 23, 24],
2: [17, 10, 9, 5, 6, 2]},
18: {18: [18],
7: [18, 7],
16: [18, 16],
20: [18, 20],
8: [18, 7, 8],
10: [18, 16, 10],
17: [18, 16, 10, 17],
19: [18, 20, 19],
21: [18, 20, 21],
22: [18, 20, 22],
6: [18, 7, 8, 6],
9: [18, 16, 10, 9],
11: [18, 16, 10, 11],
15: [18, 16, 10, 15],
4: [18, 16, 10, 11, 4],
12: [18, 16, 10, 11, 12],
14: [18, 20, 22, 23, 14],
23: [18, 20, 22, 23],
5: [18, 16, 10, 9, 5],
3: [18, 16, 10, 11, 12, 3],
13: [18, 16, 10, 11, 12, 13],
24: [18, 20, 22, 23, 24],
2: [18, 7, 8, 6, 2],
1: [18, 16, 10, 11, 12, 3, 1]},
19: {19: [19],
15: [19, 15],
17: [19, 17],
20: [19, 20],
10: [19, 15, 10],
14: [19, 15, 14],
22: [19, 15, 22],
18: [19, 20, 18],
21: [19, 20, 21],
9: [19, 15, 10, 9],
11: [19, 15, 10, 11],
16: [19, 15, 10, 16],
23: [19, 15, 22, 23],
4: [19, 15, 10, 11, 4],
12: [19, 15, 10, 11, 12],
8: [19, 15, 10, 16, 8],
5: [19, 15, 10, 9, 5],
7: [19, 20, 18, 7],
24: [19, 15, 22, 23, 24],
3: [19, 15, 10, 11, 12, 3],
13: [19, 15, 10, 11, 12, 13],
6: [19, 15, 10, 9, 5, 6],
1: [19, 15, 10, 11, 12, 3, 1],
2: [19, 15, 10, 9, 5, 6, 2]},
20: {20: [20],
18: [20, 18],
19: [20, 19],
21: [20, 21],
22: [20, 22],
15: [20, 19, 15],
23: [20, 22, 23],
17: [20, 19, 17],
7: [20, 18, 7],
16: [20, 18, 16],
24: [20, 22, 23, 24],
14: [20, 22, 23, 14],
10: [20, 19, 15, 10],
8: [20, 18, 7, 8],
11: [20, 19, 15, 10, 11],
13: [20, 22, 23, 24, 13],
9: [20, 19, 15, 10, 9],
6: [20, 18, 7, 8, 6],
4: [20, 19, 15, 10, 11, 4],
12: [20, 19, 15, 10, 11, 12],
5: [20, 19, 15, 10, 9, 5],
3: [20, 19, 15, 10, 11, 12, 3],
2: [20, 18, 7, 8, 6, 2],
1: [20, 19, 15, 10, 11, 12, 3, 1]},
21: {21: [21],
20: [21, 20],
22: [21, 22],
24: [21, 24],
15: [21, 22, 15],
23: [21, 22, 23],
18: [21, 20, 18],
19: [21, 20, 19],
13: [21, 24, 13],
14: [21, 22, 23, 14],
10: [21, 22, 15, 10],
11: [21, 22, 15, 10, 11],
17: [21, 22, 15, 10, 17],
12: [21, 24, 13, 12],
7: [21, 20, 18, 7],
16: [21, 22, 15, 10, 16],
9: [21, 22, 15, 10, 9],
4: [21, 22, 15, 10, 11, 4],
8: [21, 20, 18, 7, 8],
3: [21, 24, 13, 12, 3],
5: [21, 22, 15, 10, 9, 5],
6: [21, 22, 15, 10, 9, 5, 6],
1: [21, 24, 13, 12, 3, 1],
2: [21, 22, 15, 10, 9, 5, 6, 2]},
22: {22: [22],
15: [22, 15],
20: [22, 20],
21: [22, 21],
23: [22, 23],
14: [22, 23, 14],
24: [22, 23, 24],
18: [22, 20, 18],
19: [22, 15, 19],
10: [22, 15, 10],
11: [22, 15, 10, 11],
13: [22, 23, 24, 13],
9: [22, 15, 10, 9],
16: [22, 15, 10, 16],
17: [22, 15, 10, 17],
7: [22, 20, 18, 7],
4: [22, 15, 10, 11, 4],
12: [22, 15, 10, 11, 12],
8: [22, 15, 10, 16, 8],
5: [22, 15, 10, 9, 5],
3: [22, 15, 10, 11, 12, 3],
6: [22, 15, 10, 9, 5, 6],
1: [22, 15, 10, 11, 12, 3, 1],
2: [22, 15, 10, 9, 5, 6, 2]},
23: {23: [23],
14: [23, 14],
22: [23, 22],
24: [23, 24],
11: [23, 14, 11],
15: [23, 22, 15],
20: [23, 22, 20],
21: [23, 22, 21],
13: [23, 24, 13],
18: [23, 22, 20, 18],
19: [23, 22, 15, 19],
10: [23, 22, 15, 10],
12: [23, 24, 13, 12],
9: [23, 22, 15, 10, 9],
16: [23, 22, 15, 10, 16],
17: [23, 22, 15, 10, 17],
4: [23, 14, 11, 4],
7: [23, 22, 20, 18, 7],
3: [23, 24, 13, 12, 3],
8: [23, 22, 15, 10, 16, 8],
5: [23, 22, 15, 10, 9, 5],
1: [23, 24, 13, 12, 3, 1],
6: [23, 22, 15, 10, 9, 5, 6],
2: [23, 24, 13, 12, 3, 1, 2]},
24: {24: [24],
13: [24, 13],
21: [24, 21],
23: [24, 23],
14: [24, 23, 14],
22: [24, 23, 22],
12: [24, 13, 12],
20: [24, 23, 22, 20],
11: [24, 13, 12, 11],
15: [24, 23, 22, 15],
3: [24, 13, 12, 3],
18: [24, 23, 22, 20, 18],
19: [24, 23, 22, 15, 19],
10: [24, 23, 22, 15, 10],
4: [24, 13, 12, 11, 4],
1: [24, 13, 12, 3, 1],
9: [24, 23, 22, 15, 10, 9],
16: [24, 23, 22, 15, 10, 16],
17: [24, 23, 22, 15, 10, 17],
7: [24, 23, 22, 20, 18, 7],
8: [24, 23, 22, 15, 10, 16, 8],
5: [24, 23, 22, 15, 10, 9, 5],
2: [24, 13, 12, 3, 1, 2],
6: [24, 23, 22, 15, 10, 9, 5, 6]}}

As we can see from the above, the all_pairs_dijkstra_path function returns a nested dictionary (dict-of-dicts), that contains the sequence of shortest paths between any two nodes in the network.

An important detail in the above is that we had to use the dict funtion ahead of all_pairs_dijkstra_path. This is because by default, the ltter function will return a "generator" object, which produces specific paths between node pairs only when requested. The dict ensures that all the paths are calculated and saved into a dictionary, in our case all_paths.

WARNING: The above operation is likely going to take a lot of time in a very large network.

Having calculated all paths in a single go and stored them into a nested dictionary, we can obtain our shortest paths as follows:

In [42]:
all_paths[24][10]

Out[42]:
[24, 23, 22, 15, 10]

And if we wanted to "flatten" the dictionary and obtain all individual paths, we can use the following:

In [43]:
path_list = []      #initialises empty list of paths

for i in all_paths:
for j in all_paths[i]:
path_list.append(all_paths[i][j])

len(path_list)

Out[43]:
576

If we look closer at a random path in that set, we can notice that it is provided to us as a sequence of nodes.

In [44]:
sample_path=path_list[10]
sample_path

Out[44]:
[1, 3, 12, 11, 14]

Using the same command that we used in our visualisation function, we can convert this into a list of links (node pairs)

In [45]:
edges_path = list(zip(sample_path,sample_path[1:]))
edges_path

Out[45]:
[(1, 3), (3, 12), (12, 11), (11, 14)]

As we saw before, for a list of all edges in the network, we can use the edges() function in our graph object:

In [46]:
all_edges = list(G.edges())
all_edges

Out[46]:
[(1, 2),
(1, 3),
(2, 6),
(3, 4),
(3, 12),
(4, 5),
(4, 11),
(5, 6),
(5, 9),
(6, 8),
(7, 8),
(7, 18),
(8, 9),
(8, 16),
(9, 10),
(10, 11),
(10, 15),
(10, 16),
(10, 17),
(11, 12),
(11, 14),
(12, 13),
(13, 24),
(14, 15),
(14, 23),
(15, 19),
(15, 22),
(16, 17),
(16, 18),
(17, 19),
(18, 20),
(19, 20),
(20, 21),
(20, 22),
(21, 22),
(21, 24),
(22, 23),
(23, 24)]

Now, let's assume that we want to calculate the number of shortest paths that contain each link.

In the first instance, we would have to create a dictionary where we will store our path counts, agains our list of nodes, which are used as keys. The counts will be initially set to zero:

In [47]:
path_counts = {}  # Initializes an empty dictionary

In [48]:
for i in all_edges:
path_counts[i] = 0

path_counts

Out[48]:
{(1, 2): 0,
(1, 3): 0,
(2, 6): 0,
(3, 4): 0,
(3, 12): 0,
(4, 5): 0,
(4, 11): 0,
(5, 6): 0,
(5, 9): 0,
(6, 8): 0,
(7, 8): 0,
(7, 18): 0,
(8, 9): 0,
(8, 16): 0,
(9, 10): 0,
(10, 11): 0,
(10, 15): 0,
(10, 16): 0,
(10, 17): 0,
(11, 12): 0,
(11, 14): 0,
(12, 13): 0,
(13, 24): 0,
(14, 15): 0,
(14, 23): 0,
(15, 19): 0,
(15, 22): 0,
(16, 17): 0,
(16, 18): 0,
(17, 19): 0,
(18, 20): 0,
(19, 20): 0,
(20, 21): 0,
(20, 22): 0,
(21, 22): 0,
(21, 24): 0,
(22, 23): 0,
(23, 24): 0}

In our next step, we would go through our list of paths, convert each of them into a sequence of edges, and then keep track of how many times each of them is encountered:

In [49]:
for path in path_list:                        # go through each path in our list of paths
edges_sequence = list(zip(path,path[1:])) # convert the sequence of nodes to a sequence of edges

for edge in edges_sequence:               # now go through each edge in our sequence of edges
path_counts[edge] += 1                # increment our edge incidence counter by one

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-49-75d88961c9b7> in <module>
3
4     for edge in edges_sequence:               # now go through each edge in our sequence of edges
----> 5         path_counts[edge] += 1                # increment our edge incidence counter by one

KeyError: (12, 11)

It was a good approach in theory, but we encountered the same problem as before! Because our graph is bidirectional, an edge can be traversed in either direction. We can see that the loop above wanted to increment our counter for edge (12, 11), but such an key could not be found in our dictionary.

It did however contain an edge (11, 12). We will use a work-around: before incrementing the value in the dictionary, we will be checking whether the edge exists as a key. If it does not, we will assume that the reverse edge exists, and we will be incrementing that value instead.

Note: This issue will not have occured in a directed graph.

In [50]:
for path in path_list:                        # go through each path in our list of paths
edges_sequence = list(zip(path,path[1:])) # convert the sequence of nodes to a sequence of edges

for edge in edges_sequence:               # now go through each edge in our sequence of edges
i,j = edge

if (i,j) in path_counts.keys():
path_counts[(i,j)] += 1                # increment our edge incidence counter by one
else:
path_counts[(j,i)] += 1                # increment our edge incidence counter by one

path_counts

Out[50]:
{(1, 2): 24,
(1, 3): 56,
(2, 6): 37,
(3, 4): 19,
(3, 12): 74,
(4, 5): 42,
(4, 11): 46,
(5, 6): 50,
(5, 9): 74,
(6, 8): 24,
(7, 8): 44,
(7, 18): 30,
(8, 9): 16,
(8, 16): 42,
(9, 10): 80,
(10, 11): 124,
(10, 15): 146,
(10, 16): 90,
(10, 17): 42,
(11, 12): 106,
(11, 14): 30,
(12, 13): 60,
(13, 24): 38,
(14, 15): 4,
(14, 23): 20,
(15, 19): 54,
(15, 22): 86,
(16, 17): 0,
(16, 18): 26,
(17, 19): 4,
(18, 20): 38,
(19, 20): 28,
(20, 21): 10,
(20, 22): 26,
(21, 22): 26,
(21, 24): 10,
(22, 23): 68,
(23, 24): 46}

That looks like a very interesting set of counts. If we wanted to sort the dictionary by value, we could use the following:

In [51]:
import operator

sorted_counts = dict( sorted(path_counts.items(), key=operator.itemgetter(1),reverse=True))
sorted_counts

Out[51]:
{(10, 15): 146,
(10, 11): 124,
(11, 12): 106,
(10, 16): 90,
(15, 22): 86,
(9, 10): 80,
(3, 12): 74,
(5, 9): 74,
(22, 23): 68,
(12, 13): 60,
(1, 3): 56,
(15, 19): 54,
(5, 6): 50,
(4, 11): 46,
(23, 24): 46,
(7, 8): 44,
(4, 5): 42,
(8, 16): 42,
(10, 17): 42,
(13, 24): 38,
(18, 20): 38,
(2, 6): 37,
(7, 18): 30,
(11, 14): 30,
(19, 20): 28,
(16, 18): 26,
(20, 22): 26,
(21, 22): 26,
(1, 2): 24,
(6, 8): 24,
(14, 23): 20,
(3, 4): 19,
(8, 9): 16,
(20, 21): 10,
(21, 24): 10,
(14, 15): 4,
(17, 19): 4,
(16, 17): 0}

### Part 7 - Degrees and centralities¶

Let's now see the degrees of our nodes:

In [52]:
degrees = [G.degree(n) for n in G.nodes()]
degrees

Out[52]:
[2, 2, 3, 3, 3, 3, 2, 4, 3, 5, 4, 3, 2, 3, 4, 4, 3, 3, 3, 4, 3, 4, 3, 3]

We can plot the distribution of degrees using matplotlib. To do this, we need to import it - as with the other libraries that we used, there happens to be yet another frequently used acronym for this library - plt.

In [53]:
import matplotlib.pyplot as plt


We can plot a histogram using the plt.hist() command, passing the list in question as a parameter.

In [54]:
plt.hist(degrees)
plt.show()


We can also obtain the various centrality values. Let's start with the degree centrality:

In [55]:
nx.degree_centrality(G)

Out[55]:
{1: 0.08695652173913043,
2: 0.08695652173913043,
3: 0.13043478260869565,
4: 0.13043478260869565,
5: 0.13043478260869565,
6: 0.13043478260869565,
7: 0.08695652173913043,
8: 0.17391304347826086,
9: 0.13043478260869565,
10: 0.21739130434782608,
11: 0.17391304347826086,
12: 0.13043478260869565,
13: 0.08695652173913043,
14: 0.13043478260869565,
15: 0.17391304347826086,
16: 0.17391304347826086,
17: 0.13043478260869565,
18: 0.13043478260869565,
19: 0.13043478260869565,
20: 0.17391304347826086,
21: 0.13043478260869565,
22: 0.17391304347826086,
23: 0.13043478260869565,
24: 0.13043478260869565}

As we would like to compare the various centrality values it might be useful to store them in a new dataframe.

We can use the pd.DataFrame() command to initiate an empty dataframe.

In [56]:
centralities = pd.DataFrame()


We can now start populating it by simply storing values to new columns.

In [57]:
centralities['ID'] = G.nodes()
centralities['degree_centr'] = nx.degree_centrality(G).values()
centralities

Out[57]:
ID degree_centr
1 1 0.086957
2 2 0.086957
3 3 0.130435
4 4 0.130435
5 5 0.130435
6 6 0.130435
7 7 0.086957
8 8 0.173913
9 9 0.130435
10 10 0.217391
11 11 0.173913
12 12 0.130435
13 13 0.086957
14 14 0.130435
15 15 0.173913
16 16 0.173913
17 17 0.130435
18 18 0.130435
19 19 0.130435
20 20 0.173913
21 21 0.130435
22 22 0.173913
23 23 0.130435
24 24 0.130435

Let's now obtain the rest of the centrality values that we obtained in the class.

In [58]:
centralities['closeness_centr'] = nx.closeness_centrality(G).values()
centralities['betweenness_centr'] = nx.betweenness_centrality(G).values()
centralities['eigenvector_centr'] = nx.eigenvector_centrality(G).values()
centralities

Out[58]:
ID degree_centr closeness_centr betweenness_centr eigenvector_centr
1 1 0.086957 0.264368 0.035244 0.034586
2 2 0.086957 0.267442 0.036797 0.041609
3 3 0.130435 0.306667 0.095285 0.078701
4 4 0.130435 0.348485 0.100838 0.128455
5 5 0.130435 0.333333 0.065152 0.128600
6 6 0.130435 0.310811 0.097666 0.110150
7 7 0.086957 0.306667 0.030665 0.117212
8 8 0.173913 0.343284 0.138553 0.212955
9 9 0.130435 0.365079 0.075878 0.208734
10 10 0.217391 0.425926 0.239977 0.384541
11 11 0.173913 0.403509 0.226379 0.239538
12 12 0.130435 0.348485 0.131799 0.110723
13 13 0.086957 0.306667 0.060277 0.066920
14 14 0.130435 0.353846 0.086665 0.209532
15 15 0.173913 0.370968 0.122476 0.317121
16 16 0.173913 0.389831 0.124630 0.304680
17 17 0.130435 0.359375 0.031973 0.267580
18 18 0.130435 0.343284 0.097956 0.194776
19 19 0.130435 0.333333 0.034064 0.241578
20 20 0.173913 0.328571 0.113175 0.255652
21 21 0.130435 0.315068 0.063439 0.185475
22 22 0.173913 0.328571 0.071888 0.267482
23 23 0.130435 0.315068 0.042478 0.172218
24 24 0.130435 0.302632 0.070422 0.122064

To understand the values a bit better, it might be useful to sort the values we can use the .sort_values() function provided with all DataFrames.

In [59]:
centralities.sort_values(by='betweenness_centr', ascending=False)

Out[59]:
ID degree_centr closeness_centr betweenness_centr eigenvector_centr
10 10 0.217391 0.425926 0.239977 0.384541
11 11 0.173913 0.403509 0.226379 0.239538
8 8 0.173913 0.343284 0.138553 0.212955
12 12 0.130435 0.348485 0.131799 0.110723
16 16 0.173913 0.389831 0.124630 0.304680
15 15 0.173913 0.370968 0.122476 0.317121
20 20 0.173913 0.328571 0.113175 0.255652
4 4 0.130435 0.348485 0.100838 0.128455
18 18 0.130435 0.343284 0.097956 0.194776
6 6 0.130435 0.310811 0.097666 0.110150
3 3 0.130435 0.306667 0.095285 0.078701
14 14 0.130435 0.353846 0.086665 0.209532
9 9 0.130435 0.365079 0.075878 0.208734
22 22 0.173913 0.328571 0.071888 0.267482
24 24 0.130435 0.302632 0.070422 0.122064
5 5 0.130435 0.333333 0.065152 0.128600
21 21 0.130435 0.315068 0.063439 0.185475
13 13 0.086957 0.306667 0.060277 0.066920
23 23 0.130435 0.315068 0.042478 0.172218
2 2 0.086957 0.267442 0.036797 0.041609
1 1 0.086957 0.264368 0.035244 0.034586
19 19 0.130435 0.333333 0.034064 0.241578
17 17 0.130435 0.359375 0.031973 0.267580
7 7 0.086957 0.306667 0.030665 0.117212

That's quite interesting! We can see a wide range of centrality values - obviously, the centrality measuse regards some nodes as more important than others.

What if we wanted to obtain a Top 10 table? We can do this using the head() function:

In [60]:
centralities.sort_values(by='betweenness_centr', ascending=False).head(10)

Out[60]:
ID degree_centr closeness_centr betweenness_centr eigenvector_centr
10 10 0.217391 0.425926 0.239977 0.384541
11 11 0.173913 0.403509 0.226379 0.239538
8 8 0.173913 0.343284 0.138553 0.212955
12 12 0.130435 0.348485 0.131799 0.110723
16 16 0.173913 0.389831 0.124630 0.304680
15 15 0.173913 0.370968 0.122476 0.317121
20 20 0.173913 0.328571 0.113175 0.255652
4 4 0.130435 0.348485 0.100838 0.128455
18 18 0.130435 0.343284 0.097956 0.194776
6 6 0.130435 0.310811 0.097666 0.110150

But this is supposed to be a Betweenness Top 10 - can we get rid of the other columns?

In [61]:
centralities.sort_values(by='betweenness_centr', ascending=False).head(10)[['ID','betweenness_centr']]

Out[61]:
ID betweenness_centr
10 10 0.239977
11 11 0.226379
8 8 0.138553
12 12 0.131799
16 16 0.124630
15 15 0.122476
20 20 0.113175
4 4 0.100838
18 18 0.097956
6 6 0.097666

But the row numbers at the very left column look a bit off... Could we perhaps sort these in ascending order?

In [62]:
centralities.sort_values(by='betweenness_centr', ascending=False).head(10).reset_index()[['ID','betweenness_centr']]

Out[62]:
ID betweenness_centr
0 10 0.239977
1 11 0.226379
2 8 0.138553
3 12 0.131799
4 16 0.124630
5 15 0.122476
6 20 0.113175
7 4 0.100838
8 18 0.097956
9 6 0.097666

We tinkered enough with the table for now. Now let's try to visualise the centralities.

We can do that easily by simply passing the values as a node_color. networkx/matplotlib will find a way to translate these into an actual color.

### Part 8 - Visualising node properties¶

Let's see how the various centrality measures look like:

In [63]:
nx.draw(G, pos, with_labels = True, node_color = list(centralities['degree_centr']))

In [64]:
nx.draw(G, pos, with_labels = True, node_color = list(centralities['closeness_centr']))

In [65]:
nx.draw(G, pos, with_labels = True, node_color = list(centralities['betweenness_centr']))

In [66]:
nx.draw(G, pos, with_labels = True, node_color = list(centralities['eigenvector_centr']))


We can observe that there is quite a lot of similarity in the relative distribution of colors, but with some notable differences in the central nodes. That is to be expected, as each centrality measure has its own distinct definition (and purpose!).