Graphs and Social Networks

New Networks from Old

In many situations, simple graphs are preferred over directed graphs. A simple method of turning a directed graph into a simple graph is given by ignoring the directions of the arrows, i.e., by reading each directed edge as an undirected edge. Some information will get lost on the way. Other methods of producing a simple graph from a directed one are based on composition of relations. We will see that the same method can be used to produce simple projections from bipartite graphs.

Products of Relations

Suppose that $A$ is the (square) adjacency matrix of a (undirected) network, corresponding to a relation $R$.

Then the matrix $A \circ A$ is the adjacency matrix of the relation $R \circ R$, which is defined as follows, using $-$ as symbol for the relation $R$:

$x (R \circ R) z \iff x - y - z$ for some element $y$.

Note that in particular

$x (R \circ R) x \iff x - y - x$ for some element $y$,

that is, $x$ is $R \circ R$ related to itself, whenever $x$ is $R$-related to at least one element $y$.

If $A = (a_{ij})$ is the adjacency matrix of a relation $R$ (from $X$ to $Y$), then the transposed matrix $A^T = (a_{ji})$ is the adjacency matrix of the opposite relation

$R^{\mathrm{op}} = \{ (y, x) \in Y \times X : xRy \}$.

In a directed graph, the corresponding opposite relation is obtained by reverting all arrows:

$x R^{\mathrm{op}} y \iff y R x$.

Now, composing $R$ with its opposite yields a new relation, using $\to$ as symbol for the relation:

$x (R \circ R^{\mathrm{op}}) z \iff x \to y \leftarrow z$ for some element $y$.

The adjacency matrix of this (symmetric!) relation is the matrix $A \circ A^T$. In the context of citations between scientific papers, this network is called bibliographic coupling: two articles are linked in this way, if they both cite the same third paper.

Similarly,

$x (R^{\mathrm{op}} \circ R) z \iff x \leftarrow y \to z$ for some element $y$.

The adjacency matrix of this (symmetric!) relation is the matrix $A^T \circ A$. In the context of citations between scientific papers, this network is called the cocitation network: two articles are linked in this way, if they both are cited by the same third paper.

Note that the $x,z$-entry in the proper matrix product $A^T \cdot A$ is the number of articles $z$ citing both $x$ and $y$. In particular, the diagonal entry in row $x$ and column $x$ is the total number of articles citing $x$.

Bipartite Graphs, Affiliation Networks

A graph $G = (X, E)$ is bipartite if $X = B \sqcup W$ ($X$ is a disjoint union of $B$lack and $W$hite vertices), so that

$|e \cap B| = |e \cap W| = 1$ for all $e \in E$,

(each edge links a black vertex with a white vertex.) Bipartite networks are well suited for representing affiliation networks. Such networks are formed for example through membership in groups, letting black vertices stand for the members, the white vertices for the groups, and using edges between members and groups to link every member with all the groups they are a member of.

Here is an example of a bipartite graph.

bipartite1

However, not every diagram of a bipartite network has the white nodes neatly separated from the black ones. Here is an example of a bipartite graph arising from a chess board pattern.

bipartite2

Projections

A bipartite network can be projected onto each type of vertices: Two members are related if they are members in the same group; two groups are related if they have a member in common. In terms of adjacency matrices this works as follows.

Let $A$ be the adjacency matrix of the (undirected) bipartite graph. Then, listing the elements of the vertex set $X$ in such a way that $B$ comes first, followed by $W$, the matrix $A$ is a $2 \times 2$ block matrix:

$A = \left[ \begin{array}{cc} 0 & C \\\
C^T & 0 \end{array} \right]$,

where the blocks on the diagonal consist entirely of zeros, as there are no edges between vertices of the same color. And as $A$ is symmetric, the block below the diagonal is the transpose of the block $C$ above the diagonal.

As $A = A^T$, we have

$A^T \circ A = A \circ A^T = A \circ A = \left[ \begin{array}{cc} C \circ C^T & 0 \\\
0 & C^T \circ C \end{array} \right]$,

where $C \circ C^T$ is the adjacency matrix of the projection onto the vertex set $B$: ${\bullet} - {\circ} - {\bullet}$, and $C^T \circ C$ is the adjacency matrix of the projection onto the vertex set $W$: ${\circ} - {\bullet} - {\circ}$.

A Historical Perspective

The following TED talk illustrates the historical shift from hierarchical representations to modern network representations of data.