A graph can serve as a mathematical model of a network.

Example. The internet in December 1970. Nodes are computers, connected by a link if they can directly communicate with each other. At the time, only 13 computers participated in that network.

As far as the network structure is concerned, the following diagram contains the same information, without the distracting details of the US geography.

## Simple Graphs

Definition. A (simple) graph is a pair $G = (X, E)$, consisting of a (finite) set $X$ of objects, called nodes or vertices or points, and a subset $E \subseteq \binom{X}{2}$ of links or edges.

Usually, $n$ is used to denote the number of vertices of a graph, $n = |X|$, and $m$ for the number of edges, $m = |E|$.

Here, $\binom{X}{2}$, pronounced as “$X$ choose 2”, is the set of all $2$-element subsets of $X$. (The notation is motivated by the fact that if $X$ has $n$ elements then $\binom{X}{2}$ has $\binom{n}{2} = \frac12 n(n-1)$ elements.) Obviously, $m \leq \binom{n}{2}$.

Example. $X = \{ A, B, C, D \}$ and $E = \{ AB, BC, BD, CD \}$ (where $AB$ is short for $\{ A, B \}$).

The example also illustrates a typical way how diagrams of graphs are drawn: nodes are represented by small circles, and edges by lines connecting the nodes.

A useful, algebraic, way to represent a graph is given by its adjacency matrix. This is square matrix $A$, with rows and columns corresponding to the vertices of the graph, and an entry $1$ or $0$ in row $i$, column $j$, if the corresponding vertices are joined by an edge or not. The edge $AB$ in the example above this gives an entry $1$ in row 1 (corresponding to vertex $A$) and column 2 (corresponding to vertex $B$. And another entry $1$ in row 2 column 1. The full adjacency matrix of the above graph is as follows.

$A = \left[ \begin{array}{cccc} 0&1&0&0\\\ 1&0&1&1\\\ 0&1&0&1\\\ 0&1&1&0 \end{array} \right]$

Note that $A = (a_{ij})$, like every adjacency matrix of a simple graph, is symmetric (about the diagonal): $a_{ij} = a_{ji}$ for all $i, j$. Also, all diagonal entries are $0$.

## Directed Graphs, Multigraphs

In this simple setting, two nodes are either connected or not (that is, there are no multiple links) and if node $x$ is connected to node $y$, then it is also true that $y$ is connected to $x$: the edges set up a symmetric relationship between nodes. If we want to express more complex real world relationships, we can make use of the more complex structure of directed graphs, where edges have directions (drawn as arrows), possibly pointing back to the node they came from (forming loops, or self-edges), or even with multiple edges between the same two nodes. A graph that has multiple edges between nodes is usually called a multigraph.

The adjacency matrix $A$ of a directed graph has an entry $a_{ij} = 1$ whenever there is an edge from vertex $i$ to vertex $j$ (in that order!) in the graph, and entries $0$ in all other positions. For example,

$A = \left[ \begin{array}{cccc} 0&1&0&0\\\ 0&0&1&1\\\ 0&0&0&1\\\ 0&0&0&0 \end{array} \right]$

A simple graph can be regarded as a directed graph by reading every undirected edge as two directed edges between the end points, one going forward and one coming back.

The adjacency matrix is capable of storing additional information, like weights or multiplicities of edges or loops, if that is required. We will soon see, how algebraic operations like matrix multiplication can be used to obtain information about a network from its adjacency matrix.

## Degree

The degree of a vertex $x$ in a simple graph is the number of vertices it is connected to in the graph (it’s number of friends). The degree can serve as a (simple) measure of the importance of a node in a network. The average degree of the nodes in a network depends (only) on the number $n$ of nodes, and the number $m$ of edges in the network.

Writing $k_i$ for the degree of vertex $x_i$, this number easily be determined from the adjacency matrix $A$ as the number of entries $1$ in row $i$ (or in column $i$):

$k_i = \sum_j a_{ij} = \sum_j a_{ji}$.

As every edge contributes to the degree of $2$ nodes, the sum of all degrees equals twice the number of edges:

$\sum_i k_i = 2m$,

whence the average degree is

$c = \frac1n \sum_i k_i = \frac{2m}{n}$.

## Graphs are Relations

Recall the following definitions.

Definition. A relation from a set $X$ to a set $Y$ is (nothing but) a subset $R$ of the Cartesian product $X \times Y = \{(x, y) : x \in X,\, y \in Y \}$. We say that $x \in X$ is $R$-related to $y \in Y$ whenever $(x, y) \in R$ and then write $x R y$.

The adjacency matrix of a relation $R \subseteq X \times Y$ is the matrix with one row for each element $x \in X$ and one column for each element $y \in Y$, and it has an entry $1$ in row $x$ and column $y$ if $x R y$, and entries $0$ otherwise.

In many cases, $Y = X$. If $Y = X$, we say that $R$ is a relation on $X$. Such a relation can have one or more of the following properties.

• (R) $R$ is reflexive if $xRx$ for all $x \in X$;
• (S) $R$ is symmetric if $xRy$ implies $yRx$ for all $x, y \in X$;
• (T) $R$ is transitive if $xRy$ and $yRz$ imply that $xRz$ for all $x, y, z \in X$;

• (I) $R$ is irreflexive if not $xRx$ for all $x \in X$;
• (A) $R$ is antisymmetric if $xRy$ and $yRx$ imply that $x = y$ for all $x, y \in X$.

A relation that is (RST), i.e., reflexive, symmetric and transitive, is called an equivalence relation, and it partitions the set $X$ into (mutually disjoint) parts, called equivalence classes. A relation that is (RAT) is called a partial order (such as the divides partial order on the natural numbers, or the contains relation between the subsets of a set).

In view of these notions, we can now describe simple graphs and some of their properties as follows: A simple graph with node set $X$ is a symmetric, irreflexive relation on $X$. A directed graph with node set $X$ is irreflexive if it has no loops. And it is antisymmetric if every edge has a unique direction.

The article Counting Transitive Relations (in the Journal of Integer Sequences) contains a systematic account on the various types of relations that can be distinguished by these 5 properties, and a discussion of how to count them (up to equivalence) in case the underlying set $X$ is finite.

## Composition

Relations can be composed, like functions. If $R$ is a relation from a set $X$ to a set $Y$, and if $S$ is a relation from $Y$ to a set $Z$, then the composite relation $R \circ S$ is the relation from $X$ to $Z$, defined by $x (R \circ S) z$ if there is a an element $y \in Y$ such that $x R y$ and $y S z$.

The adjacency matrix of the composite relation $R \circ S$ is essentially the (matrix) product of the adjacency matrices of the individual relations $R$ and $S$. If $A = (a_{ij})$ is the adjacency matrix of $R$, and $B = (b_{jk})$ the adjacency matrix of $S$, then the $i,k$-entry of the product $AB$ is

$(AB)_{ik} = \sum_{j} a_{ij} b_{jk}$,

which is exactly the number of elements $y \in Y$ such that $x_i R y$ and $y S z_k$. All it needs for $x_i$ to be $(R \circ S)$-related to $z_k$ is this number to be at least $1$. Hence, replacing all nonzero entries in the product matrix $AB$ with $1$ yields the adjacency matrix of the composite $R \circ S$.

Let’s write $A \circ B$ for this matrix.