1 Introduction

Relations are the fundamental fabric of reality.

Michele Coscia

1.1Motivation¶

Alongside the exponential growth of computer networks over the last few decades, we have witnessed concurrent and equally rapid growth in a field called network science. Once computer networks brought network structure into clearer focus, scientists began to recognize networks almost everywhere, even in phenomena that had already received centuries of attention using other methods, and to apply network theory to organize and expand knowledge right throughout the sciences, in every field and discipline.

The set of possible examples is vast, and sources mentioning or treating hundreds of different applications of network methods and graph theory are listed in the reading notes at the end of the chapter. In computer science and machine learning alone, we see computational graphs, graphical networks, neural networks and deep learning. In operations research, network analysis focuses on minimum cost flow, traveling salesman, shortest path, and assignment problems. In biology, networks are a standard way to represent interactions between bioentities.

In this book, our interest lies in economic and social phenomena. Here, too, networks are pervasive. Important examples include financial networks, production networks, trade networks, transport networks and social networks. For example, social and information networks affect trends in sentiments and opinions, consumer decisions, and a range of peer effects. The topology of financial networks helps to determine relative fragility of the financial system, while the structure of production networks affects trade, innovation and the propagation of local shocks.

Figure 1.1–Figure 1.2 show two examples of trade networks. Figure 1.1 is called a Sankey diagram, which is a kind of figure used to represent flows. Oil flows from left to right. The countries on the left and below are the top 10 exporters of crude oil, while the countries on the right are the top 20 consumers. The figure relates to one of our core topics: optimal (and equilibrium) flows across networks. We treat optimal flows at length in Chapter 3.^[1]

Figure 1.2 shows international trade in large commercial aircraft in 2019.^[2] Node size is proportional to total exports and link width is proportional to exports to the target country. The US, France and Germany are revealed as major export hubs.

While some readers viewing Figure 1.1–Figure 1.2 might at first suspect that the network perspective adds little more than an attractive technique for visualizing data, it actually adds much more. For example, in Figure 1.2, node colors are based on a ranking of “importance” in the network called eigenvector centrality, which we introduce in Section 1.4.3.4. Such rankings and centrality measures are an active area of research among network scientists. Eigenvector and other forms of centrality feature throughout the text. For example, we will see that these concepts are closely connected to—and shed new light on—fundamental ideas first developed many years ago by researchers in the field of input-output economics.

In addition, in production networks, it turns out that the nature of shock propagation is heavily dependent on the underlying structure of the network. For example, for a few highly connected nodes, shocks occurring within one firm or sector can have an outsized influence on aggregate-level fluctuations. Economists are currently racing to understand these relationships, their interactions with various centrality measures, and other closely related phenomena.

To understand this line of work, as well as other applications of network methods to economics and finance, some technical foundations are required. For example, to define eigenvector centrality, we need to be familiar with eigenvectors, spectral decompositions and the Perron–Frobenius theorem. To work with Katz centrality, which also features regularly in network science and economics, we require a sound understanding of the Neumann series lemma. The Perron–Frobenius theorem and the Neumann series lemma form much of the technical foundation of this textbook. We review them in detail in Section 1.2 and develop extensions throughout remaining chapters.

One reason that analysis of networks is challenging is high-dimensionality. To see why, consider implementing a model with $n$ economic agents. This requires $n$ times more data than one representative agent in a setting where agents are atomistic or coordinated by a fixed number of prices. For example, Carvalho & Grassi (2019) model the dynamics of $n = 6 \times 10^6$ firms, all of which need to be tracked when running a simulation. However, if we wish to model interactions between each pair $i, j$ (supply linkages, liabilities, etc.), then, absent sparsity conditions, the data processing requirement grows like $O(n^2)$.^[3] In the Carvalho & Grassi (2019) example, $n^2$ is $3.6 \times 10^{13}$, which is very large even for modern computers. One lesson is that network models can be hard to solve, even with powerful computers, unless we think carefully about algorithms.

In general, to obtain a good grasp on the workings of economic networks, we will need computational skills plus a firm understanding of linear algebra, probability and a field of discrete mathematics called graph theory. The rest of this chapter provides relevant background in these topics. Before tackling this background, we recommend that readers skim the list of common symbols, as well the mathematical topics in the appendix, which start. (The appendix is not intended for sequential reading, but rather as a source of definitions and fundamental results to be drawn on in what follows.)

1.2Spectral Theory¶

In this section we review some linear algebra needed for the study of graphs and networks. Highlights include the spectral decomposition of diagonalizable matrices, the Neumann series lemma, and the theorem of Perron and Frobenius.

1.2.1Eigendecompositions¶

Our first task is to cover spectral decompositions and the spectral theorem. We begin with a brief review of eigenvalues and their properties. (If you are not familiar with eigenvalues and eigenvectors, please consult an elementary treatment first. See, for example, Cohen (2021).)

1.2.1.1Eigenvalues¶

Fix $A$ in $\matset{n}{n}$. A scalar $\lambda \in \CC$ is called an eigenvalue of $A$ if there exists a nonzero complex vector $e \in \CC^n$ such that $Ae = \lambda e$. A vector $e$ satisfying this equality is called an eigenvector corresponding to the eigenvalue $\lambda$. (Notice that eigenvalues and eigenvectors are allowed to be complex, even though we restrict elements of $A$ to be real.) The set of all eigenvalues of $A$ is called the spectrum of $A$ and written as $\sigma(A)$. As we show below, $A$ has at most $n$ distinct eigenvalues.

In Julia, we can check for the eigenvalues of a given square matrix $A$ via eigvals(A). Here is one example

using LinearAlgebra
A = [0 -1;
     1  0]
eigenvals = eigvals(A) 

