2  Degree, Walks, and Paths

Degree of a Node

There is an important relationship between the degree sequence and the total number of edges \(m\) in the network:

Computing with Degrees

Let’s grab some sample data. We’ll use the Les Miserables network, which is a network of coappearances of characters in the book Les Miserables by Victor Hugo. Nodes represent characters and edges represent characters who appear within the same chapter. This data set is supplied as a built-in example in NetworkX, and for this reason we’ll use it several times throughout these notes.

This hidden code cell imports several packages and defines an unweight function which we’ll use to convert the network from its native weighted format to an unweighted format.

Code

from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')

plot_kwargs = {"node_size" : 100, "edgecolors" : 'white', "node_color" : "steelblue", "width" : 0.5, "edge_color" : "darkgrey"}
# This is a coding exercise in the live notes.

def unweight(G):
    for source, target in G.edges():
        G[source][target]['weight'] = 1
    return G

Here’s how this network looks:

Code

fig, ax = plt.subplots(1, 1, figsize = (7, 4))
G_LesMis = unweight(nx.les_miserables_graph())
nx.draw(G_LesMis, **plot_kwargs)

Now let’s compute the degree of each node. There are multiple ways to achieve this task: we can work directly using the adjacency matrix, or we can use the built-in NetworkX function nx.degree().

One way to compute the degrees of the nodes in a graph is to use the adjacency matrix, as directly described by Definition 2.1. With convenient functions from NetworkX and NumPy, this is a two-liner:

For undirected graphs, we could equally do np.sum(A, axis = 0) because \(\mathbf{A}\) is a symmetric matrix. When we discuss directed graphs soon, it will become necessary to be careful!

# computing degrees directly from the adjacency matrix

A = nx.adjacency_matrix(G_LesMis)   # extract the adjacency matrix
degree_vector = np.sum(A, axis = 1) # sum the adjacency matrix over rows
print(f"The degree vector has shape {degree_vector.shape}")

The degree vector has shape (77,)

Networkx also has a helpful built-in function to calculate the complete set of degrees:

degree_view = G_LesMis.degree()

The result is a DegreeView object which behaves much like a Python dictionary (and which can be easily converted to a dictionary using the dict constructor).

Let’s take a moment to compare the first few nodes to make sure that our two methods agree:

i = 0
for name, degree in dict(degree_view).items():
    if i < 5:
        print(f"{name} has degree: {degree} (networkx) and {degree_vector[i]} (adjacency matrix)")
        i += 1

Napoleon has degree: 1 (networkx) and 1 (adjacency matrix)
Myriel has degree: 10 (networkx) and 10 (adjacency matrix)
MlleBaptistine has degree: 3 (networkx) and 3 (adjacency matrix)
MmeMagloire has degree: 3 (networkx) and 3 (adjacency matrix)
CountessDeLo has degree: 1 (networkx) and 1 (adjacency matrix)

Degree in directed graphs

We have to be a little more subtle in how we define degree in a directed network because there is a distinction between in-edges and out-edges in these networks.

Definition 2.2 In a directed network, the in-degree is the number of ingoing edges to a node and the out-degree is the number of outgoing edges. These are defined by the formulas \[ k_i^{\text{in}} = \sum_{j=1}^n A_{ij} \] and the out-degree is \[ k_j^{\text{out}} = \sum_{i=1}^n A_{ij} \]

Just as before, we can also define the in-degree sequence \(\mathbf{k}^{\mathrm{in}}\) and out-degree sequence \(\mathbf{k}^{\mathrm{out}}\).

We will repeat the exercises above for directed networks.

Exercise

1. Express the total number of edges \(m\) in a directed graph in terms of the degree sequences \(\mathbf{k}^{\text{in}}\) and \(\mathbf{k}^{\text{out}}\).
2. Determine the mean in-degree and mean out-degree of a directed graph in terms of \(m\) and \(n\).

Let’s see these definitions in action on a directed graph. This time, we’ll use the mention graph from the musical Hamilton. Each node in this graph is a character. There is a directed edge from character \(i\) to character \(j\) if character \(i\) mentions character \(j\) in a song.

Code

import pandas as pd

# import data for our directed network
df = pd.read_csv("https://philchodrow.github.io/PIC16A/homework/HW3-hamilton-data.csv", 
names = ["mentioner", "mentioned"])

df = df[df["mentioner"] != df["mentioned"]]

