Graph theory basics
A graph represents a system through objects and the relationships between them. In biology, the objects may be individuals, species, genes, proteins or cells, while the relationships may represent contact, predation, regulation or another interaction.
Vertices and edges
A graph is written
\[\boxed{G=(V,E)},\]where \(V\) is the set of vertices, or nodes, and \(E\) is the set of edges.
For example, if
\[V=\{1,2,3,4\}\]and
\[E=\{\{1,2\},\{1,3\},\{3,4\}\},\]then node \(1\) is connected to nodes \(2\) and \(3\), while node \(4\) is connected only to node \(3\).
Undirected graphs
An undirected edge \(\{i,j\}\) represents a relationship with no direction. If individual \(i\) is in physical contact with individual \(j\), for example, the contact may naturally be represented as undirected.
In an undirected graph, \(i\) connected to \(j\) automatically means \(j\) is connected to \(i\).
Directed graphs
A directed edge is written
\[i\to j.\]Direction matters. In a gene-regulatory network, for example, gene \(i\) may regulate gene \(j\) without gene \(j\) regulating gene \(i\).
A directed graph is therefore appropriate whenever the biological relationship is asymmetric.
Adjacency matrix
For a graph with \(n\) nodes, the adjacency matrix is the \(n\times n\) matrix
\[A=(A_{ij}).\]For a simple unweighted graph,
\[\boxed{A_{ij}=\begin{cases}1,&\text{if there is an edge from }i\text{ to }j,\\0,&\text{otherwise.}\end{cases}}\]An adjacency-matrix example
For the undirected graph with edges
\[\{1,2\},\qquad\{1,3\},\qquad\{3,4\},\]the adjacency matrix is
\[A=\begin{pmatrix}0&1&1&0\\1&0&0&0\\1&0&0&1\\0&0&1&0\end{pmatrix}.\]The entry in row \(1\), column \(3\) is \(1\) because nodes \(1\) and \(3\) are connected.
Symmetry of an undirected adjacency matrix
For an undirected graph,
\[A_{ij}=A_{ji}.\]Therefore
\[\boxed{A=A^T}.\]A directed graph need not have a symmetric adjacency matrix.
Self-loops
An edge from a node to itself is called a self-loop. In a simple graph, self-loops are excluded, so
\[A_{ii}=0.\]Some biological network models allow self-interactions, in which case diagonal entries can be non-zero.
Degree
The degree \(k_i\) of a node in an undirected graph is the number of edges incident to it. From the adjacency matrix,
\[\boxed{k_i=\sum_{j=1}^{n}A_{ij}}.\]In the example above,
\[k_1=2,\qquad k_2=1,\qquad k_3=2,\qquad k_4=1.\]Degree measures the number of direct neighbours, not how important the node is in every possible sense.
In-degree and out-degree
For a directed graph, it is useful to distinguish the number of incoming and outgoing edges.
With the convention that \(A_{ij}=1\) represents \(i\to j\),
\[\boxed{k_i^{\mathrm{out}}=\sum_j A_{ij}},\qquad\boxed{k_i^{\mathrm{in}}=\sum_j A_{ji}}.\]The handshaking identity
Every undirected edge contributes one to the degree of each of its two endpoints. Therefore
\[\boxed{\sum_{i=1}^{n}k_i=2|E|}.\]Consequently, the mean degree is
\[\boxed{\langle k\rangle=\frac{1}{n}\sum_i k_i=\frac{2|E|}{n}}.\]Neighbours
The neighbourhood of node \(i\) is the set of nodes directly connected to it:
\[N(i)=\{j:\{i,j\}\in E\}.\]For a simple undirected graph,
\[|N(i)|=k_i.\]Walks and paths
A walk is a sequence of adjacent vertices. A path is a walk with no repeated vertices.
For example,
\[2\to1\to3\to4\]is a path in the example graph.
Paths are important because many biological processes propagate through sequences of interactions rather than only through direct neighbours.
Path length and distance
The length of a path is its number of edges. The graph distance between nodes \(i\) and \(j\), written \(d(i,j)\), is the length of a shortest path connecting them.
In the example,
\[d(2,4)=3\]through the path \(2-1-3-4\).
Connected graphs
An undirected graph is connected if every pair of vertices can be joined by a path.
If this is not true, the graph separates into connected components. A process spreading only along edges cannot pass between disconnected components unless new edges or another transmission mechanism are introduced.
Cycles
A cycle is a closed path that returns to its starting node. Cycles create alternative routes through a network and can affect spreading, feedback and robustness.
Weighted graphs
Not all interactions have equal strength. A weighted adjacency matrix may use
\[A_{ij}=w_{ij},\]where \(w_{ij}\) measures interaction intensity, contact duration, movement volume or another biologically meaningful quantity.
The weighted degree, often called node strength, is
\[\boxed{s_i=\sum_j w_{ij}}.\]Simple graphs and multigraphs
A simple graph has at most one edge between any pair of distinct vertices and no self-loops.
Other network models can allow repeated edges, producing a multigraph. This can be useful when repeated contacts are represented explicitly rather than collapsed into a single weighted edge.
Subgraphs
A subgraph contains a subset of the vertices and edges of a larger graph. Subgraphs allow us to study a particular group, community or local interaction pattern within a biological network.
Matrix powers and walks
The adjacency matrix contains more information than direct connections. For an unweighted graph, the entry
\[(A^m)_{ij}\]counts the number of walks of length \(m\) from node \(i\) to node \(j\).
For example,
\[(A^2)_{ij}=\sum_k A_{ik}A_{kj}\]counts the possible two-edge walks \(i\to k\to j\).
Why graph structure matters biologically
Two populations can contain the same number of individuals and the same number of contacts overall while having very different arrangements of those contacts.
One may contain highly connected hubs, another may be divided into communities, and another may be almost regular. These structural differences can change epidemic spread, gene-regulatory behaviour, ecological robustness and intervention effectiveness.
Graph representation versus biological mechanism
A graph describes interaction structure, but the graph alone does not specify the biological dynamics.
For an epidemic, for example, the network says which transmissions are possible, while infection and recovery rules determine how disease states change over time.
Transition to biological networks
The definitions developed here apply to many systems. The next lesson asks how nodes and edges should be interpreted in specific biological settings and what information can be learned from representing biology as a network.