1. Creating graphs

2. Graph visualisations

3. Shortest Paths

4. Working with external files

5. Visualizing shortest paths

6. All-to-all shortest paths

7. Degrees and centralities

8. Visualising node properties

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, using`nx`

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)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1, 2)
G.add_edge(2, 3)
G.add_edge(2, 4)
```

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]:

In [6]:

```
G.edges()
```

Out[6]:

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')
```

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]:

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]:

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]:

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')
```

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')
links
```

Out[18]:

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]:

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']))
new_links
```

Out[20]:

We are now ready too proceed:

In [21]:

```
G = nx.Graph()
G.add_nodes_from(nodes['node'])
G.add_edges_from(new_links)
```

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]:

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]:

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.

Let's visualize the path:

In [26]:

```
path = nx.dijkstra_path(G, source=13, target=7)
path
```

Out[26]:

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]:

Everything appears to be OK here.

In [29]:

```
edge_colors
```

Out[29]:

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]:

In [31]:

```
edges_path
```

Out[31]:

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]:

We now append them to the list:

In [33]:

```
edges_path = edges_path + edges_path_reversed
edges_path
```

Out[33]:

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]:

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]:

In [37]:

```
nx.set_edge_attributes(G, values = weights, name = 'weight')
G.edges.data("weight")
```

Out[37]:

Much better. Let's try again.

In [38]:

```
nx.dijkstra_path_length(G, source=13, target=7)
```

Out[38]:

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]:

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.

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]:

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]:

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]:

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]:

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]:

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]:

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]:

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
```

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]:

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]:

Let's now see the degrees of our nodes:

In [52]:

```
degrees = [G.degree(n) for n in G.nodes()]
degrees
```

Out[52]:

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]:

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]:

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]:

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]:

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]:

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]:

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]:

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.

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!).