Running this code in a Jupyter cell (with Julia kernel) or Julia REPL produces

2-element Vector{ComplexF64}:
 0.0 - 1.0im
 0.0 + 1.0im

Here im stands for $i$, the imaginary unit (i.e., $i^2=-1$).

If $\lambda \in \sigma(A)$ and $e$ is an eigenvector for $\lambda$, then $(\lambda, e)$ is called an eigenpair.

It can be shown that $p(\lambda) := \det(A -\lambda I)$ is a polynomial of degree $n$.^[4] This polynomial is called the characteristic polynomial of $A$. By the Fundamental Theorem of Algebra, there are $n$ roots (i.e., solutions in $\CC$ to the equation $p(\lambda)=0$), although some may be repeated as in the complete factorization of $p(\lambda)$. By Lemma 1.2.1,

If $\lambda \in \sigma(A)$ appears $k$ times in the factorization of the polynomial $p(\lambda)$, then $\lambda$ is said to have algebraic multiplicity $k$. An eigenvalue with algebraic multiplicity one is called simple. A simple eigenvalue $\lambda$ has the property that its eigenvector is unique up to a scalar multiple, in the sense of Exercise 1.2.2. In other words, the linear span of $\setntn{e \in \CC^n}{(\lambda, e) \text{ is an eigenpair}}$ (called the eigenspace of $\lambda$) is one-dimensional.

1.2.1.2The Eigendecomposition¶

What are the easiest matrices to work with? An obvious answer to this question is: the diagonal matrices. For example, when $D = \diag(\lambda_i)$ with $i \in \natset{n}$,

• the linear system $Dx = b$ reduces to $n$ completely independent scalar equations,

• the $t$-th power $D^t$ is just $\diag(\lambda_i^t)$, and

• the inverse $D^{-1}$ is just $\diag(\lambda_i^{-1})$, assuming all $\lambda_i$’s are nonzero.

While most matrices are not diagonal, there is a way that “almost any” matrix can be viewed as a diagonal matrix, after translation of the usual coordinates in $\RR^n$ via an alternative basis. This can be extremely useful. The key ideas are described below.

$A \in \matset{n}{n}$ is called diagonalizable if

We allow both $D$ and $P$ to contain complex values. The representation $P D P^{-1}$ is called the eigendecomposition or the spectral decomposition of $A$.

One way to think about diagonalization is in terms of maps, as in

Either we can map directly with $A$ or, alternatively, we can shift to $\CC^n$ via $P^{-1}$, apply the diagonal matrix $D$, and then shift back to $\RR^n$ via $P$.

The equality $A = P D P^{-1}$ can also be written as $A P = P D$. Decomposed across column vectors, this equation says that each column of $P$ is an eigenvector of $A$ and each element along the principal diagonal of $D$ is an eigenvalue.

When does diagonalizability hold?

While diagonalizability is not universal, the set of matrices in $\matset{n}{n}$ that fail to be diagonalizable has “Lebesgue measure zero” in $\matset{n}{n}$. (Loosely speaking, only special or carefully constructed examples will fail to be diagonalizable.) The next results provide conditions for the property.

This result is intuitive: for $A = P D P^{-1}$ to hold we need $P$ to be invertible, which requires that its $n$ columns are linearly independent. Since $\CC^n$ is $n$-dimensional, this means that the columns form a basis of $\CC^n$.

There is another way that we can establish diagonalizability, based on symmetry. Symmetry also lends the diagonalization certain properties that turn out to be very useful in applications. We are referring to the following celebrated theorem.

Since, for the orthonormal matrix $U$, we have $U^\top = U^{-1}$ (see Lemma 6.1.15), one consequence of the spectral theorem is that $A$ is diagonalizable. For obvious reasons, we often say that $A$ is orthogonally diagonalizable.

1.2.1.3Worker Dynamics¶

Let’s study a small application of the eigendecomposition. Suppose that, each month, workers are hired at rate $\alpha$ and fired at rate $\beta$. Their two states are unemployment (state 1) and employment (state 2). Figure 1.3 shows the transition probabilities for a given worker in each of these two states.

We translate these dynamics into the matrix

• Row 1 of $P_w$ gives probabilities for unemployment and employment respectively when currently unemployed.

• Row 2 of $P_w$ gives probabilities for unemployment and employment respectively when currently employed.

Below we demonstrate that the $m$-th power of $P_w$ provides $m$-step transition probabilities for workers. Anticipating this discussion, we now seek an expression for $P^m_w$ at arbitrary $m \in \NN$. This problem is simplified if we use diagonalization.

1.2.1.4Left Eigenvectors¶

A vector $\epsilon \in \CC^n$ is called a left eigenvector of $A \in \matset{n}{n}$ if $\epsilon$ is an eigenvector of $A^\top$. In other words, $\epsilon$ is nonzero and there exists a $\lambda \in \CC$ such that $A^\top \epsilon = \lambda \epsilon$. We can alternatively write the expression as $\epsilon^\top A = \lambda \epsilon^\top$, which is where the name “left” eigenvector originates.

Left eigenvectors will play important roles in what follows, including that of stochastic steady states for dynamic models under a Markov assumption. To help distinguish between ordinary and left eigenvectors, we will at times call (ordinary) eigenvectors of $A$ right eigenvectors of $A$.

If $A$ is diagonalizable, then so is $A^\top$. To show this, let $A = P D P^{-1}$ with $D = \diag(\lambda_i)$. We know from earlier discussion that the columns of $P$ are the (right) eigenvectors of $A$.

