Appendix

The branch of mathematics studying networks is called graph theory. Graph and network are more or less two words for the same thing, but mathematicians can be picky about exact definitions. A graph is composed of two parts: a set of things called vertices and a set of edges representing connections between those vertices.

What is a vertex? It's a mathematical object whose sole purpose is to be connected to other vertices. In other words, it's pretty much the same thing as a node. In order to tell vertices apart, it is necessary to give them some kind of label. These labels could be anything, but let's call them v₁, v₂, and so on. It's a common convention to call a set of vertices V. Mathematically, this can be written using the following set notation, where N is the number of vertices in V:

V = {v₁, v₂, ..., v_N},

Connections between vertices are called...

Adjacency matrices

A matrix is a way of describing pairwise relationships. A matrix looks like a grid of numbers, as in the following example:

┌           ┐
│ 0    1 42 │
│ 0.5 -3  1 │
└           ┘

The preceding matrix contains six entries, organized in two rows and three columns. A matrix can have any number of rows or columns, but they are always rectangular. A matrix with two rows and three columns is described as a 2 x 3 matrix. If the entire matrix is called A, then the element at row i and column j is called A_i,j. So, in the preceding example, A_2,1 = 0.5.

One way to represent a graph as a matrix is to place the weight of each edge in one element of the matrix (or a zero if there is no edge). So, an edge from v₃, to v₁ with a weight of 37 would be represented by A_3,1 = 37, meaning the third row has a 37 in the first column...

Biadjacency matrices

Bipartite graphs can be represented using another type of matrix. Bipartite graphs have two types of vertices, which I'll call row-vertices and column-vertices, for reasons that will become obvious. All edges connect one row-vertex to one column-vertex, so it's not necessary to use a full adjacency matrix connecting all possible vertex pairs. Instead, we represent the edge from the ith row-vertex to the jth column-vertex by setting the element of the matrix at row i and column j. This type of matrix is called a biadjacency matrix, and is typically denoted as B. Because the number of row vertices and column vertices can be different, the biadjacency matrix does not need to be square. The bipartite graph can be projected into a graph containing only row-nodes (or only column-nodes) by using simple matrix operations.

...

Modularity

As an example of how math is used in network science, several popular community detection algorithms (including those discussed in Chapter 7, In-Between – Communities) work by maximizing a mathematical property called modularity. Modularity is the difference between the fraction of internal edges and how many you'd expect if edges were assigned randomly (without changing vertex degrees).

Let's assume an undirected network. Given a set of vertex labels c, with corresponding vertex degrees k_i for i∊c, the expected fraction of internal edges can be approximately written as follows:

∑_i∊c ∑_j∊c k_ik_j / (2 |E|)²,

Here, |E| is the total number of edges. The true number of edges between vertices i and j is given by element A_i,j of the adjacency matrix. Summing over all communities c in partition C, the modularity Q, can be written...