G_Hamilton = nx.from_pandas_edgelist(df, 
                            source = "mentioner", 
                            target = "mentioned", 
                            edge_attr=None, 
                            create_using=nx.DiGraph())

layout = nx.arf_layout(G_Hamilton)

fig, ax = plt.subplots(1, 1, figsize = (10, 7))
nx.draw(G_Hamilton, pos = layout,  with_labels = True, edge_color = "darkgrey", width = 0.5, node_color = "lavender", edgecolors = "white")

# This is a coding exercise in the live notes.

# Create and print a numpy array of node in-degrees and out-degrees directly from the adjacency matrix

Let’s calculate the in-degrees of the nodes in the Hamilton network using the adjacency matrix and compare to the networkx built-ins.

Code

A = nx.adjacency_matrix(G_Hamilton)       # grab the adjacency matrix
in_degree_vector = np.sum(A, axis = 0)    # manual in-degrees from A
in_degree_view   = G_Hamilton.in_degree() # networkx builtin

i = 0
for name, degree in dict(in_degree_view).items():
    if i < 5:
        print(f"{name} has degree: {degree} (networkx) and {in_degree_vector[i]} (adjacency matrix)")
        i += 1

burr has degree: 13 (networkx) and 13 (adjacency matrix)
hamilton has degree: 14 (networkx) and 14 (adjacency matrix)
weeks has degree: 1 (networkx) and 1 (adjacency matrix)
madison has degree: 4 (networkx) and 4 (adjacency matrix)
jay has degree: 1 (networkx) and 1 (adjacency matrix)

Exercise

Repeat this calculation and check that you can also compute out-degrees, with a matching result.

fig, ax = plt.subplots(1, 1, figsize = (2, 2))
G = nx.complete_graph(5)
nx.draw(G, **plot_kwargs)

Density and Sparsity

One way to interpret density is to think of it as a probability that a pair of nodes picked uniformly at random is connected by an edge.

\[ \begin{align} \rho &= \frac{m}{\binom{n}{2}} \\ &= \frac{m}{\frac{1}{2}n(n-1)} \\ &= \frac{2m}{n(n-1)} \\ &= \frac{c}{n-1} \,. \end{align} \]

If a network is sufficiently large, you can approximate the density as \(\rho \approx \frac{c}{n}.\)

Let’s compute density in network below using three different strategies:

• Calculating directly using number of edges and number of nodes;
• Calculating directly using mean degree and number of nodes;
• Using the built-in NetworkX function nx.density().

from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')

# Create an unweighted version of the Les Mis network
G = G_LesMis

# This is a coding exercise in the live notes.

# Calculate density directly using number of edges and number of nodes

n = G.number_of_nodes()
m = G.number_of_edges()
print(f"Density using nodes and edges: {2*m/(n*(n-1)):.4f}")

# Calculate density directly using mean degree and number of nodes
# Hint: you may want to calculate degree from the adjacency matrix so that you can calculate mean using numpy

A = nx.adjacency_matrix(G)
degree = np.sum(A, axis = 1)
c = np.mean(degree)
print(f"Calculating using mean degree {c/(n-1):.4f}")
#----

# Use the built-in NetworkX function nx.density()

density = nx.density(G)
print(f"Density with NetworkX built-in: {density:.4f}")

Density using nodes and edges: 0.0868
Calculating using mean degree 0.0868
Density with NetworkX built-in: 0.0868

Informally, we call a network sparse when it has low density. This is pretty tricky to formally define: how low is “low enough?” There isn’t a universally agreed upon threshold for density below which a real-world network would be considered sparse. However, we can create a definition which applies for certain theoretical models of networks. Many models are defined for graphs on \(n\) nodes. If we have a model where we can take a formal limit as \(n\) grows large, then such a network is sparse if \(\rho \to 0\) as \(n \to \infty\). In this scenario, the mean degree grows (much) more slowly than the number of nodes. We’ll study limiting arguments about sparse graphs much more when we discuss random graphs.

Walks and Paths

We may like to know if it it is possible to reach one node from another by traversing edges. For this task, we introduce the notion of a walk.

Code

from matplotlib import pyplot as plt
import networkx as nx
import numpy as np
plt.style.use('seaborn-v0_8-whitegrid')

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