The results of the last exercise show that, when $A = P D P^{-1}$, the columns of $(P^\top)^{-1}$ coincide with the left eigenvectors of $A$. (Why?) Equivalently, $A = P D Q^\top$ where $Q = (\epsilon_1, \ldots, \epsilon_n)$ is the $n\times n$ matrix with $i$-th column equal to the $i$-th left eigenvector of $A$.

1.2.1.5Similar Matrices¶

Diagonalizability is a special case of a more general concept: $A \in \matset{n}{n}$ is called similar to $B \in \matset{n}{n}$ if there exists an invertible matrix $P$ such that $A = P B P^{-1}$. In this terminology, $A$ is diagonalizable if and only if it is similar to a diagonal matrix.

The last result is a generalization of (1.1). When $A$ is large, calculating the powers $A^k$ can be computationally expensive or infeasible. If, however, $A$ is similar to some simpler matrix $B$, then we can take powers of $B$ instead, and then transition back to $A$ using the similarity relation.^[5]

1.2.2The Neumann Series Lemma¶

Most high school students learn that, if $a$ is a number with $|a| < 1$, then

This geometric series representation extends to matrices: If $A$ is a matrix satisfying a certain condition, then (1.6) holds, in the sense that $\sum_{i \geq 0} A^i = (I-A)^{-1}$. (Here $I$ is the identity matrix.) But what is the “certain condition” that we need to place on $A$, which generalizes the concept $|a|<1$ to matrices? The answer to this question involves the “spectral radius” of a matrix, which we now describe.

1.2.2.1Spectral Radius¶

Fix $A \in \matset{n}{n}$. With $|z|$ indicating the modulus of a complex number $z$, the spectral radius of $A$ is defined as

Within economics, the spectral radius has important applications in dynamics, asset pricing, and numerous other fields. As we will see, the same concept also plays a key role in network analysis.

After executing

import numpy as np

The following Python code computes the spectral radius of a square matrix $M$:

def spec_rad(M):
    return np.max(np.abs(np.linalg.eigvals(M)))    

1.2.2.2Geometric Series¶

We can now return to the matrix extension of (1.6) and state a formal result.

The sum $\sum_{m=0}^{\infty} A^m$ is called the power series representation of $(I - A)^{-1}$. Convergence of the matrix series is understood as element-by-element convergence.

A full proof of Theorem 1.2.5 can be found in Cheney (2013) and many other sources. The core idea is simple: if $S = I + A + A^2 + \cdots$ then $I + A S = S$. Reorganizing gives $(I - A)S = I$, which is equivalent to (1.8). The main technical issue is showing that the power series converges. The full proof shows that this always holds when $r(A)<1$.

1.2.3The Perron–Frobenius Theorem¶

In this section we state and discuss a suprisingly far reaching theorem due to Oskar Perron and Ferdinand Frobenius, which has applications in network theory, machine learning, asset pricing, Markov dynamics, nonlinear dynamics, input-output analysis and many other fields. In essence, the theorem provides additional information about eigenvalues and eigenvectors when the matrix in question is positive in some sense.

1.2.3.1Order in Matrix Space¶

We require some definitions. In what follows, for $A \in \matset{n}{k}$, we write

• $A \geq 0$ if all elements of $A$ are nonnegative and

• $A \gg 0$ if all elements of $A$ are strictly positive.

It’s easy to imagine how nonnegativity and positivity are important notions for matrices, just as they are for numbers. However, strict positivity of every element of a matrix is hard to satisfy, especially for a large matrix. As a result, mathematicians routinely use two notions of “predominantly strictly positive,” which sometimes provide sufficient positivity for the theorems that we need.

Regarding these two notions, for $A \in \matset{n}{n}$, we say that $A \geq 0$ is

• irreducible if $\sum_{m=0}^\infty A^m \gg 0$ and

• primitive if there exists an $m \in \NN$ such that $A^m \gg 0$.

Evidently, for $A \in \matset{n}{n}$ we have

A nonnegative matrix is called reducible if it fails to be irreducible.

In addition to the above notation, for $A, B \in \matset{n}{k}$, we also write

• $A \geq B$ if $A - B \geq 0$ and $A \gg B$ if $A - B \gg 0$,

• $A \leq 0$ if $-A \geq 0$, etc.

The partial order $\leq$ discussed in Exercise 1.2.21 is usually called the pointwise partial order on $\matset{n}{k}$. Analogous notation and terminology are used for vectors.

The following exercise shows that nonnegative matrices are order-preserving maps (see Section 6.1.2.3) on vector space under the pointwise partial order—a fact we shall exploit many times.

1.2.3.2Statement of the Theorem¶

Let $A$ be in $\matset{n}{n}$. In general, $r(A)$ is not an eigenvalue of $A$. For example,

But $r(A)$ is always an eigenvalue when $A \geq 0$. This is just one implication of the following famous theorem.

The fact that $r(A)$ is simple under irreducibility means that its eigenvectors are unique up to scalar multiples. We will exploit this property in several important uniqueness proofs.

In the present context, $r(A)$ is called the dominant eigenvalue or Perron root of $A$, while $\epsilon$ and $e$ are called the dominant left and right eigenvectors of $A$, respectively.

Why do we use the word “dominant” here? To help illustrate, let us suppose that $A \in \matset{n}{n}$ is primitive and fix any $x \in \RR^n$. Consider what happens to the point $x_m := A^m x$ as $m$ grows. By (1.11) we have $A^m x \approx r(A)^m c e$ for large $m$, where $c = \epsilon^\top x$. In other words, asymptotically, the sequence $(A^m x)_{m \in \NN}$ is just scalar multiples of $e$, growing at rate $\ln r(A)$. Thus, $r(A)$ dominates other eigenvalues in controlling the growth rate of $A^m x$, while $e$ dominates other eigenvectors in controlling the direction of growth.

