Notebook 2.1 - Introduction to NetworkX¶
Contents¶
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
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.
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.
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.
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()
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.
G.nodes()
G.edges()
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.
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:
nx.draw(G, with_labels = True, font_color = 'white')
What if we wanted to use square nodes?
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.
G = nx.petersen_graph()
In theory, our graph should look like this:
Let's see what networkx draws...
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:
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:
path = nx.shortest_path(G, source=0, target=9)
path
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.
edges_path = list(zip(path,path[1:]))
edges_path
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.
edge_colors = ['black' if not edge in edges_path else 'red' for edge in G.edges()]
edge_colors
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.
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.
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.
links = pd.read_csv('datasets/siouxfalls_links.csv')
links
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.
nodes = pd.read_csv('datasets/siouxfalls_nodes.csv')
nodes
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.
new_links = list(zip(links['from_node'], links['to_node']))
new_links
We are now ready too proceed:
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:
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.
coords = list(zip(nodes['x'], nodes['y']))
pos = dict(zip(nodes['node'], coords))
pos
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.
nx.dijkstra_path_length(G, source=13, target=7)
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:
path = nx.dijkstra_path(G, source=13, target=7)
path
We can now plot it using the same approach that we followed above.
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.
edges_path
Everything appears to be OK here.
edge_colors
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.
G.edges()
edges_path
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:
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path_reversed
We now append them to the list:
edges_path = edges_path + edges_path_reversed
edges_path
Let's try again!
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:
G.edges.data("weight")
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:
weights = dict(zip(G.edges,links['length']))
weights
nx.set_edge_attributes(G, values = weights, name = 'weight')
G.edges.data("weight")
Much better. Let's try again.
nx.dijkstra_path_length(G, source=13, target=7)
This looks more like it! Let's visualise the shortest path:
path = nx.dijkstra_path(G, source=13, target=7)
path
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?
all_paths = dict(nx.all_pairs_dijkstra_path(G))
all_paths
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:
all_paths[24][10]
And if we wanted to "flatten" the dictionary and obtain all individual paths, we can use the following:
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)
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.
sample_path=path_list[10]
sample_path
Using the same command that we used in our visualisation function, we can convert this into a list of links (node pairs)
edges_path = list(zip(sample_path,sample_path[1:]))
edges_path
As we saw before, for a list of all edges in the network, we can use the edges() function in our graph object:
all_edges = list(G.edges())
all_edges
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:
path_counts = {} # Initializes an empty dictionary
for i in all_edges:
path_counts[i] = 0
path_counts
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:
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.
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
That looks like a very interesting set of counts. If we wanted to sort the dictionary by value, we could use the following:
import operator
sorted_counts = dict( sorted(path_counts.items(), key=operator.itemgetter(1),reverse=True))
sorted_counts
Part 7 - Degrees and centralities¶
Let's now see the degrees of our nodes:
degrees = [G.degree(n) for n in G.nodes()]
degrees
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.
import matplotlib.pyplot as plt
We can plot a histogram using the plt.hist() command, passing the list in question as a parameter.
plt.hist(degrees)
plt.show()
We can also obtain the various centrality values. Let's start with the degree centrality:
nx.degree_centrality(G)
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.
centralities = pd.DataFrame()
We can now start populating it by simply storing values to new columns.
centralities['ID'] = G.nodes()
centralities['degree_centr'] = nx.degree_centrality(G).values()
centralities
Let's now obtain the rest of the centrality values that we obtained in the class.
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
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.
centralities.sort_values(by='betweenness_centr', ascending=False)
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:
centralities.sort_values(by='betweenness_centr', ascending=False).head(10)
But this is supposed to be a Betweenness Top 10 - can we get rid of the other columns?
centralities.sort_values(by='betweenness_centr', ascending=False).head(10)[['ID','betweenness_centr']]
But the row numbers at the very left column look a bit off... Could we perhaps sort these in ascending order?
centralities.sort_values(by='betweenness_centr', ascending=False).head(10).reset_index()[['ID','betweenness_centr']]
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:
nx.draw(G, pos, with_labels = True, node_color = list(centralities['degree_centr']))
nx.draw(G, pos, with_labels = True, node_color = list(centralities['closeness_centr']))
nx.draw(G, pos, with_labels = True, node_color = list(centralities['betweenness_centr']))
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!).