1  Networks and Their Representations

Simple graphs

Simple graphs will be our primary focus throughout much of these notes. A simple graph is a graph that has no nodes which connect directly to themselves and no repeated edges. More formally:

fig, ax = plt.subplots(1, 1, figsize = small_fig_size)

G = nx.MultiDiGraph()
G.add_edges_from([(1, 4), (2, 4), (3, 3), (3, 4), (4, 2)])

nx.draw(G, ax = ax, connectionstyle='arc3, rad = 0.1', arrows = True, arrowsize = 0.1, **plot_kwargs)

fig, ax = plt.subplots(1, 1, figsize = small_fig_size)

G = nx.Graph()
edgelist = [(1, 4), (2, 5), (3, 5), (4, 5), (5, 6), (6, 1), (1, 4), (3, 6), (2, 3), (2, 4), (1, 3), (4, 6)]
G.add_edges_from(edgelist)
nx.draw(G, ax = ax, **plot_kwargs)

Planar graphs

Show code

fig, ax = plt.subplots(1, 1, figsize = small_fig_size)
G = nx.Graph()
edgelist = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (1, 4), (3, 6)]
G.add_edges_from(edgelist)

nx.draw_planar(G, ax = ax, **plot_kwargs)

Planar graphs are commonly studied objects in graph theory and there are many cool theorems about them (see, for example, the four-color theorem or Kuratowski’s theorem). This means that a network that can be represented with a planar graph can leverage this theory.

Directed graphs

In this course, we will spend much of our time focused on the analysis of undirected graphs, where an edge between nodes \(i\) and \(j\) is an unordered pair \(\{i,j\}\). However, there is an extension that can be important in many modeling contexts where there may be an edge from \(j\) to \(i\), but no edge from \(i\) to \(j\). This is called a directed graph. Informally, each edge in a directed graph has a direction, pointing from one node to another. Directed edges are usually represented by lines with arrows.

fig, ax = plt.subplots(1, 1, figsize = small_fig_size)

DG = nx.DiGraph()
DG.add_edges_from([(0, 1), (0, 2), (2, 3), (3, 0), (0, 3)])

nx.draw(DG, 
        with_labels = True, 
        arrowsize = 8, 
        font_color = 'white', 
        font_weight = 'bold',  
        ax = ax, 
        edgecolors = "white", 
        width = 0.5, 
        edge_color = "darkgrey")

Adjacency matrix

Let’s observe a few notes about how the graph structure relates to the structure of the adjacency matrix.

• If there are no self-edges, the diagonal elements \(A_{ii}\) are all zero.
• If the network is undirected, then an edge between \(i\) and \(j\) implies the existence of an edge between \(j\) and \(i\). This means that \(A_{ji} = A_{ij}\) and thus the adjacency matrix is symmetric.
• Similarly, if the adjacency matrix is not symmetric, the network cannot be undirected.

Example. The adjacency matrix for the graph in Figure 1.5 is \[ \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} \]

If we have a graph with multiedges, then we can set the corresponding matrix element \(A_{ij}\) equal to the multiplicity of the edge. For example, a double edge between nodes 2 and 3 in an undirected graph is represented \(A_{23} = A_{32} = 2.\)

But why stop there? Instead of requiring an integer number of edges between two nodes, we could extend this idea to form weighted networks with real-valued edge weights. Sometimes it is useful to represent edges as having a strength, weight, or value. In this situation, we set the value of \(A_{ij}\) equal to the weight of the corresponding edge \((j, i)\). For example, weights in an airport network could be used represent a distance between two airports, or weights in a social media network could represent the number of messages sent between two individuals.

Creating networks

Creating a graph dictionary

You can also build your graph using a dictionary that maps nodes to neighbors. The code below creates a graph with 3 nodes, where nodes 1 and 3 are both connected to node 2, but not to each other.

fig, ax = plt.subplots(1, 1, figsize = small_fig_size)

graph_dict = {1: [2], 2: [1, 3], 3:[2], 4: [2, 3]}
G = nx.Graph(graph_dict) 
nx.draw(G, ax =ax, **plot_kwargs)

It’s also possible to “go backwards” and obtain the dictionary representation from the graph object using

nx.to_dict_of_lists(G)

{1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]}

Using an adjacency matrix

In amny cases, we might actually have a complete network represented as an adjacency matrix. We’ll typically use the Numpy package for representing arrays of numbers like matrices.

You can directly create a graph using a numpy array that encodes your adjacency matrix representation for your graph. The example network in Figure 1.6 has the adjacency matrix

\[ \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix} \]

We can construct this matrix in Python using the numpy package, and then create a graph with it:

import numpy as np
fig, ax = plt.subplots(1, 1, figsize = small_fig_size)

A = np.array([[0, 1, 0, 0], 
              [1, 0, 1, 1], 
              [0, 1, 0, 1], 
              [0, 1, 1, 0]])

G = nx.from_numpy_array(A)

nx.draw(G, ax = ax, **plot_kwargs)

For a directed graph, you need to make two additional changes to the code above. You need specify that you want a directed graph with the create_using argument to the graph constructor. Additionally, you need to be very careful about the adjacency matrix convention for in and out edges. The default convention for from_numpy_array points edges in the opposite direction to what we defined above (it assumes \(A_{ij} = 1\) if \((i,j) \in E\)), so if you want to match that convention, you’ll need to take the transpose with np.transpose.

Here’s an example of constructing the directed graph shown in Figure 1.5 from an adjacency matrix.

import numpy as np
fig, ax = plt.subplots(1, 1, figsize = (2, 3))

A = np.array([[0, 0, 0, 1], 
              [1, 0, 0, 0], 
              [1, 0, 0, 0], 
              [0, 0, 1, 0]])

G = nx.from_numpy_array(np.transpose(A), create_using = nx.DiGraph)
nx.draw(G, 
        with_labels = True, 
        arrowsize = 8, 
        font_color = 'white', 
        font_weight = 'bold',  
        ax = ax, 
        edgecolors = "white", 
        width = 0.5, 
        edge_color = "darkgrey")