1.2.3.3Worker Dynamics II¶

We omit the full proof of Theorem 1.2.6, which is quite long and can be found in Meyer (2000), Seneta (2006) or Meyer-Nieberg (2012).^[6] Instead, to build intuition, let us prove the theorem in a rather simple special case.

The special case we will consider is the class of matrices

This example is drawn from the study of worker dynamics in Section 1.2.1.3.

You might recall from Section 1.2.1.3 that $\lambda_1 = 1$ and $\lambda_2 = 1-\alpha-\beta$. Clearly $r(A)=1$, so $r(A)$ is an eigenvalue, as claimed by the first part of the Perron–Frobenius theorem.

From now on we assume that $\min\{\alpha, \beta\} > 0$, which just means that we are excluding the identity matrix in order to avoid some tedious qualifying remarks.

The two right eigenvectors ($e_1, e_2$) and two left eigenvectors ($\epsilon_1, \epsilon_2$) are, respectively,

1.2.3.4Bounding the Spectral Radius¶

Using the Perron–Frobenius theorem, we can provide useful bounds on the spectral radius of a nonnegative matrix. In what follows, fix $A = (a_{ij}) \in \matset{n}{n}$ and set

• $\rsum_i(A) := \sum_j a_{ij} =$ the $i$-th row sum of $A$ and

• $\csum_j(A) := \sum_i a_{ij} =$ the $j$-th column sum of $A$.

1.3Probability¶

Next we review some elements of probability that will be required for analysis of networks.

1.3.1Discrete Probability¶

We first introduce probability models on finite sets and then consider sampling methods and stochastic matrices.

1.3.1.1Probability on Finite Sets¶

Throughout this text, if $S$ is a finite set, then we set

and call $\dD(S)$ the set of distributions on $S$. We say that a random variable $X$ taking values in $S$ has distribution $\phi \in \dD(S)$ and write $X \eqdist \phi$ if

A distribution $\phi$ can also be understood as a vector $(\phi(x_i))_{i =1}^n \in \RR^n$ (see Lemma 6.1.2 in Section 6.1.1.3). As a result, $\dD(S)$ can be viewed as a subset of $\RR^n$. Figure 1.4 provides a visualization when $S = \{1, 2, 3\}$. Each $\phi \in \dD(S)$ is identified by the point $(\phi(1), \phi(2), \phi(3))$ in $\RR^3$.

More generally, if $|S|=n$, then $\dD(S)$ can be identified with the unit simplex in $\RR^n$, which is the set of all $n$-vectors that are nonnegative and sum to one.

Throughout, given $x \in S$, we use the symbol $\delta_x$ to represent the element of $\dD(S)$ that puts all mass on $x$. In other words, $\delta_x(y) = \1\{y = x\}$ for all $y \in S$. In Figure 1.4, each $\delta_x$ is a vertex of the unit simplex.

We frequently make use of the law of total probability, which states that, for a random variable $X$ on $S$ and arbitrary $A \subset S$,

where $\{B_i\}$ is a partition of $S$ (i.e., finite collection of disjoint subsets of $S$ such that their union equals $S$).

1.3.1.2Inverse Transform Sampling¶

Let $S$ be a finite set. Suppose we have the ability to generate random variables that are uniformly distributed on $(0, 1]$. We now want to generate random draws from $S$ that are distributed according to arbitrary $\phi \in \dD(S)$.

Let $W$ be uniformly distributed on $(0,1]$, so that, for any $a \leq b \in (0,1]$, we have $\PP\{a < W \leq b\} = b - a$, which is the length of the interval $(a, b]$.^[7] Our problem will be solved if we can create a function $z \mapsto \kappa(z )$ from $(0,1]$ to $S$ such that $\kappa(W)$ has distribution $\phi$. One technique is as follows. First we divide the unit interval $(0,1]$ into disjoint subintervals, one for each $x \in S$. The interval corresponding to $x$ is denoted $I(x)$ and is chosen to have length $\phi(x)$. More specifically, when $S = \{x_1, \ldots, x_N\}$, we take

You can easily confirm that the length of $I(x_i )$ is $\phi(x_i)$ for all $i$.

Now consider the function $z \mapsto \kappa(z)$ defined by

where $\1\{z \in I(x )\}$ is one when $z \in I(x )$ and zero otherwise. It turns out that $\kappa(W)$ has the distribution we desire.

The last exercise tells us that that the law of large numbers holds in this setting, since, under this law, we expect that

with probability one as $n \to \infty$. In view of Exercise 1.3.3, the right hand side equals $\phi(j)$.

1.3.1.3Stochastic Matrices¶

A matrix $P = (p_{ij}) \in \matset{n}{n}$ is called a stochastic matrix if

In other words, $P$ is nonnegative and has unit row sums.

We will see many applications of stochastic matrices in this text. Often the applications are probabilistic, where each row of $P$ is interpreted as a distribution over a finite set.

The vector $\psi$ in part (iii) of Exercise 1.3.7 is called the PageRank vector by some authors, due to its prominence in Google’s PageRank algorithm. We will call it a stationary distribution instead.^[8] Stationary distributions play a key role in the theory of Markov chains, to be treated in Section 4.1. Ranking methods are discussed again in Section 1.4.3. PageRank is treated in more detail in Section 4.2.3.3.

1.3.2Power Laws¶

Next we discuss distributions on the (non-discrete) sets $\RR$ and $\RR_+$. We are particularly interested in a certain class of distributions that are apparently non-standard and yet appear with surprising regularity in economics, social science, and the study of networks. We refer to the distributions that are said to obey a “power law.”

In what follows, given a real-valued random variable $X$, the function