graph_dict = {1: [2], 2: [1, 3], 3:[2], 4:[5,6], 7: [4]}
G = nx.Graph(graph_dict) 
nx.draw(G, with_labels = True, font_color = 'white', font_weight = 'bold', edgecolors = "white", ax = ax, node_size = 200, font_size = 10, edge_color = "darkgrey")

# code example adapted from: https://stackoverflow.com/questions/24024411/highlighting-the-shortest-path-in-a-networkx-graph

np.random.seed(123)

G = nx.karate_club_graph()
pos = nx.spring_layout(G)
nx.draw(G,pos, **plot_kwargs)

path = nx.shortest_path(G, source = 14, target = 16)
pos_path = {i: pos[i] for i in path}
path_edges = list(zip(path,path[1:]))
nx.draw_networkx_nodes(G,pos_path,nodelist=path,node_color='steelblue', node_size = 100, edgecolors = "black")
nx.draw_networkx_edges(G,pos_path,edgelist=path_edges,edge_color='k',width=1)

Cyclic and Acyclic graphs

Many algorithms and measures of graph structure reflect the existence of cycles within a graph.

In some cases, it is useful to check a network to determine whether it contains any cycles. While the adjacency matrix can be used to count cycles of a specific length, it could be quite inefficient to use to detect whether we have a cycle of any length (because we may have to check the diagonal entries of \({\bf A}^r\) for all possible cycle lengths \(r\)). We can construct a simple algorithm to determine computationally whether a network is cyclic or acyclic. For the purposes of this algorithm, we’ll consider directed graphs; the algorithm can be easily adapted to undirected graphs. Here it is:

While \(n > 0\):

• Find a node \(i\) with no out-edges (i.e. \(k_i^{\mathrm{out}} = 0\)).
  • If no such node exists, then the network is cyclic.
• Remove node \(i\) and all its edges.

If all nodes can be removed this way, then the network is acyclic.

Now that we’re convinced that the algorithm works, let’s go ahead and implement it in Python. Our implementation accepts a NetworkX DiGraph object as an argument, returning True if the network is cyclic and False if the network is acyclic.

def is_cyclic(G):
    while G.number_of_nodes() > 0:
        zero_out_degree = [node for node in G.nodes if G.out_degree(node) == 0]
        if len(zero_out_degree) == 0:
            return True
        G.remove_nodes_from(zero_out_degree)
    else: 
        return False

Now let’s test our algorithm on a few examples. First, we’ll construct a random toy directed graph that we know does not possess any cycles by its construction. Indeed, our implemented cycle detector indicates that no cycles are present.

Code

print('Binomial Tree:', end = " ")

fig, ax = plt.subplots(1, 1, figsize = (3, 3))
G_Tree = nx.binomial_tree(4, create_using = nx.DiGraph)
nx.draw(G_Tree,  **plot_kwargs)
if is_cyclic(G_Tree): 
    print("cyclic.")
else: 
    print("acyclic.")

Binomial Tree: acyclic.

On the other hand, the Hamilton mentions network contains at least one cycle:

Code

print('Hamilton Network:', end = " ")
layout = nx.arf_layout(G_Hamilton)
fig, ax = plt.subplots(1, 1, figsize = (3, 3))
nx.draw(G_Hamilton, layout, **plot_kwargs)
is_cyclic(G_Hamilton)
if is_cyclic(G_Hamilton): 
    print("cyclic.")
else: 
    print("acyclic.")

Hamilton Network: cyclic.

This algorithm has a nice mathematical consequence. If we label the nodes in an acyclic network according to the order we removed them, we will end up with an adjacency matrix that is strictly upper triangular. This is because each node that is removed could only have out-edges that were already removed previously, i.e., nonzero entries of the \(i\)th column could only occur between columns 1 and \(i-1\). There exists at least one such labeling for any acyclic network.

edges = [(0,1), (0,2), (1,3), (1,4), (2,5), (2,6), (2, 7), (7, 8)]

pos = {
    0 : (0, 0),
    1 : (-1, -1),
    2 : (1, -1),
    3 : (-1.5, -2),
    4 : (-0.5, -2),
    5 : (0.5, -2),
    6 : (1.0, -2), 
    7 : (1.5, -2), 
    8:  (1.5, -3)
}

fig, ax = plt.subplots(1, 1, figsize = (3, 3))
G_Tree = nx.Graph(edges)
nx.draw(G_Tree, pos = pos, **plot_kwargs)