Working with Trees and Networks

Networks are objects that contain nodes and edges between pairs of nodes. They can be used to represent a wide variety of real-world situations, such as distribution and scheduling. Mathematically, networks are useful for visualizing combinatorial problems and make for a rich and fascinating theory.

There are, of course, several different kinds of networks. We will mostly deal with simple networks, where edges connect two distinct nodes (so there are no self-loops), there is, at most, one edge between any two nodes, and all the edges are bidirectional. A tree is a special kind of network in which there are no cycles; that is, there are no lists of nodes in which each node is connected to the following node by an edge, and the final node is connected to the first. Trees are especially simple in terms of their theory because they connect several nodes with the fewest possible edges. A complete network is a network in which every node is connected to...

Technical requirements

In this chapter, we will primarily use the NetworkX package for working with trees and networks. This package can be installed using your favorite package manager, such as pip:

python3.10 -m pip install networkx

We usually import this under the nx alias, following the conventions established in the official NetworkX (https://networkx.org/documentation/stable/) documentation, using the following import statement:

import networkx as nx

The code for this chapter can be found in the Chapter 05 folder of this book’s GitHub repository at https://github.com/PacktPublishing/Applying-Math-with-Python-2nd-Edition/tree/main/Chapter%2005.

Creating networks in Python

To solve the multitude of problems that can be expressed as network problems, we need a way of creating networks in Python. For this, we will make use of the NetworkX package and the routines and classes it provides to create, manipulate, and analyze networks.

In this recipe, we’ll create an object in Python that represents a network and add nodes and edges to this object.

Getting ready

As we mentioned in the Technical requirements section, we need the NetworkX package to be imported under the nx alias. We can do this using the following import statement:

import networkx as nx

How to do it...

Follow these steps to create a Python representation of a simple graph:

1. We need to create a new Graph object that will store the nodes and edges that constitute the graph:

   G = nx.Graph()

2. Next, we need to add the nodes for the network using the add_node method:

   G.add_node(1)

   G.add_node(2)

3. To avoid calling this method repetitively...

Visualizing networks

A common first step in analyzing a network is to draw the network, which can help us identify some of the prominent features of a network. (Of course, drawings can be misleading, so we should not rely on them too heavily in our analysis.)

In this recipe, we’ll describe how to use the network drawing facilities in the NetworkX package to visualize a network.

Getting ready

For this recipe, we will need to import the NetworkX package under the nx alias, as described in the Technical requirements section. We will also need the Matplotlib package. For this, as usual, we must import the pyplot module as plt using the following import statement:

import matplotlib.pyplot as plt

How to do it...

The following steps outline how to draw a simple network object using the drawing routines from NetworkX:

1. First, we will create a simple example network to draw:

   G = nx.Graph()

   G.add_nodes_from(range(1, 7))

   G.add_edges_from([

       ...

Getting the basic characteristics of networks

Networks have various basic characteristics beyond the number of nodes and edges that are useful for analyzing a graph. For example, the degree of a node is the number of edges that start (or end) at that node. A higher degree indicates that the node is better connected to the rest of the network.

In this recipe, we will learn how to access the basic attributes and compute various basic measures associated with a network.

Getting ready

As usual, we need to import the NetworkX package under the nx alias. We also need to import the Matplotlib pyplot module as plt.

How to do it...

Follow these steps to access the various basic characteristics of a network:

1. Create the sample network that we will analyze in this recipe, like so:

   G = nx.Graph()

   G.add_nodes_from(range(10))

   G.add_edges_from([

       (0, 1), (1, 2), (2, 3), (2, 4),

       (2, 5), (3, 4), (4, 5), (6, 7),

       ...

Generating the adjacency matrix for a network

One potent tool for analyzing graphs is the adjacency matrix, which has entries if there is an edge from node to node , and 0 otherwise. For most networks, the adjacency matrix will be sparse (most of the entries are 0). For networks that are not directed, the matrix will also be symmetric (). Numerous other matrices can be associated with a network. We will briefly discuss these in the There’s more... section of this recipe.

In this recipe, we will generate the adjacency matrix for a network and learn how to get some basic properties of the network from this matrix.

Getting ready

For this recipe, we will need the NetworkX package imported under the nx alias, and the NumPy module imported as np.

How to do it...

The following steps outline how to generate the adjacency matrix for a network and derive some simple properties of the network from this matrix:

1. First, we will generate a network to work with throughout...

Creating directed and weighted networks

Simple networks, such as those described in the previous recipes, are useful for describing networks where the direction of an edge is unimportant and where the edges carry equal weight. In practice, most networks carry additional information, such as weights or directions.

In this recipe, we will create a directed and weighted network and explore some of the basic properties of such networks.

Getting ready

For this recipe, we will need the NetworkX package, imported under the nx alias (as usual), the Matplotlib pyplot module imported as plt, and the NumPy package imported as np.

How to do it...

The following steps outline how to create a directed network with weights, as well as how to explore some of the properties and techniques we discussed in the previous recipes:

1. To create a directed network, we can use the DiGraph class from NetworkX rather than the simple Graph class:

   G = nx.DiGraph()

2. As usual, we must add nodes...

Finding the shortest paths in a network

A common problem where networks make an appearance is in the problem of finding the shortest – or perhaps more precisely, the highest reward – route between two nodes in a network. For instance, this could be the shortest distance between two cities, where the nodes represent the cities, and the edges are roads connecting pairs of cities. In this case, the weights of the edges would be their lengths.

In this recipe, we will find the shortest path between two nodes in a network with weights.

Getting ready

For this recipe, we will need the NetworkX package imported, as usual, under the nx alias, the Matplotlib pyplot module imported as plt, and a random number generator object from NumPy:

from numpy.random import default_rng
rng = default_rng(12345) # seed for reproducibility

How to do it...

Follow these steps to find the shortest path between two nodes in a network:

1. First, we will create a random network...

Quantifying clustering in a network

There are various quantities associated with networks that measure the characteristics of the network. For example, the clustering coefficient of a node measures the interconnectivity between the nodes nearby (here, nearby means connected by an edge). In effect, it measures how close the neighboring nodes are to forming a complete network or clique.

The clustering coefficient of a node measures the proportion of the adjacent nodes that are connected by an edge; that is, two adjacent nodes form a triangle with the given node. We count the number of triangles and divide this by the total number of possible triangles that could be formed, given the degree of the node. Numerically, the clustering coefficient at a node, , in a simple unweighted network is given by the following equation:

Here, is the number of triangles at and the denominator is the total possible number of triangles at . If the degree of (the number of...

Coloring a network

Networks are also useful in scheduling problems, where you need to arrange activities into different slots so that there are no conflicts. For example, we could use networks to schedule classes to make sure that students who are taking different options do not have to be in two classes at once. In this scenario, the nodes will represent the different classes and the edges will indicate that students are taking both classes. The process we use to solve these kinds of problems is called network coloring. This process involves assigning the fewest possible colors to the nodes in a network so that no two adjacent nodes have the same color.

In this recipe, we will learn how to color a network to solve a simple scheduling problem.

Getting ready

For this recipe, we need the NetworkX package imported under the nx alias and the Matplotlib pyplot module imported as plt.

How to do it...

Follow these steps to solve a network coloring problem:

1. First, we...

Finding minimal spanning trees and dominating sets

Networks have applications for a wide variety of problems. Two obvious areas that see many applications are communication and distribution. For example, we might wish to find a way of distributing goods to several cities (nodes) in a road network that covers the smallest distance from a particular point. For problems like this, we need to look at minimal spanning trees and dominating sets.

In this recipe, we will find a minimal spanning tree and a dominating set in a network.

Getting ready

For this recipe, we need to import the NetworkX package under the nx alias and the Matplotlib pyplot module as plt.

How to do it...

Follow these steps to find a minimum spanning tree and dominating set for a network:

1. First, we will create a sample network to analyze:

   G = nx.gnm_random_graph(15, 22, seed=12345)

2. Next, as usual, we will draw the network before doing any analysis:

   fig, ax = plt.subplots()

   pos = nx.circular_layout...

Further reading

There are several classical texts on graph theory, including books by Bollobás and Diestel:

• Diestel, R., 2010. Graph Theory. 3rd ed. Berlin: Springer.
• Bollobás, B., 2010. Modern Graph Theory. New York, NY: Springer.