is called the cumulative distribution function (CDF) of $X$. The counter CDF (CCDF) of $X$ is the function $G(t) := \PP\{X > t\} = 1 - F(t)$.

A useful property that holds for any nonnegative random variable $X$ and $p \in \RR_+$ is the identity

See, for example, Çınlar (2011), p. 63.

1.3.2.1Heavy Tails¶

Recall that a random variable $X$ on $\RR$ is said to be normally distributed with mean $\mu$ and variance $\sigma^2$, and we write $X \eqdist N(\mu, \sigma^2)$, if $X$ has density

One notable feature of the normal density is that the tails of the density approach zero quickly. For example, $\phi(t)$ goes to zero like $\exp(-t^2)$ as $t \to \infty$, which is extremely fast.

A random variable $X$ on $\RR_+$ is called exponentially distributed and we write $X \eqdist \Exp(\lambda)$ if, for some $\lambda > 0$, $X$ has density

The tails of the exponential density go to zero like $\exp(-t)$ as $t \to \infty$, which is also relatively fast.

When a distribution is relatively light-tailed, in the sense that its tails go to zero quickly, draws rarely deviate more than a few standard deviations from the mean. In the case of a normal random variable, the probability of observing a draw more than 3 standard deviations above the mean is around 0.0014. For 6 standard deviations, the probability falls to $10^{-11}$.

In contrast, for some distributions, “extreme” outcomes occur relatively frequently. The left panel of Figure 1.5 helps to illustrate by simulating 1,000 independent draws from Student’s t-distribution, with $1.5$ degrees of freedom. For comparison, the right subfigure shows an equal number of independent draws from the $N(0, 4)$ distribution. The Student’s t draws reveal tight clustering around zero combined with a few large deviations.

Formally, a random variable $X$ on $\RR$ is called light-tailed if its moment generating function

is finite for at least one $t > 0$. Otherwise $X$ is called heavy-tailed.^[9]

For any random variable $X$ and any $r \geq 0$, the (possibly infinite) expectation $\EE |X|^r$ called the $r$-th moment of $X$.

Together with Lemma 1.3.1, Exercise 1.3.8 shows that existence of an infinite moment is a sufficient but not necessary condition for heavy tails.

1.3.2.2Pareto Tails¶

Given $\alpha > 0$, a nonnegative random variable $X$ is said to have a Pareto tail with tail index $\alpha$ if there exists a $c > 0$ such that

In other words, the CCDF $G$ of $X$ satisfies

If $X$ has a Pareto tail for some $\alpha > 0$, then $X$ is also said to obey a power law.

Regarding Example 1.3.3, note that the converse is not true: Pareto-tailed random variables are not necessarily Pareto distributed, since the Pareto tail property only restricts the far right hand tail.

From Exercise 1.3.9 and Lemma 1.3.1, we see that every Pareto-tailed random variable is heavy-tailed. The converse is not true, since the Pareto tail property (1.16) is very specific. Despite this, it turns out that many heavy-tailed distributions encountered in the study of networks are, in fact, Pareto-tailed.

1.3.2.3Empirical Power Law Plots¶

When the Pareto tail property holds, the CCDF satisfies $\ln G(t) \approx \ln c - \alpha \ln t$ for large $t$. In other words, $G$ is eventually log linear. Figure 1.6 illustrates this using a Pareto distribution. For comparison, the CCDF of an exponential distribution is also shown.

If we replace the CCDF $G$ with its empirical counterpart—which returns, for each $x$, the fraction of the sample with values greater than $x$—we should also obtain an approximation to a straight line under the Pareto tail assumption.

For example, consider the cross-sectional distribution of firm sizes. While the precise nature of this distribution depends on the measure of firm size, the sample of firms and other factors, the typical picture is one of extreme heavy tails. As an illustration, Figure 1.7 shows an empirical CCDF log-log plot for market values of the largest 500 firms in the Forbes Global 2000 list, as of March 2021. The slope estimate and data distribution are consistent with a Pareto tail and infinite population variance.

1.3.2.4Discrete Power Laws¶

Let $X$ be a random variable with the Pareto distribution, as described in Example 1.3.3. The density of this random variable on the set $[\bar x, \infty)$ is $p(t) = c t^{-\gamma}$ with $c := \alpha \bar x^\alpha$ and $\gamma := \alpha + 1$. The next exercise extends this idea.

The discrete analog of (1.19) is a distribution on the positive integers with

for large $k$. In the special case where this equality holds for all $k \in \NN$, and $c$ is chosen so that $\sum_{k \in \NN} f(k) = 1$, we obtain the zeta distribution.^[10]

In general, when we see a probability mass function with the specification (1.20) for large $k$, we can identify this with a Pareto tail, with tail index $\alpha = \gamma - 1$. Figure 1.8 illustrates with $\gamma=2$.

1.4Graph Theory¶

Graph theory is a major branch of discrete mathematics. It plays an essential role in this text because it forms the foundations of network analysis. This section provides a concise introduction to graph theory suitable for our purposes.^[11]

Graph theory has another closely related use: many economic models are stochastic and dynamic, which means that they specify states of the world and rates of transition between them. One of the most natural ways to conceptualize these notions is to view states as vertices in a graph and transition rates as relationships between them.

We begin with definitions and fundamental concepts. We focus on directed graphs, where there is a natural asymmetry in relationships (bank $A$ lends money to bank $B$, firm $A$ supplies goods to firm $B$, etc.). This costs no generality, since undirected graphs (where relationships are symmetric two-way connections) can be recovered by insisting on symmetry (i.e., existence of a connection from $A$ to $B$ implies existence of a connection from $B$ to $A$).

1.4.1Unweighted Directed Graphs¶

