Feature extraction of graphs

In this section, we will learn how to find features of graphs from their adjacency matrices using some methods from linear algebra we learned in Chapter 6, Computational Algorithms in Linear Algebra—especially matrix sums and matrix multiplication. We will learn how to find the degrees of vertices, count the paths between vertices of a specified length, and find the shortest paths between vertices of graphs.

Degrees of vertices in a graph

In this subsection, we will learn how to find the degrees of vertices with Python. As we mentioned in the previous section, the row (or column) sums of an adjacency matrix give the degrees of each vertex.

We do these calculations in Python:

# Find the degrees of each vertex of the graph in Figure 8.1
# Using column sums
print(numpy.sum(A1, axis=0))
# Using row sums
print(numpy.sum(A1, axis=1))

Note that we use the sum() function from NumPy where the first input is the adjacency matrix A1 of the graph...