Compute with networks

Open In Colab

Compute with networks#

So far we worked out the network of bridges of Konigsberg by illustrating the network with points and lines. From now, we will work with a representation of the network that can be easily computed with code.

Network representation#

An atomic element of a network is a node, i.e., a network is a collection of edges which are pairs of nodes. We label a unique integer as an identifier for each node. For instance, the bridges of Konigsberg has 4 nodes, and we assign the number 0 to 3 to the nodes. An edge can be represented by a pair of nodes. For instance, the edge between node 0 and node 1 can be represented by the pair (0, 1).

file

Fig. 4 Labeled Knigsberg graph#

Note

We label nodes starting from 0 with consecutive numbers, which is convenient for Python. However, this is not the only way to label nodes.

The Konigsberg graph can be represented by a list of edges.

edges = [(0,1), (0, 1), (0, 3), (1, 2), (1, 2), (1, 3), (2, 3)]

Another, more convenient format is the adjacency matrix. In this form, one regard the node index as a coordinate in the matrix. For instance, edge \((1,3)\) is represented by the entry in the second row and fourth column. The entry of the matrix represents the number of edges between two nodes. Thus, the zeros in the matrix represent the absence of edges.

A = [[0, 2, 0, 1],
     [2, 0, 2, 1],
     [0, 2, 0, 1],
     [1, 1, 1, 0]]

or equivalently, using for loops:

import numpy as np

A = np.zeros((4, 4))
for i, j in edges:
    A[i][j] += 1
    A[j][i] += 1

Note

In the Konigsberg graph, the edges are undirected, meaning edge (i,j) is the same as edge (j,i), which is why we increment both entries \((i,j)\) and \((j,i)\) in the for loop. If the edges are directed, we treat (i,j) and (j,i) as two different edges, and increment only (i,j).

Edge counting#

Let us showcase the convenience of the adjacency matrix by counting the number of edges in the network.

The total number of edges in the network is the sum of the entities in the

np.sum(A) / 2

7.0

We divide by 2 because an edge corresponds to two entries in the matrix. Now, let us consider

It is also easy to compute the number of edges pertained to individual nodes by taking the row or column sum of the matrix.

np.sum(A, axis = 1)

array([3., 5., 3., 3.])

The result is an array of length 4, where the i-th entry is the number of edges connected to node i.

Important

The number of edges connected to a node is called the degree of the node.

Tip

The np.sum(A, axis = 1) is the column sum of A. Alternatively, np.sum(A, axis = 0) is the row sum of A. Check out the numpy documentation for more details.

Tip

If the adjacency matrix is scipy CSR format (or CSC format), you can instead use A_csr.sum(axis=1), A_csr.sum(axis=0), and A_csr.sum(). Check out the scipy documentation for more details.

We can check the number of nodes with odd degree by taking the modulus of the degree by 2.

deg = np.sum(A, axis = 1)
is_odd = deg % 2 == 1
is_odd

array([ True,  True,  True,  True])

if np.sum(is_odd) == 2 or np.sum(is_odd) == 0:
    print("The graph has a Euler path.")
else:
    print("The graph does not have a Euler path.")

The graph does not have a Euler path.
Contents