We begin with unweighted directed graphs and examine standard properties, such as connectedness and aperiodicity.

1.4.1.1Definition and Examples¶

A directed graph or digraph is a pair $\gG = (V, E)$, where

• $V$ is a finite nonempty set and

• $E$ is a collection of ordered pairs $(u, v) \in V \times V$ called edges.

Elements of $V$ are called the vertices or nodes of $\gG$. Intuitively and visually, an edge $(u,v)$ is understood as an arrow from vertex $u$ to vertex $v$.

Two graphs are given in Figure 1.9–Figure 1.10. Each graph has three vertices. In these cases, the arrows (edges) could be thought of as representing positive possibility of transition over a given unit of time.

For a given edge $(u, v)$, the vertex $u$ is called the tail of the edge, while $v$ is called the head. Also, $u$ is called a direct predecessor of $v$ and $v$ is called a direct successor of $u$. For $v \in V$, we use the following notation:

• $\iI(v) :=$ the set of all direct predecessors of $v$

• $\oO(v) :=$ the set of all direct successors of $v$

Also, the in-degree and out-degree of $v \in V$ are defined by

• the $i_d(v) := |\iI(v)|$ and

• the $o_d(v) := |\oO(v)|$ respectively.

If $i_d(v)=0$ and $o_d(v) > 0$, then $v$ is called a source. If either $\oO(v)=\emptyset$ or $\oO(v)=\{v\}$, then $v$ is called a sink. For example, in Figure 1.10, “poor” is a sink with an in-degree of 3.

1.4.1.2Digraphs in Networkx¶

Both Python and Julia provide valuable interfaces to numerical computing with graphs. Of these libraries, the Python package Networkx is probably the most mature and fully developed. It provides a convenient data structure for representing digraphs and implements many common routines for analyzing them. To import it into Python we run

import networkx as nx

In all of the code snippets shown below, we assume readers have executed this import statement, as well as

import numpy as np
import matplotlib.pyplot as plt

As an example, let us create the digraph in Figure 1.10, which we denote henceforth by $\gG_p$. To do so, we first create an empty DiGraph object:

G_p = nx.DiGraph()    

Next we populate it with nodes and edges. To do this we write down a list of all edges, with poor represented by p and so on:

edge_list = [
    ('p', 'p'),
    ('m', 'p'), ('m', 'm'), ('m', 'r'),
    ('r', 'p'), ('r', 'm'), ('r', 'r')
]

Finally, we add the edges to our DiGraph object:

for e in edge_list:
    u, v = e
    G_p.add_edge(u, v)

Adding the edges automatically adds the nodes, so G_p is now a correct representation of $\gG_p$. For our small digraph we can verify this by plotting the graph via Networkx with the following code:

fig, ax = plt.subplots()
nx.draw_spring(G_p, ax=ax, node_size=500, with_labels=True, 
                 font_weight='bold', arrows=True, alpha=0.8,
                 connectionstyle='arc3,rad=0.25', arrowsize=20)
plt.show()

This code produces Figure 1.11, which matches the original digraph in Figure 1.10.

DiGraph objects have methods that calculate in-degree and out-degree of vertices. For example,

G_p.in_degree('p')

prints 3.

1.4.1.3Communication¶

Next we study communication and connectedness, which have important implications for production, financial, transportation and other networks, as well as for dynamic properties of Markov chains.

A directed walk from vertex $u$ to vertex $v$ of a digraph $\gG$ is a finite sequence of vertices, starting with $u$ and ending with $v$, such that any consecutive pair in the sequence is an edge of $\gG$. A directed path from $u$ to $v$ is a directed walk from $u$ to $v$ such that all vertices in the path are distinct. For example, in Figure 1.12, $(3, 2, 3, 2, 1)$ is a directed walk from $3$ to $1$ but not a directed path, while $(3, 2, 1)$ is both a directed path and a directed walk from $3$ to $1$.

As is standard, the length of a directed walk (or path) counts the number of edges rather than vertices. For example, the directed path $(3, 2, 1)$ from $3$ to $1$ in Figure 1.12 is said to have length 2.

Vertex $v$ is called accessible (or reachable) from vertex $u$, and we write $u \to v$, if either $u=v$ or there exists a directed path from $u$ to $v$. A set $U \subset V$ is called absorbing for the directed graph $(V, E)$ if no element of $V \setminus U$ is accessible from $U$.

Two vertices $u$ and $v$ are said to communicate if $u \to v$ and $v \to u$.

Since communication is an equivalence relation, it induces a partition of $V$ into a finite collection of equivalence classes. Within each of these classes, all elements communicate. These classes are called strongly connected components. The graph itself is called strongly connected if there is only one such component; that is, $v$ is accessible from $u$ for any pair $(u, v) \in V \times V$. This corresponds to the idea that any node can be reached from any other.

Networkx can be used to test for communication and strong connectedness, as well as to compute strongly connected components. For example, applied to the digraph in Figure 1.12, the code

G = nx.DiGraph()
G.add_edge(1, 1)
G.add_edge(2, 1)
G.add_edge(2, 3)
G.add_edge(3, 2)

list(nx.strongly_connected_components(G)) 

prints [{1}, {2, 3}].

1.4.1.4Aperiodicity¶

A cycle $(u, v, w, \ldots, u)$ of a directed graph $\gG = (V, E)$ is a directed walk in $\gG$ such that (i) the first and last vertices are equal and (ii) no other vertex is repeated. The graph is called a directed acyclic graph if it contains no cycles. The graph is called periodic if it contains at least one cycle and, moreover, there exists a $k > 1$ such that the length of every cycle is a multiple of $k$. The graph is called aperiodic if it is not periodic.

