## Graphs and Social Networks

# Graphs, Relations and a Matrix

**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.

## Adjacency Matrix

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

,

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.