9 Network Analysis
Chapter Aim
Chapter 08 treated a network as an estimated statistical object: an adjacency matrix, a partial-correlation matrix, or a sparse precision matrix was learned from data. Chapter 09 starts after this estimation step. The question is no longer only whether an edge should be present. The question is what can be learned from the graph once its nodes and edges have been defined.
This distinction is essential. Network analysis can summarize a graph by degrees, paths, modules, centralities, robustness curves, or comparisons to reference graph models. None of these quantities has a biological meaning by itself. A high-degree taxon is only a high-degree taxon relative to the preprocessing, association measure, sparsification rule, and node definition used to construct the graph. A module is only a module in the graph that was actually analyzed. Chapter 09 therefore keeps the construction map visible while introducing the mathematical summaries used to characterize networks.
Notation follows the shared convention in the notation chapter. Vectors are columns by default, row vectors are written with transposes, and dimensions should be checked whenever matrices are multiplied, transformed, modeled, or decomposed.
For graph terminology, graph encodings, graphs constructed from data, and biological network workflows, see MSMB Networks and Trees, especially the sections on graph encodings (MSMB Networks Graph Encoding), graphs from data (MSMB Networks Graphs From Data), gene set enrichment as a bridge to network thinking (MSMB Networks Gene Sets), and high-scoring subgraphs (MSMB Networks Significant Subgraphs). The transition from association estimation to adjacency matrices follows the modular network-construction view used in NetCoMi (Peschel et al. 2021), with microbial network computation and comparison practiced in Exercise Sheet 6, Task 2 (Exercise Sheet 06 2026). General network summaries and null-model thinking are connected to small-world networks (Watts and Strogatz 1998; Humphries et al. 2006), modularity and communities (Girvan and Newman 2002; Newman 2006), graphlet-based graph comparison (Hočevar and Demšar 2014; Yaveroğlu et al. 2014), and robustness under node removal (Albert et al. 2000; Iyer et al. 2013).
Learning Goals
After this chapter, students should be able to describe the map from a learned association or precision matrix to a graph, distinguish signed, unsigned, weighted, unweighted, and dissimilarity-based networks, compute degree, density, path length, diameter, and clustering coefficients, explain the difference between degree, closeness, betweenness, and eigenvector centrality, define modularity for a proposed community assignment, compare network summaries to null models, describe graphlet-based graph comparison at a high level, and interpret robustness curves under random and targeted node removal.
9.1 From Learned Matrices To Networks
Network analysis begins with a graph
\[\begin{equation} G=(V,E), \qquad V=\{1,\ldots,p\}, \label{eq:ch09-graph-object} \end{equation}\]
where the nodes are features: genes, proteins, metabolites, taxa, peaks, or other molecular variables. In this chapter, \(p\) is the number of nodes, inherited from the number of columns of the data matrix. For an undirected unweighted graph, the adjacency matrix is
\[\begin{equation} A\in\{0,1\}^{p\times p}, \qquad A=A^\top, \qquad A_{jj}=0. \label{eq:ch09-binary-adjacency} \end{equation}\]
The set of edges is
\[\begin{equation} E = \left\{ (j,\ell): 1\leq j<\ell\leq p, A_{j\ell}=1 \right\}. \label{eq:ch09-edge-set-from-adjacency} \end{equation}\]
The number of edges is denoted by
\[\begin{equation} q = |E| = \sum_{1\leq j<\ell\leq p} A_{j\ell}. \label{eq:ch09-number-of-edges} \end{equation}\]
Chapter 08 often produced more than a binary graph. A sparse Gaussian graphical model may produce an estimated precision matrix \(\hat{\Omega}\) and a partial-correlation matrix \(\hat{P}\) with entries
\[\begin{equation} \hat{P}_{j\ell} = - \frac{\hat{\Omega}_{j\ell}} {\sqrt{\hat{\Omega}_{jj}\hat{\Omega}_{\ell\ell}}}, \qquad j\neq \ell. \label{eq:ch09-partial-correlation-from-precision} \end{equation}\]
This matrix is an association matrix. It can be analyzed directly as a weighted signed graph, or it can be transformed into an unweighted adjacency matrix. More generally, let
\[\begin{equation} R = (r_{j\ell}) \in[-1,1]^{p\times p} \label{eq:ch09-association-matrix} \end{equation}\]
denote a symmetric association matrix. The entries may be correlations, SparCC associations, proportionality scores transformed to an association scale, partial correlations, or conditional-dependence scores. The important point is that the mathematical object used for network analysis is not uniquely determined by \(R\). One must still decide which graph to construct.
A simple unweighted signed-threshold graph uses
\[\begin{equation} A_{j\ell}^{\mathrm{thr}} = \mathbf{1} \left\{ |r_{j\ell}|\geq \tau \right\}, \qquad j\neq \ell. \label{eq:ch09-threshold-adjacency} \end{equation}\]
The corresponding weighted graph can keep the association values on selected edges:
\[\begin{equation} W_{j\ell}^{\mathrm{thr}} = r_{j\ell} \mathbf{1} \left\{ |r_{j\ell}|\geq \tau \right\}. \label{eq:ch09-threshold-weighted-adjacency} \end{equation}\]
If the sign matters, positive and negative edge sets can be recorded separately:
\[\begin{equation} E^+ = \left\{ (j,\ell): r_{j\ell}\geq \tau \right\}, \qquad E^- = \left\{ (j,\ell): r_{j\ell}\leq -\tau \right\}. \label{eq:ch09-positive-negative-edge-sets} \end{equation}\]
Some graph summaries, especially shortest-path summaries, require nonnegative dissimilarities rather than signed associations. Two common transformations emphasize different biological questions. An unsigned dissimilarity treats strong positive and strong negative associations as close:
\[\begin{equation} d_{j\ell}^{\mathrm{unsigned}} = 1-r_{j\ell}^{2}. \label{eq:ch09-unsigned-dissimilarity} \end{equation}\]
A signed dissimilarity treats positive association as close and negative association as far:
\[\begin{equation} d_{j\ell}^{\mathrm{signed}} = \frac{1-r_{j\ell}}{2}. \label{eq:ch09-signed-dissimilarity} \end{equation}\]
Thus the same partial-correlation matrix can give several network objects: a signed weighted association network, an unsigned co-association network, a binary threshold graph, or a dissimilarity graph used for path-based summaries. NetCoMi makes this modular distinction explicit: preprocessing, zero handling, normalization, association estimation, sparsification, adjacency construction, network analysis, visualization, and comparison are separate choices in one workflow (Peschel et al. 2021). The companion computation is the NetCoMi exercise in Exercise Sheet 6, Task 2, where microbial association networks are constructed, analyzed, visualized, and compared. This is why a network result should report not only \(A\), but also the matrix from which it was derived.
A compact analysis object is therefore
\[\begin{equation} \mathcal{G} = \left( V, R, D, W, A \right), \label{eq:ch09-network-analysis-object} \end{equation}\]
where \(R\) is an association matrix, \(D\) is a dissimilarity matrix if path lengths require one, \(W\) is a weighted adjacency matrix, and \(A\) is the binary adjacency matrix used for unweighted summaries. In practice not all components are needed, but the analysis should state which ones are used.
9.2 Node-Level Summaries
The simplest node-level property is degree. For an undirected unweighted graph, the degree of node \(j\) is
\[\begin{equation} k_j = \sum_{\ell=1}^{p} A_{j\ell}. \label{eq:ch09-degree} \end{equation}\]
The degree distribution is the empirical distribution of the \(k_j\) values:
\[\begin{equation} \hat{F}_{k}(t) = \frac{1}{p} \sum_{j=1}^{p} \mathbf{1} \left\{ k_j\leq t \right\}. \label{eq:ch09-degree-distribution} \end{equation}\]
Degree is often the first summary plotted because it immediately distinguishes dense, hub-dominated, banded, random-like, and modular graphs. In a microbial association network, a high-degree taxon is sometimes called a hub. This term should be used carefully. A hub is a graph-theoretic statement, not automatically a keystone species or causal driver. A taxon can have high degree because it is broadly associated, because it is abundant and easy to estimate, because the sparsification threshold is permissive, or because it sits in a compositional structure that induces many associations.
For a weighted graph with nonnegative edge weights \(w_{j\ell}\geq 0\), the analogous node summary is strength:
\[\begin{equation} s_j = \sum_{\ell=1}^{p} w_{j\ell}. \label{eq:ch09-node-strength} \end{equation}\]
If \(W\) contains signed associations, it is usually better to separate positive and negative strength:
\[\begin{equation} s_j^+ = \sum_{\ell=1}^{p} \max(w_{j\ell},0), \qquad s_j^- = \sum_{\ell=1}^{p} \max(-w_{j\ell},0). \label{eq:ch09-signed-strength} \end{equation}\]
This separation is useful because positive and negative microbial associations often have different interpretations. Positive associations can reflect shared habitat, shared response to unmeasured covariates, cross-feeding, or co-colonization. Negative associations can reflect exclusion, different environmental preferences, competition, or the closure effect of compositions. Network analysis does not decide between these mechanisms; it summarizes the graph produced by the chosen statistical construction.
9.3 Global Network Size And Density
The edge density of an undirected graph is the fraction of possible edges that are present:
\[\begin{equation} \delta(G) = \frac{2q}{p(p-1)}. \label{eq:ch09-edge-density} \end{equation}\]
Density is deceptively important. Many network summaries change strongly with density. A graph with more edges will usually have shorter paths, higher degrees, larger connected components, and often higher clustering. Therefore comparisons between biological groups should either control for the construction rule or compare against a null model that preserves relevant baseline quantities such as \(p\), \(q\), or the degree sequence.
The connected components of \(G\) are maximal node sets in which every pair of nodes is joined by some path. If \(\mathcal{C}(G)\) is the collection of connected components and \(C_{\max}\) is the largest component, then the relative largest connected component size is
\[\begin{equation} L_{\max}(G) = \frac{|C_{\max}|}{p}. \label{eq:ch09-largest-connected-component} \end{equation}\]
This quantity is especially useful for sparse biological networks because many path-based summaries are unstable or undefined when a graph fragments into many components.
9.4 Paths, Diameter, And Clustering
A path between nodes \(j\) and \(\ell\) is a sequence of adjacent nodes connecting them. For an unweighted graph, let
\[\begin{equation} \operatorname{dist}_{G}(j,\ell) = \text{length of the shortest path from }j\text{ to }\ell \label{eq:ch09-shortest-path} \end{equation}\]
when \(j\) and \(\ell\) are connected. If they are not connected, the distance is infinite. For disconnected biological graphs, one often averages only over connected pairs:
\[\begin{equation} \bar{L}(G) = \frac{1}{|\mathcal{P}_{c}|} \sum_{(j,\ell)\in\mathcal{P}_{c}} \operatorname{dist}_{G}(j,\ell), \label{eq:ch09-average-shortest-path-connected} \end{equation}\]
where
\[\begin{equation} \mathcal{P}_{c} = \left\{ (j,\ell): 1\leq j<\ell\leq p, \operatorname{dist}_{G}(j,\ell)<\infty \right\}. \label{eq:ch09-connected-node-pairs} \end{equation}\]
The diameter is the longest finite shortest-path distance:
\[\begin{equation} \operatorname{diam}(G) = \max_{(j,\ell)\in\mathcal{P}_{c}} \operatorname{dist}_{G}(j,\ell). \label{eq:ch09-diameter} \end{equation}\]
For weighted networks, shortest paths require edge lengths, not association strengths. If \(s_{j\ell}\) is a similarity, an edge length might be \(1/s_{j\ell}\) or a signed or unsigned dissimilarity. This choice changes path-based summaries. A strong negative association may be close in an unsigned network but far in a signed network, as in Equations \(\ref{eq:ch09-unsigned-dissimilarity}\) and \(\ref{eq:ch09-signed-dissimilarity}\).
The local clustering coefficient measures how close the neighbors of node \(j\) are to forming a clique. Let \(N(j)=\{\ell:A_{j\ell}=1\}\) and \(k_j=|N(j)|\). The number of triangles touching node \(j\) is
\[\begin{equation} T_j = \sum_{\ell<m} A_{j\ell}A_{jm}A_{\ell m}. \label{eq:ch09-node-triangles} \end{equation}\]
For \(k_j\geq 2\), the local clustering coefficient is
\[\begin{equation} C_j = \frac{2T_j}{k_j(k_j-1)}. \label{eq:ch09-local-clustering-coefficient} \end{equation}\]
The average clustering coefficient is
\[\begin{equation} \bar{C}(G) = \frac{1}{p} \sum_{j=1}^{p} C_j, \label{eq:ch09-average-clustering-coefficient} \end{equation}\]
with \(C_j\) usually set to zero or treated as undefined when \(k_j<2\). High clustering means that neighbors of a node tend to be connected to each other. In biological association networks this can indicate modules, shared environmental drivers, taxonomic relatedness, pathway structure, or technical dependencies. The statistic is useful, but interpretation again depends on the graph construction.
9.5 Centrality
Centrality measures rank nodes by different graph-theoretic notions of importance. Degree centrality is local:
\[\begin{equation} C_D(j) = \frac{k_j}{p-1}. \label{eq:ch09-degree-centrality} \end{equation}\]
It asks how many neighbors node \(j\) has. Closeness centrality is path-based. A robust version for disconnected graphs is harmonic closeness:
\[\begin{equation} C_H(j) = \frac{1}{p-1} \sum_{\ell\neq j} \frac{1}{\operatorname{dist}_{G}(j,\ell)}, \label{eq:ch09-harmonic-closeness} \end{equation}\]
where \(1/\infty=0\). A node has high harmonic closeness if it is close, in shortest-path distance, to many other nodes.
Betweenness centrality asks whether a node lies on shortest paths between other nodes. Let \(\sigma_{ab}\) be the number of shortest paths from \(a\) to \(b\), and let \(\sigma_{ab}(j)\) be the number of those paths that pass through \(j\). Then
\[\begin{equation} C_B(j) = \sum_{\substack{a<b\\a\neq j,\ b\neq j}} \frac{\sigma_{ab}(j)}{\sigma_{ab}}. \label{eq:ch09-betweenness-centrality} \end{equation}\]
Betweenness is sensitive to small changes in sparse graphs because adding or removing a few edges can reroute many shortest paths. In inferred biological networks, this makes betweenness useful as a descriptive diagnostic but risky as a stand-alone claim about biological control.
Eigenvector centrality assigns high scores to nodes connected to other high-scoring nodes. For a nonnegative adjacency or weight matrix \(A\), it is defined by
\[\begin{equation} A u = \lambda_{\max} u, \qquad u_j\geq 0, \label{eq:ch09-eigenvector-centrality} \end{equation}\]
where \(\lambda_{\max}\) is the largest eigenvalue. This measure is global: a node can score highly not only because it has many neighbors, but because it is connected to a central region of the graph.
Different centralities answer different questions. A node can have high degree but low betweenness if it lies inside a dense module. A node can have modest degree but high betweenness if it connects two otherwise separated modules. For microbiome networks, “keystone” language should therefore be linked to the specific centrality used, and ideally to robustness analyses or independent biological validation.
9.6 Communities And Modularity
Many biological graphs appear modular: nodes form groups with many within-group edges and fewer between-group edges. Let \(g_j\in\{1,\ldots,K\}\) denote the community label assigned to node \(j\). The modularity of this partition is
\[\begin{equation} Q(g) = \frac{1}{2q} \sum_{j=1}^{p} \sum_{\ell=1}^{p} \left[ A_{j\ell} - \frac{k_jk_\ell}{2q} \right] \mathbf{1} \left\{ g_j=g_\ell \right\}. \label{eq:ch09-modularity} \end{equation}\]
The term \(A_{j\ell}\) counts observed within-community edges. The term \(k_jk_\ell/(2q)\) is the expected number of such edges under a degree-preserving random-graph baseline. Modularity is therefore not merely a count of within-community edges; it asks whether there are more within-community edges than expected from the degrees.
Community detection methods often search for a partition with large modularity, but the result is not unique in general. Different algorithms can find different partitions with similar modularity. Biological interpretation should therefore focus on stable and interpretable modules: groups enriched for pathways, taxonomic groups, environmental niches, protein complexes, or coherent covariate associations. A complementary perspective is given by high-scoring subgraphs: when nodes carry scores from a statistical analysis, one can search for connected regions of a known network that concentrate signal (MSMB Networks Significant Subgraphs).
9.7 Small-World Structure And Null Models
Network summaries become more meaningful when compared to a reference model. Small-world analysis is a classic example. Informally, a small-world network has short path lengths, like a random graph, but high clustering, like a locally organized graph (Watts and Strogatz 1998). Let \(\bar{C}(G)\) be the average clustering coefficient and \(\bar{L}(G)\) the average shortest-path length. Let \(\bar{C}_{0}\) and \(\bar{L}_{0}\) be corresponding averages under a null model. A common small-world coefficient is
\[\begin{equation} \sigma_{\mathrm{SW}}(G) = \frac{\bar{C}(G)/\bar{C}_{0}} {\bar{L}(G)/\bar{L}_{0}}. \label{eq:ch09-small-world-coefficient} \end{equation}\]
The null model matters. An Erdos-Renyi graph with the same number of nodes and edges preserves only coarse density. A configuration-model graph preserves the degree sequence more closely. If the observed graph has hubs, then comparing to a null model that ignores hubs can overstate how surprising its clustering or path length is. This is the broader lesson: a network property is not simply large or small; it is large or small relative to a reference distribution.
9.8 Generative Null Models For Networks
A generative graph model is a probability distribution on graphs. In network analysis, such models are often used as null models: they define what network structure would look like if only a limited set of graph properties were preserved. Let
\[\begin{equation} G_0 \sim \mathcal{M}_0(\theta_0) \label{eq:ch09-null-graph-model} \end{equation}\]
denote a graph drawn from a null model \(\mathcal{M}_0\) with parameter \(\theta_0\). The model parameter should usually be estimated or chosen to match a property of the observed graph \(G\), such as \(p\), \(q\), density, mean degree, or the degree sequence.
9.8.1 Erdos-Renyi Graphs
The Erdos-Renyi model is the simplest density-preserving random graph model. In the \(G(p,\pi)\) version, the node set is fixed as \(V=\{1,\ldots,p\}\) and each possible undirected edge is included independently:
\[\begin{equation} A_{j\ell} \sim \operatorname{Bernoulli}(\pi), \qquad 1\leq j<\ell\leq p. \label{eq:ch09-er-edge-model} \end{equation}\]
The expected number of edges is
\[\begin{equation} \mathbb{E}(|E|) = \binom{p}{2}\pi. \label{eq:ch09-er-expected-edges} \end{equation}\]
To match an observed graph with \(q\) edges, choose
\[\begin{equation} \hat{\pi} = \frac{2q}{p(p-1)} = \delta(G). \label{eq:ch09-er-density-estimator} \end{equation}\]
The procedure is: fix the observed number of nodes \(p\), estimate \(\hat{\pi}\) from the observed density, sample independent Bernoulli edges for all \(j<\ell\), symmetrize the adjacency matrix, and set the diagonal to zero. This null model preserves only the expected density. It does not preserve hubs, clustering, geometry, or community structure.
The \(G(p,q)\) version preserves the number of edges exactly rather than in expectation. It samples uniformly from all graphs with \(p\) nodes and \(q\) edges:
\[\begin{equation} \Pr(G_0=g) = \binom{\binom{p}{2}}{q}^{-1} \label{eq:ch09-er-fixed-edge-probability} \end{equation}\]
for every graph \(g\) with exactly \(q\) undirected edges. The procedure is: list all \(\binom{p}{2}\) possible edges, sample \(q\) of them uniformly without replacement, and form the adjacency matrix.
9.8.2 Random Geometric Graphs In Two Or Three Dimensions
A random geometric graph creates edges because nodes are close in an unobserved or observed geometric space. This is useful as a reference when locality matters, for example spatial proximity, habitat gradients, tissue neighborhoods, or latent ecological niches.
For dimension \(d\in\{2,3\}\), sample node positions
\[\begin{equation} u_j \sim \operatorname{Uniform}([0,1]^d), \qquad j=1,\ldots,p. \label{eq:ch09-rgg-node-positions} \end{equation}\]
Given a radius \(r>0\), connect nodes whose Euclidean distance is at most \(r\):
\[\begin{equation} A_{j\ell} = \mathbf{1} \left\{ \|u_j-u_\ell\|_2\leq r \right\}, \qquad j\neq \ell. \label{eq:ch09-rgg-adjacency} \end{equation}\]
For a two-dimensional random geometric graph, \(d=2\) and \(u_j=(u_{j1},u_{j2})^\top\). For a three-dimensional random geometric graph, \(d=3\) and \(u_j=(u_{j1},u_{j2},u_{j3})^\top\). The procedure is: choose the dimension \(d\), sample \(p\) positions in the unit square or cube, choose \(r\), and connect all pairs within radius \(r\).
To match the observed graph density, choose \(r\) so that the simulated expected edge density is close to \(\delta(G)\). In practice this can be done by simulation or by solving
\[\begin{equation} \mathbb{E}_{r,d} \left[ \delta(G_0) \right] \approx \delta(G). \label{eq:ch09-rgg-radius-matching} \end{equation}\]
Random geometric graphs usually have high clustering because “nearby” is transitive: if node \(j\) is close to both \(\ell\) and \(m\), then \(\ell\) and \(m\) are often close to each other. They are therefore useful null models when one wants to ask whether observed clustering is more than what would be expected from spatial or latent-space proximity alone.
9.8.3 Watts-Strogatz Small-World Graphs
The Watts-Strogatz construction, associated with Duncan Watts and Steven Strogatz, interpolates between a regular lattice and a random graph (Watts and Strogatz 1998). It is designed to produce graphs with high clustering and short path lengths.
Start with \(p\) nodes on a cycle. Choose an even integer \(K\) with \(2\leq K<p\). Each node is connected to \(K/2\) nearest neighbors on each side:
\[\begin{equation} A_{j\ell}^{(0)} = \mathbf{1} \left\{ 1\leq \operatorname{dist}_{\mathrm{cycle}}(j,\ell) \leq \frac{K}{2} \right\}. \label{eq:ch09-watts-strogatz-lattice} \end{equation}\]
Here \(\operatorname{dist}_{\mathrm{cycle}}(j,\ell)\) is the shortest circular distance between nodes \(j\) and \(\ell\). The initial graph has degree \(K\) at every node and strong local clustering.
Then rewire edges with probability \(\rho_{\mathrm{rewire}}\). For each edge \((j,\ell)\) in a systematic traversal, with probability \(\rho_{\mathrm{rewire}}\) remove that edge and replace it by a new edge \((j,m)\), where \(m\) is sampled uniformly from nodes not equal to \(j\) and not already adjacent to \(j\):
\[\begin{equation} (j,\ell) \longmapsto (j,m) \quad \text{with probability } \rho_{\mathrm{rewire}}. \label{eq:ch09-watts-strogatz-rewiring} \end{equation}\]
The procedure is: construct the regular ring lattice, traverse its edges once, independently decide whether to rewire each edge, and avoid self-loops and duplicate edges. When \(\rho_{\mathrm{rewire}}=0\), the graph is a regular lattice. When \(\rho_{\mathrm{rewire}}\) is large, the graph becomes more random. For small positive \(\rho_{\mathrm{rewire}}\), a few long-range shortcuts can sharply reduce path lengths while leaving much of the local clustering intact.
9.8.4 Scale-Free Graphs By Preferential Attachment
Scale-free graph models are designed to generate heavy-tailed degree distributions. A standard preferential-attachment construction grows the network one node at a time. Begin with a small connected graph \(G_{m_0}\) on \(m_0\) nodes. At time \(t=m_0+1,\ldots,p\), add a new node \(t\) and attach it to \(m\) existing nodes, where \(m\leq m_0\). Existing node \(j\) is selected with probability proportional to its current degree:
\[\begin{equation} \Pr(t\text{ connects to }j\mid G_{t-1}) = \frac{k_j(t-1)} { \sum_{\ell=1}^{t-1} k_\ell(t-1) }. \label{eq:ch09-preferential-attachment-probability} \end{equation}\]
The procedure is: choose \(m_0\) and \(m\), initialize a connected seed graph, repeatedly add a new node, sample \(m\) distinct existing targets using degree-proportional probabilities, and add the corresponding edges. Nodes that already have high degree are more likely to receive new edges, producing a “rich get richer” mechanism.
A scale-free degree distribution is often summarized by a power law,
\[\begin{equation} \Pr(K=k) \propto k^{-\alpha}, \qquad k\geq k_{\min}, \label{eq:ch09-power-law-degree} \end{equation}\]
for some exponent \(\alpha>1\). In practice, a heavy-tailed degree distribution should not be asserted from a log-log plot alone. Biological networks are finite, inferred with error, and strongly affected by filtering and sparsification. Preferential-attachment graphs are best used as a mechanistic reference for hub-dominated structure, not as proof that the biological system literally grew by preferential attachment.
9.8.5 Sticky And Configuration Models
The configuration model is a degree-sequence-preserving null model. It starts from a target degree sequence
\[\begin{equation} k_1,\ldots,k_p, \qquad \sum_{j=1}^{p} k_j = 2q. \label{eq:ch09-configuration-degree-sequence} \end{equation}\]
The stub-matching construction gives node \(j\) exactly \(k_j\) half-edges, or stubs. All \(2q\) stubs are then randomly paired to form edges. The procedure is: create \(k_j\) stubs for each node, sample a uniformly random perfect matching of all stubs, collapse each matched pair into an edge, and then decide how to handle self-loops and multi-edges. If one rejects self-loops and multi-edges until a simple graph is obtained, the result is a simple graph with the target degree sequence, although the rejection step can become inefficient for very heterogeneous degrees.
The sticky model is a related expected-degree model. Assign each node a nonnegative stickiness parameter \(\theta_j\). Conditional on these parameters, edges are sampled independently with probabilities proportional to the product of node stickiness values:
\[\begin{equation} \Pr(A_{j\ell}=1\mid \theta) = \min \left\{ 1,\, c\theta_j\theta_\ell \right\}, \qquad j<\ell. \label{eq:ch09-sticky-edge-probability} \end{equation}\]
Here \(c>0\) controls the overall density. If \(\theta_j\) is chosen to be related to the observed degree \(k_j\), then high-degree nodes in the observed graph are also likely to have high expected degree in the null graph. The expected degree of node \(j\) is
\[\begin{equation} \mathbb{E}(K_j\mid \theta) = \sum_{\ell\neq j} \Pr(A_{j\ell}=1\mid \theta). \label{eq:ch09-sticky-expected-degree} \end{equation}\]
The procedure is: estimate or choose \(\theta_j\) from node-level propensities such as degree, choose \(c\) to match the observed density or expected edge count, and sample edges independently using Equation \(\ref{eq:ch09-sticky-edge-probability}\). Compared with Erdos-Renyi graphs, sticky and configuration models preserve hub structure much more strongly. They are therefore useful when the scientific question is whether clustering, modularity, robustness, or graphlet structure exceeds what would be expected from the degree sequence alone.
9.9 Fitting A Null Model To An Observed Graph
In practice, a null model is fitted with respect to an observed graph. Let \(G_{\mathrm{obs}}=(V,E_{\mathrm{obs}})\) be the graph obtained from the network-construction step, with adjacency matrix \(A_{\mathrm{obs}}\). Its basic size summaries are
\[\begin{equation} p_{\mathrm{obs}} = |V|, \qquad q_{\mathrm{obs}} = |E_{\mathrm{obs}}|. \label{eq:ch09-observed-graph-size} \end{equation}\]
The general fitting workflow is:
- choose the graph property to preserve;
- estimate the null-model parameter from \(G_{\mathrm{obs}}\);
- simulate many graphs from the fitted null model;
- compute the same statistic on the observed and simulated graphs;
- compare the observed statistic to the simulated reference distribution.
Mathematically, the fitted null model is
\[\begin{equation} \hat{\theta}_{0} = \hat{\theta}_{0}(G_{\mathrm{obs}}), \qquad G_0^{(b)} \sim \mathcal{M}_0(\hat{\theta}_{0}), \qquad b=1,\ldots,B. \label{eq:ch09-fitted-null-model-simulation} \end{equation}\]
For an Erdos-Renyi \(G(p,\pi)\) null, the fitted parameter is
\[\begin{equation} \hat{\theta}_{0}^{\mathrm{ER}} = \left( p_{\mathrm{obs}}, \hat{\pi} \right), \qquad \hat{\pi} = \frac{2q_{\mathrm{obs}}} {p_{\mathrm{obs}}(p_{\mathrm{obs}}-1)}. \label{eq:ch09-fitted-er-parameters} \end{equation}\]
For a random geometric graph in dimension \(d\), the fitted parameter is
\[\begin{equation} \hat{\theta}_{0}^{\mathrm{RGG}} = \left( p_{\mathrm{obs}}, d, \hat{r} \right), \qquad \mathbb{E}_{\hat{r},d} \left[ \delta(G_0) \right] \approx \delta(G_{\mathrm{obs}}). \label{eq:ch09-fitted-rgg-parameters} \end{equation}\]
For a Watts-Strogatz model, choose \(K\) to match the observed mean degree as closely as possible,
\[\begin{equation} \hat{K} \approx \frac{2q_{\mathrm{obs}}}{p_{\mathrm{obs}}}, \label{eq:ch09-fitted-watts-strogatz-degree} \end{equation}\]
usually rounded to a feasible even integer. The rewiring parameter can then be chosen by matching a target statistic, for example the observed average path length, clustering coefficient, or small-world coefficient:
\[\begin{equation} \hat{\rho}_{\mathrm{rewire}} = \arg\min_{\rho\in[0,1]} \left| \mathbb{E}_{\rho} \left[ T(G_0) \right] - T(G_{\mathrm{obs}}) \right|. \label{eq:ch09-fitted-watts-strogatz-rho} \end{equation}\]
Here \(T(G)\) is the statistic chosen for fitting. If the model is used strictly as a null model, one should avoid fitting the same statistic that will later be used as the test statistic; otherwise the comparison is circular. For example, one may match \(p\) and \(q\) and then ask whether clustering is unusually high, or preserve the degree sequence and ask whether modularity is unusually high.
For a preferential-attachment scale-free model, the fitted parameter is often chosen to match the observed size and approximate mean degree. Since each new node contributes \(m\) edges, the mean degree is approximately \(2m\), so one can set
\[\begin{equation} \hat{m} = \operatorname{round} \left( \frac{q_{\mathrm{obs}}}{p_{\mathrm{obs}}} \right), \label{eq:ch09-fitted-preferential-attachment-m} \end{equation}\]
with a small seed graph size \(m_0\geq \hat{m}\). More detailed fitting can compare the observed degree distribution to simulated degree distributions, but the basic use here is as a hub-generating reference model.
For a configuration model, the fitted parameter is the observed degree sequence itself:
\[\begin{equation} \hat{\theta}_{0}^{\mathrm{conf}} = \left( k_1^{\mathrm{obs}}, \ldots, k_{p_{\mathrm{obs}}}^{\mathrm{obs}} \right), \qquad k_j^{\mathrm{obs}} = \sum_{\ell=1}^{p_{\mathrm{obs}}} A_{\mathrm{obs},j\ell}. \label{eq:ch09-fitted-configuration-parameters} \end{equation}\]
For a sticky expected-degree model, a simple choice is to set \(\theta_j\) proportional to the observed degree and then choose \(c\) to match the expected number of edges:
\[\begin{equation} \hat{\theta}_j = k_j^{\mathrm{obs}}, \qquad \sum_{1\leq j<\ell\leq p_{\mathrm{obs}}} \min \left\{ 1,\, \hat{c}\hat{\theta}_j\hat{\theta}_\ell \right\} \approx q_{\mathrm{obs}}. \label{eq:ch09-fitted-sticky-parameters} \end{equation}\]
Once the null graphs have been generated, compute the statistic of interest on each graph:
\[\begin{equation} T_{\mathrm{obs}} = T(G_{\mathrm{obs}}), \qquad T_b = T(G_0^{(b)}), \qquad b=1,\ldots,B. \label{eq:ch09-null-statistic-simulation} \end{equation}\]
The resulting values \(T_1,\ldots,T_B\) are the reference distribution induced by the fitted null model. For small-worldness, a typical statistic is \(\sigma_{\mathrm{SW}}(G)\) from Equation \(\ref{eq:ch09-small-world-coefficient}\), or the pair \(\left(\bar{C}(G),\bar{L}(G)\right)\). In ecological-network analysis, this workflow is often used to ask whether an observed microbial or ecological graph has more clustering and shorter paths than expected under reference graphs with the same size or density. The accompanying ecological-network example applies exactly this logic to small-worldness: compute the observed summary, generate reference networks, recompute the summary, and compare the observed value to the null distribution.
If \(T(G)\) is any graph statistic and \(G^{(1)}_0,\ldots,G^{(B)}_0\) are null graphs, a simulation-based upper-tail p-value can be written as
\[\begin{equation} \hat{p}_{\mathrm{null}} = \frac{ 1+ \sum_{b=1}^{B} \mathbf{1} \left\{ T(G^{(b)}_0)\geq T(G) \right\} } {B+1}. \label{eq:ch09-null-model-p-value} \end{equation}\]
This equation is useful beyond small-world analysis. The same logic applies to clustering, modularity, robustness, graphlet summaries, or any other statistic where the absolute value is hard to interpret. For biological networks, the null model should preserve the aspects of the construction that are not under scientific investigation, such as node count, edge count, degree distribution, or group-specific sparsity.
9.10 Comparing Networks
Network comparison appears in at least three forms. First, one may compare two networks from two biological groups. Second, one may compare an observed network to networks generated from a null model. Third, one may compare many networks using a summary-vector embedding.
Let \(G^{(1)}\) and \(G^{(2)}\) be two graphs with the same node set. At the edge level, a simple difference of association matrices is
\[\begin{equation} \Delta R = R^{(1)}-R^{(2)}. \label{eq:ch09-association-difference-matrix} \end{equation}\]
A differential association network can then be defined by thresholding this difference:
\[\begin{equation} A_{j\ell}^{\Delta} = \mathbf{1} \left\{ |\Delta R_{j\ell}|\geq \tau_{\Delta} \right\}. \label{eq:ch09-differential-adjacency} \end{equation}\]
Statistical tests for differential associations require care because many pairs are tested simultaneously and because the association estimates are themselves products of normalization and sparsification choices. This is one reason NetCoMi separates network construction, network analysis, and network comparison in its workflow (Peschel et al. 2021).
At the graph-summary level, define a vector of summaries
\[\begin{equation} h(G) = \left( \delta(G), L_{\max}(G), \bar{C}(G), \bar{L}(G), Q(G), \ldots \right)^\top. \label{eq:ch09-graph-summary-vector} \end{equation}\]
Two networks can then be compared by a distance between summaries:
\[\begin{equation} d_{\mathrm{summary}}(G^{(a)},G^{(b)}) = \left\| h(G^{(a)})-h(G^{(b)}) \right\|_2. \label{eq:ch09-summary-distance} \end{equation}\]
This heuristic is useful when many graphs are available, for example networks constructed across body sites, time points, habitats, or perturbation conditions. After computing pairwise distances between graphs, one can use the dimensionality-reduction tools from Chapter 04 to visualize relationships among graphs.
9.11 Graphlets And Graphlet Correlation Distance
Graphlet-based methods provide a richer comparison by counting small induced subgraphs. A graphlet is a small connected induced subgraph, for example a two-node edge, a three-node path, a triangle, a four-node star, or a square. In contrast to a single global statistic such as density or average clustering, graphlets describe local wiring patterns. They are useful because two networks can have similar degree distributions and still be built from different local motifs.
Let \(\mathcal{H}_m\) denote a collection of connected graphlets with at most \(m\) nodes. For a graphlet \(H\in\mathcal{H}_m\), let
\[\begin{equation} N_H(G) = \#\left\{ U\subseteq V: G[U]\cong H \right\} \label{eq:ch09-graphlet-count} \end{equation}\]
be the number of induced copies of \(H\) in \(G\). Here \(G[U]\) is the subgraph induced by the node set \(U\), and \(\cong\) denotes graph isomorphism. The vector of graphlet counts is
\[\begin{equation} g_m(G) = \left( N_H(G) \right)_{H\in\mathcal{H}_m}. \label{eq:ch09-graphlet-count-vector} \end{equation}\]
Raw graphlet counts depend strongly on graph size and density. Graphlet correlation methods therefore move from graph-level counts to node-level graphlet-degree vectors. Graphlets can contain different node positions, called automorphism orbits. For example, in a three-node path, the middle node and the two endpoint nodes represent different orbits. Let \(\mathcal{O}_m\) be the set of graphlet orbits for graphlets with at most \(m\) nodes. For node \(j\) and orbit \(o\in\mathcal{O}_m\), define
\[\begin{equation} M_{jo}(G) = \#\left\{ \text{induced graphlet copies in which node }j \text{ touches orbit }o \right\}. \label{eq:ch09-graphlet-degree-entry} \end{equation}\]
The matrix
\[\begin{equation} M(G) = \left( M_{jo}(G) \right)_ {\substack{j=1,\ldots,p\\o\in\mathcal{O}_m}} \in \mathbb{R}^{p\times |\mathcal{O}_m|} \label{eq:ch09-graphlet-degree-matrix} \end{equation}\]
is the graphlet-degree matrix. Each column describes how often nodes participate in one local topological role. The first orbit corresponds to ordinary degree, so graphlet degrees can be viewed as a systematic extension of the degree distribution.
The graphlet correlation matrix records correlations between graphlet-orbit counts across nodes:
\[\begin{equation} \Gamma_{oo'}(G) = \operatorname{Cor} \left( M_{\cdot o}(G), M_{\cdot o'}(G) \right), \qquad o,o'\in\mathcal{O}_m. \label{eq:ch09-graphlet-correlation-matrix} \end{equation}\]
This matrix summarizes how different local roles co-occur across nodes. A network in which hub nodes also frequently sit in triangles can have a different graphlet correlation matrix from a network in which hub nodes sit in tree-like stars, even if both networks have similar density.
The graphlet correlation distance compares these graphlet correlation matrices (Yaveroğlu et al. 2014; Hočevar and Demšar 2014). If \(\operatorname{vecl}\) extracts the lower-triangular entries of a symmetric matrix, then one common schematic form is
\[\begin{equation} d_{\mathrm{GCD}}(G^{(a)},G^{(b)}) = \left\| \operatorname{vecl} \left[ \Gamma(G^{(a)})-\Gamma(G^{(b)}) \right] \right\|_2, \label{eq:ch09-graphlet-correlation-distance} \end{equation}\]
The distance is small when two networks have similar local wiring organization and large when their graphlet-orbit correlation structures differ. In practice, graphlet correlation distance is a graph-level comparison tool: it does not say which biological interaction is true, but it can show whether networks from different habitats, treatments, or construction methods have similar local topology. For inferred microbiome networks, it should be interpreted after checking that node definitions, sparsity levels, and network-construction rules are comparable.
9.12 Robustness And Attack Analysis
Robustness analysis asks how network connectivity changes when nodes or edges are removed. This is natural in ecological and biological settings, where one might ask whether a microbial community remains connected after losing taxa, or whether a protein interaction network is vulnerable to removing central proteins (Montoya et al. 2006; Albert et al. 2000; Iyer et al. 2013).
Let \(v_1,\ldots,v_p\) be a node-removal order. The order might be random, decreasing degree, decreasing betweenness, decreasing abundance, or decreasing external biological priority. After removing the first \(t\) nodes, the remaining node set is
\[\begin{equation} V_t = V\setminus \{v_1,\ldots,v_t\}. \label{eq:ch09-remaining-node-set} \end{equation}\]
Let \(G_t\) be the induced subgraph on \(V_t\). A simple robustness curve is the relative largest connected component size after removal:
\[\begin{equation} R(t) = \frac{|C_{\max}(G_t)|}{p-t}, \qquad t=0,\ldots,p-1. \label{eq:ch09-robustness-curve} \end{equation}\]
The area under this curve gives a one-number robustness summary:
\[\begin{equation} \operatorname{AUR}(G) = \frac{1}{p} \sum_{t=0}^{p-1} R(t). \label{eq:ch09-area-under-robustness} \end{equation}\]
Random removal and targeted removal answer different questions. Random removal measures generic tolerance to unstructured loss. Targeted removal measures vulnerability to a specific attack strategy, such as removing high-degree or high-betweenness nodes. In microbiome applications, robustness summaries have been used to connect network structure to perturbation, diet, antibiotic exposure, and host phenotypes (Mahana et al. 2016; Tipton et al. 2018). The interpretation should remain conditional: a network robustness curve describes the inferred association graph, not a direct intervention experiment on the biological system.
9.13 What To Report
A network-analysis result should make the construction and analysis layers explicit. At minimum, report the node definition, the input data matrix, preprocessing and filtering, association measure, transformation from association to dissimilarity or adjacency, sparsification rule, whether the graph is signed or unsigned, whether weights are used, the number of nodes, the number of edges, density, connected-component structure, centrality measures, community method, null model, and robustness strategy.
A compact reporting object is
\[\begin{equation} \mathcal{R}_{\mathrm{net}} = \left( R, D, W, A, h(G), \mathcal{M}, \mathcal{N} \right), \label{eq:ch09-network-reporting-object} \end{equation}\]
where \(h(G)\) is the vector of graph summaries, \(\mathcal{M}\) contains modules or community assignments, and \(\mathcal{N}\) describes the null model or graph-comparison reference. This object makes clear that biological claims arise from a chain of choices. Changing the association matrix, the sign convention, the threshold, or the null model can change the final interpretation.
Summary
Network analysis characterizes a graph after nodes and edges have been defined. The bridge from Chapter 08 is the map from a learned association, partial-correlation, or precision matrix to a concrete graph object. The same matrix can produce signed, unsigned, weighted, unweighted, or dissimilarity-based networks, and each choice changes the meaning of downstream summaries.
The main graph properties are node-level summaries such as degree and strength, global summaries such as density and connected components, path-based summaries such as average shortest path and diameter, clustering coefficients, centrality measures, community structure, graph-comparison distances, and robustness curves. These quantities turn a complex graph into interpretable mathematical summaries, but their interpretation depends on the construction process. A network statistic is always a statistic of a particular graph, and in this course that graph is usually the result of a high-dimensional statistical workflow.