An obvious sufficient condition for aperiodicity is existence of even one self-loop. The digraphs in Figure 1.9–Figure 1.12 are aperiodic for this reason.

The next result provides an easy way to understand aperiodicity for connected graphs. Proofs can be found in Häggström (2002) and Norris (1998).

It is common to call a vertex $v$ satisfying the condition in Lemma 1.4.1 aperiodic. With this terminology, Lemma 1.4.1 states that a strongly connected digraph is aperiodic if and only if every vertex is aperiodic.

Networkx can be used to check for aperiodicity of vertices or graphs. For example, if G is a DiGraph object, then nx.is_aperiodic(G) returns True or False depending on aperiodicity of G.

1.4.1.5Adjacency Matrices¶

There is a simple map between edges of a graph with fixed vertices and a binary matrix called an adjacency matrix. The benefit of viewing connections through adjacency matrices is that they bring the power of linear algebra to the analysis of digraphs. We illustrate this briefly here and extensively in Section 1.4.2.

If $\gG = (V, E)$ is a digraph with $V = \{v_1, \ldots, v_n\}$, then the $n \times n$ adjacency matrix corresponding to $(V, E)$ is defined by^[12]

For example, with $\{$poor, middle, rich$\}$ mapped to $(1, 2, 3)$, the adjacency matrix corresponding to the digraph in Figure 1.10 is

An adjacency matrix provides us with enough information to recover the edges of a graph. More generally, given a set of vertices $V = \{v_1, \ldots, v_n\}$, an $n \times n$ matrix $A = (a_{ij})_{1 \leq i, j \leq n}$ with binary entries generates a digraph $\gG$ with vertices $V$ and edges

The adjacency matrix of this graph $(V, E)$ is $A$.

Like Networkx, the Python library quantecon provides a graph object that supplies certain graph-theoretic algorithms. In the case of QuantEcon’s DiGraph object, algorithms are implemented by interfacing with routines in SciPy and an instance is created by supplying an adjacency matrix. For example, to construct a digraph corresponding to Figure 1.10 we use the corresponding adjacency matrix (1.22):

import quantecon as qe
import numpy as np

A = ((1, 0, 0),
     (1, 1, 1,),
     (1, 1, 1))
A = np.array(A)       # Convert to NumPy array
G = qe.DiGraph(A)

Let’s print the set of strongly connected components, as a list of NumPy arrays:

G.strongly_connected_components 

The output is [array([0]), array([1, 2])].

1.4.2Weighted Digraphs¶

Early quantitative work on networks tended to focus on unweighted digraphs, where the existence or absence of an edge is treated as sufficient information (e.g., following or not following on social media, existence or absence of a road connecting two towns). However, for some networks, this binary measure is less significant than the size or strength of the connection.

As one illustration, consider Figure 1.14, which shows flows of funds (i.e., loans) between private banks, grouped by country of origin. An arrow from Japan to the US, say, indicates aggregate claims held by Japanese banks on all US-registered banks, as collected by the Bank of International Settlements (BIS). The size of each node in the figure is increasing in the total foreign claims of all other nodes on this node. The widths of the arrows are proportional to the foreign claims they represent.^[13] The country codes are given in Table Table 1.1.

In this network, an edge $(u, v)$ exists for almost every choice of $u$ and $v$ (i.e., almost every country in the network).^[14] Hence existence of an edge is not particularly informative. To understand the network, we need to record not just the existence or absence of a credit flow, but also the size of the flow. The correct data structure for recording this information is a “weighted directed graph,” or “weighted digraph.” In this section we define this object and investigate its properties.

1.4.2.1Definitions¶

A weighted digraph $\gG$ is a triple $(V, E, w)$ such that $(V, E)$ is a digraph and $w$ is a function from $E$ to $(0, \infty)$, called the weight function.

The definitions of accessibility, communication, periodicity and connectedness extend to any weighted digraph $\gG = (V, E, w)$ by applying them to $(V, E)$. For example, $(V, E, w)$ is called strongly connected if $(V, E)$ is strongly connected. The weighted digraph in Figure 1.15 is strongly connected.

1.4.2.2Adjacency Matrices of Weighted Digraphs¶

In Section 1.4.1.5 we discussed adjacency matrices of unweighted digraphs. The adjacency matrix of a weighted digraph $(V, E, w)$ with vertices $\{v_1, \ldots, v_n\}$ is the matrix

Clearly, once the vertices in $V$ are enumerated, the weight function and adjacency matrix provide the same information. We often work with the latter, since it facilitates computations.

In QuantEcon’s DiGraph implementation, weights are recorded via the keyword weighted:

A = ((0.9, 0.1, 0.0),
     (0.4, 0.4, 0.2),
     (0.1, 0.1, 0.8))
A = np.array(A)
G = qe.DiGraph(A, weighted=True)    # Store weights

One of the key points to remember about adjacency matrices is that taking the transpose “reverses all the arrows” in the associated digraph.

It is not difficult to see that each nonnegative $n \times n$ matrix $A = (a_{ij})$ can be viewed as the adjacency matrix of a weighted digraph with vertices equal to $\natset{n}$. The weighted digraph $\gG = (V, E, w)$ in question is formed by setting

We call $\gG$ the weighted digraph induced by $A$.

The next exercise helps to reinforce the point that transposes reverse the edges.

1.4.2.3Application: Quadratic Network Games¶

Acemoglu et al. (2016) and Zenou (2016) consider quadratic games with $n$ agents where agent $k$ seeks to maximize

Here $x = (x_i)_{i=1}^n$, $A$ is a symmetric matrix with $a_{ii}=0$ for all $i$, $\alpha \in (0,1)$ is a parameter and $\epsilon = (\epsilon_i)_{i=1}^n$ is a random vector. (This is the set up for the quadratic game in §21.2.1 of Acemoglu et al. (2016).) The $k$-th agent takes the decisions $x_j$ as given for all $j \neq k$ when maximizing (1.26).

