Foundations of Network Science: Graph Theory, Metrics, and Data

The mathematical formalism of graph theory serves as the cornerstone of network science, providing a precise language to describe systems of interconnected entities. A graph $G$ is defined as an ordered pair $G = (V, E)$, where $V$ is a finite set of nodes (or vertices) and $E \subseteq V \times V$ is a set of edges (or links) that encode relationships between pairs of nodes. This abstraction, though deceptively simple, captures the essence of diverse phenomena: social ties among individuals, hyperlinks between web pages, neuronal connections in the brain, or protein interactions in a cell. The power of network science lies in its ability to reveal universal patterns across these seemingly disparate domains through a shared mathematical lens. Without this rigorous foundation, subsequent analyses of connectivity, cascades, and collective behavior would lack the necessary precision and generalizability. Thus, this chapter formalizes the bedrock concepts, metrics, and data practices that underpin all advanced explorations in the field.

Graph Theoretical Foundations

Basic Definitions and Representations

At its core, a graph $G = (V, E)$ consists of a set of $n = |V|$ nodes and a set of $m = |E|$ edges. Nodes represent discrete entities, while edges represent symmetric (undirected) or asymmetric (directed) relationships. The simplest case is the undirected, unweighted graph, where an edge $\{i, j\} \in E$ implies a mutual relationship between nodes $i$ and $j$, and the absence of an edge implies no direct connection. Formally, the adjacency matrix $A \in \{0,1\}^{n \times n}$ encodes this structure: $A_{ij} = 1$ if $\{i, j\} \in E$, and $0$ otherwise. For undirected graphs, $A$ is symmetric ($A_{ij} = A_{ji}$) and has zeros on the diagonal ($A_{ii} = 0$) under the standard assumption of no self-loops. The adjacency matrix provides a convenient algebraic representation; for instance, the number of paths of length $\ell$ from node $i$ to node $j$ is given by the $(i,j)$-th entry of $A^\ell$. However, for sparse graphs—where $m \ll n^2$, as is typical in real-world networks—adjacency lists are often more memory-efficient: each node stores a list of its neighbors, requiring $O(m)$ space versus $O(n^2)$ for the matrix.

Directed, Weighted, and Multigraphs

Real-world interactions often demand richer representations. In a directed graph (digraph), edges are ordered pairs $(i, j) \in E$, indicating a direction from source $i$ to target $j$. The adjacency matrix of a digraph is generally asymmetric, allowing $A_{ij} \neq A_{ji}$. This captures asymmetry in relationships: in a social network, following someone on Twitter does not imply reciprocity; in a citation network, a paper cites another without being cited back. For directed graphs, degree splits into out-degree $k_i^{\text{out}} = \sum_j A_{ij}$ (number of edges emanating from $i$) and in-degree $k_i^{\text{in}} = \sum_j A_{ji}$ (number of edges arriving at $i$).

Weighted graphs assign a scalar $w_{ij} > 0$ to each edge, representing strength, capacity, frequency, or intensity. The weighted adjacency matrix $W$ has entries $W_{ij} = w_{ij}$ if $(i,j) \in E$, and $0$ otherwise. Weights enable nuanced modeling: in a communication network, $w_{ij}$ could be the number of emails exchanged; in a transportation network, it could be travel time or bandwidth. Note that weights can be normalized or thresholded during preprocessing.

Multigraphs allow multiple edges between the same pair of nodes, which is useful for modeling repeated interactions or different modes of connection. However, they are less common in standard network analysis because they can often be reduced to weighted graphs by summing multiplicities. Formally, a multigraph $G = (V, E)$ has $E$ as a multiset of edges, so $|\{(i,j)\}|$ may exceed one. The adjacency matrix then stores integer counts rather than binary values.

Finally, graphs may include self-loops ($A_{ii} = 1$) or be bipartite, with nodes partitioned into two disjoint sets $U$ and $W$ such that all edges go between the sets. Bipartite structures arise naturally in affiliation networks (e.g., users–groups, movies–actors) and require special projection techniques to obtain unimodal networks for standard metrics.

Core Topological Metrics

The global structure of a network is quantified through a handful of fundamental metrics that characterize its connectivity, clustering, and efficiency. These metrics form the baseline for detecting anomalies, comparing networks, and modeling processes.

Degree and Degree Distribution

The degree $k_i$ of node $i$ is the number of edges incident to it. In directed graphs, we distinguish in-degree $k_i^{\text{in}}$ and out-degree $k_i^{\text{out}}$. The degree distribution $P(k)$ is the probability that a randomly selected node has degree $k$, or equivalently, the fraction of nodes with degree $k$: $P(k) = \frac{1}{n} \sum_{i=1}^n \delta(k_i - k)$, where $\delta$ is the Kronecker delta. For continuous approximation, $P(k)$ is treated as a probability density function.

Empirically, many real-world networks exhibit heavy-tailed degree distributions, often approximated by a power law: $P(k) \sim k^{-\gamma}$ with exponent $\gamma \in [2, 3]$. Such networks are termed scale-free or "no-scale-free" (as the term is debated) and are characterized by the presence of hubs—nodes with exceptionally high degree. The power law implies that extreme events (very high-degree nodes) are vastly more probable than in distributions with thin tails like the Poisson or Gaussian. Figure 1 (conceptual) illustrates a typical power-law degree distribution on a log-log scale, showing linearity over several decades. This property has profound implications for robustness and vulnerability: targeted attacks on hubs can fragment the network, while random failures have little effect due to the preponderance of low-degree nodes.

```mermaid graph TD A[Raw Data] --> B[Adjacency Matrix] B --> C[Degree Calculation] C --> D[Histogram] D --> E[Log-Log Plot] E --> F{Power Law?} F -->|Yes| G[Estimate γ via MLE] F -->|No| H[Fit Alternative Distribution] ```

Maximum likelihood estimation (MLE) for the power-law exponent $\gamma$ is standard: given $n$ observed degrees $\{k_i\}$ above a minimum $k_{\min}$, $\hat{\gamma} = 1 + n \left[ \sum_{i=1}^n \ln \frac{k_i}{k_{\min}} \right]^{-1}$. The choice of $k_{\min}$ is critical; Clauset et al. (2009) propose a method to select $k_{\min}$ that minimizes the Kolmogorov-Smirnov distance between the empirical data and the fitted power law. Significance is assessed via a goodness-of-fit test comparing the empirical distribution to the fitted one and to alternative heavy-tailed distributions (e.g., lognormal). It is crucial to note that not all networks are scale-free; many exhibit truncated power laws, exponential cutoffs, or Poisson-like degree distributions (e.g., in physical infrastructure networks).

Clustering Coefficient

The clustering coefficient measures the extent to which a node's neighbors are connected to each other, capturing the notion of "triadic closure." For node $i$ with degree $k_i \geq 2$, the local clustering coefficient is defined as: $$C_i = \frac{2T_i}{k_i(k_i - 1)}$$ where $T_i$ is the number of edges among the neighbors of $i$ (i.e., the number of triangles that include $i$). The denominator $k_i(k_i - 1)/2$ is the maximum possible number of edges among $k_i$ neighbors, so $C_i \in [0,1]$. A value $C_i = 1$ means the neighbors form a complete subgraph (clique), while $C_i = 0$ means no connections among them.

The global clustering coefficient $C$ aggregates local values. Two common definitions exist: 1. Average of local coefficients: $C = \frac{1}{n} \sum_{i=1}^n C_i$. This is intuitive but can be biased toward low-degree nodes, which inherently have fewer potential triangles. 2. Transitivity: $C = \frac{3 \times \text{number of triangles}}{\text{number of co