In this context, $A$ is understood as the adjacency matrix of a graph with vertices $V = \natset{n}$, where each vertex is one agent. We can reconstruct the weighted digraph $(V, E, w)$ by setting $w(i, j) = a_{ij}$ and letting $E$ be all $(i,j)$ pairs in $\natset{n} \times \natset{n}$ with $a_{ij} > 0$. The weights identify some form of relationship between the agents, such as influence or friendship.

The network game described in this section has many interesting applications, including social networks, crime networks and peer networks. References are provided in Section 1.5.

1.4.2.4Properties¶

In this section, we examine some of the fundamental properties of and relationships among digraphs, weight functions and adjacency matrices. Throughout this section, without loss of generality, we consider a weighted digraph with $V = \natset{n}$.

As an additional convention, if $A$ is an adjacency matrix, and $A^k$ is the $k$-th power of $A$, then we write $a^k_{ij}$ for a typical element of $A^k$. With this notation, we observe that, since $A^{(s+t)} = A^s A^t$, the rules of matrix multiplication imply

($A^0$ is the identity.) The next proposition explains the significance of the powers.

In this context, the next result is fundamental.

We will find that the property of being primitive is valuable for analysis. (The Perron–Frobenius Theorem hints at this.) What do we need to add to strong connectedness to obtain primitiveness?

1.4.3Network Centrality¶

When studying networks of all varieties, a recurring topic is the relative “centrality” or “importance” of different nodes. One classic application is the ranking of web pages by search engines. Here are some examples related to economics:

• In which industry will one dollar of additional demand have the most impact on aggregate production, once we take into account all the backward linkages? In which sector will a rise in productivity have the largest effect on national output?

• A negative shock endangers the solvency of the entire banking sector. Which institutions should the government rescue, if any?

• In the network games considered in Section 1.4.2.3, the Nash equilibrium is $x^* = (I - \alpha A)^{-1} \epsilon$. Players’ actions are dependent on the topology of the network, as encoded in $A$. A common finding is that the level of activity or effort exerted by an agent (e.g., severity of criminal activity by a participant in a criminal network) can be predicted from their “centrality” within the network.

In this section we review essential concepts related to network centrality.^[15]

1.4.3.1Centrality Measures¶

Let $G$ be the set of weighted digraphs. A centrality measure associates to each $\gG = (V, E, w)$ in $G$ a vector $m(\gG) \in \RR^{|V|}$, where the $i$-th element of $m(\gG)$ is interpreted as the centrality (or rank) of vertex $v_i$. In most cases $m(\gG)$ is nonnegative. In what follows, to simplify notation, we take $V = \natset{n}$.

(Unfortunately, the definitions and terminology associated with even the most common centrality measures vary widely across the applied literature. Our convention is to follow the mathematicians, rather than the physicists. For example, our terminology is consistent with Benzi & Klymko (2015).)

1.4.3.2Authorities vs Hubs¶

Search engine designers recognize that web pages can be important in two different ways. Some pages have high hub centrality, meaning that they link to valuable sources of information (e.g., news aggregation sites) . Other pages have high authority centrality, meaning that they contain valuable information, as indicated by the number and significance of incoming links (e.g., websites of respected news organizations). Figure 1.19 helps to visualize the difference.

Similar ideas can and have been applied to economic networks (often using different terminology). For example, in production networks we study below, high hub centrality is related to upstreamness: such sectors tend to supply intermediate goods to many important industries. Conversely, a high authority ranking will coincide with downstreamness.

In what follows we discuss both hub-based and authority-based centrality measures, providing definitions and illustrating the relationship between them.

1.4.3.3Degree Centrality¶

Two of the most elementary measures of “importance” of a vertex in a given digraph $\gG = (V, E)$ are its in-degree and out-degree. Both of these provide a centrality measure. In-degree centrality $i(\gG)$ is defined as the vector $(i_d(v))_{v \in V}$. Out-degree centrality $o(\gG)$ is defined as $(o_d(v))_{v \in V}$. If $\gG$ is expressed as a Networkx DiGraph called G (see, e.g., Section 1.4.1.2), then $i(\gG)$ can be calculated via

iG = [G.in_degree(v) for v in G.nodes()]    

This method is relatively slow when $\gG$ is a large digraph. Since vectorized operations are generally faster, let’s look at an alternative method using operations on arrays.

To illustrate the method, recall the network of financial institutions in Figure 1.16. We can compute the in-degree and out-degree centrality measures by first converting the adjacency matrix, which is shown in (1.24), to a binary matrix that corresponds to the adjacency matrix of the same network viewed as an unweighted graph:

Now $U(i, j) = 1$ if and only if $i$ points to $j$. The out-degree and in-degree centrality measures can be computed as

respectively. That is, summing the rows of $U$ gives the out-degree centrality measure, while summing the columns gives the in-degree measure.

The out-degree centrality measure is a hub-based ranking, while the vector of in-degrees is an authority-based ranking. For the financial network in Figure 1.16, a high out-degree for a given institution means that it lends to many other institutions. A high in-degree indicates that many institutions lend to it.

Notice that, to switch from a hub-based ranking to an authority-based ranking, we need only transpose the (binary) adjacency matrix $U$. We will see that the same is true for other centrality measures. This is intuitive, since transposing the adjacency matrices reverses the direction of the edges (Exercise 1.4.4).

For a weighted digraph $\gG = (V, E, w)$ with adjacency matrix $A$, the weighted out-degree centrality and weighted in-degree centrality measures are defined as