# Economic Networks:
Theory and Computation
QuantEcon Book I

John Stachurski and Thomas J. Sargent

###### Contents

  1. Preface
  2. Common Symbols
  3. 1 Introduction
    1. 1.1 Motivation
    2. 1.2 Spectral Theory
      1. 1.2.1 Eigendecompositions
      2. 1.2.2 The Neumann Series Lemma
      3. 1.2.3 The Perron–Frobenius Theorem
    3. 1.3 Probability
      1. 1.3.1 Discrete Probability
      2. 1.3.2 Power Laws
    4. 1.4 Graph Theory
      1. 1.4.1 Unweighted Directed Graphs
      2. 1.4.2 Weighted Digraphs
      3. 1.4.3 Network Centrality
      4. 1.4.4 Scale-Free Networks
    5. 1.5 Chapter Notes
  4. 2 Production
    1. 2.1 Multisector Models
      1. 2.1.1 Production Networks
      2. 2.1.2 Equilibrium
      3. 2.1.3 Demand Shocks
      4. 2.1.4 Forward Linkages
    2. 2.2 General Equilibrium
      1. 2.2.1 Supply and Demand
      2. 2.2.2 The Granular Hypothesis
      3. 2.2.3 Network Structure and Shock Propagation
    3. 2.3 More Spectral Theory
      1. 2.3.1 Vector Norms
      2. 2.3.2 Matrix Norms
      3. 2.3.3 Iteration in Matrix Space
      4. 2.3.4 Exact Stability Conditions
    4. 2.4 Chapter Notes
  5. 3 Optimal Flows
    1. 3.1 Shortest Paths
      1. 3.1.1 Definition and Examples
      2. 3.1.2 Bellman’s Method
      3. 3.1.3 Betweenness Centrality
    2. 3.2 Linear Programming and Duality
      1. 3.2.1 Linear Assignment
      2. 3.2.2 Linear Programming
    3. 3.3 Optimal Transport
      1. 3.3.1 The Monge-Kantorovich Problem
      2. 3.3.2 Kantorovich Duality
      3. 3.3.3 Optimal Transport and Competitive Equilibria
      4. 3.3.4 The General Flow Problem
    4. 3.4 Chapter Notes
  6. 4 Markov Chains and Networks
    1. 4.1 Markov Chains as Digraphs
      1. 4.1.1 Markov Models
      2. 4.1.2 Distribution Dynamics
      3. 4.1.3 Stationarity
    2. 4.2 Asymptotics
      1. 4.2.1 Ergodicity
      2. 4.2.2 Aperiodicity and Stability
      3. 4.2.3 The Markov–Dobrushin Coefficient
      4. 4.2.4 Information and Social Networks
    3. 4.3 Chapter Notes
  7. 5 Nonlinear Interactions
    1. 5.1 Fixed Point Theory
      1. 5.1.1 Contraction Mappings
      2. 5.1.2 Shortest Paths Revisited
      3. 5.1.3 Supply Constraints
      4. 5.1.4 Fixed Points and Monotonicity
    2. 5.2 Financial Networks
      1. 5.2.1 Contagion
      2. 5.2.2 Default Cascades
      3. 5.2.3 Equity-Cross Holdings
    3. 5.3 Chapter Notes
  8. I Appendices
    1. 6 Appendix
      1. 6.1 Math Review
        1. 6.1.1 Sets and Functions
        2. 6.1.2 Order
        3. 6.1.3 Convergence
        4. 6.1.4 Linear Algebra
        5. 6.1.5 Convexity and Concavity
        6. 6.1.6 Optimization
        7. 6.1.7 Lagrangian Duality
      2. 6.2 Solutions
    2. List of Authors

### Preface

The development and use of network science has grown exponentially since the
beginning of the 21st century. The ideas and techniques found in this field
are already core tools for analyzing a vast range of phenomena, from epidemics
and disinformation campaigns to chemical reactions and brain function.

In economics, network theory is typically taught as a specialized subfield,
available to students as one of many elective courses towards the end of their
program. However, we are rapidly approaching the stage where every aspiring
scientist—including social scientists and economists—wants to know the
foundations of this field. It is arguably the case that, just as every well-
trained economist learns the basics of convex optimization, maximum likelihood
and linear regression, so too should every graduate student in economics learn
the fundamental ideas of network theory.

This textbook is an introduction to economic networks, intended for students
and researchers in the fields of economics and applied mathematics. The
textbook emphasizes quantitative modeling, with the main underlying tools
being graph theory, linear algebra, fixed point theory and programming. Most
mathematical tools are covered from first principles, with the two main
technical results—the Neumann series lemma and the Perron–Frobenius
theorem—playing a central role.

The text is suitable for a one-semester course, taught either to advanced
undergraduate students who are comfortable with linear algebra or to beginning
graduate students. (For example, although we define eigenvalues, an ideal
student would already know what eigenvalues and eigenvectors are, so that
concepts like “eigenvector centrality” or results like the Neumann series
lemma are readily absorbed.) The text will also suit students from
mathematics, engineering, computer science and other related fields who wish
to learn about connection between economics and networks.

Several excellent textbooks on network theory in economics and social science
already exist, including Jackson, (2010), Easley et al., (2010), and Borgatti
et al., (2018), as well as the handbook by Bramoullé et al., (2016). These
textbooks have broad scope and treat many useful applications. In contrast,
our book is narrower and more technical. It provides mathematical,
computational and graph-theoretic foundations that are required to understand
and apply network theory, along with a treatment of some of the most important
network applications in economics, finance and operations research. It can be
used as a complementary resource, or as a preliminary course that facilitates
understanding of the alternative texts listed above, as well as research
papers in the area.

The book contains a mix of Python and Julia code. The majority is in Python
because the libraries are somewhat more stable at the time of writing,
although Julia also has strong graph manipulation and optimization libraries.
Code for figures is available from the authors. There are many solved
exercises, ranging from simple to quite hard. At the end of each chapter we
provide notes, informal comments and references.

We are greatly indebted to Jim Savage and Schmidt Futures for generous
financial support, as well as to Shu Hu for his outstanding research
assistance. QuantEcon research fellow Matthew McKay generously lent us his
time and remarkable expertise in data analysis, networks and visualization.
QuantEcon research assistant Mark Dawkins turned a messy collection of code
files into an elegant companion Jupyter book. For many important fixes,
comments and suggestions, we thank Quentin Batista, Rolf Campos, Fernando
Cirelli, Rebekah Dix, Saya Ikegawa, Fazeleh Kazemian, Dawie van Lill, Simon
Mishricky, Pietro Monticone, Flint O’Neil, Zejin Shi, Akshay Shanker, Arnav
Sood, Natasha Watkins and Chao Wei. Finally, Chase Coleman, Alfred Galichon,
Spencer Lyon, Daisuke Oyama and Jesse Perla are collaborators at QuantEcon,
and almost everything we write has benefited from their input. This text is no
exception.

### Common Symbols

$P\implies Q$ |  $P$ implies $Q$
---|---
$P\iff Q$ |  $P\implies Q$ and $Q\implies P$
$[n]$ | the set $\\{1,\ldots,n\\}$
$\alpha:=1$ |  $\alpha$ is defined as equal to $1$
$f\equiv 1$ | function $f$ is everywhere equal to $1$
$\wp(A)$ | the power set of $A$; that is, the collection of all subsets of given set $A$
$\mathbbm{N}$, $\mathbbm{Z}$ and $\mathbbm{R}$ | the natural numbers, integers and real numbers respectively
$\mathbbm{C}$ | the set of complex numbers (see §6.1.1.8)
$\mathbbm{Z}_{+}$, $\mathbbm{R}_{+}$, etc. | the nonnegative elements of $\mathbbm{Z}$, $\mathbbm{R}$, etc.
$\mathbbm{M}^{n\times k}$ | all $n\times k$ matrices
$\operatorname{diag}(a_{1},\ldots,a_{n})$ | the diagonal matrix with $a_{1},\ldots a_{n}$ on the principle diagonal
$\delta_{x}$ | the probability distribution concentrated on point $x$
$|x|$ | the absolute value of $x\in\mathbbm{R}$
$|B|$ | the cardinality of (number of elements in) set $B$
$f\colon A\to B$ |  $f$ is a function from set $A$ to set $B$
$\mathbbm{R}^{S}$ | the set of all functions from $S$ to $\mathbbm{R}$
$\mathbbm{R}^{n}$ | all $n$-tuples of real numbers
$\|x\|_{1}$ | the $\ell_{1}$ norm $\sum_{i}|x_{i}|$ (see §2.3.1.1)
$\|x\|_{\infty}$ | the $\ell_{\infty}$ norm $\max_{i}|x_{i}|$ (see §2.3.1.1)
$\|A\|$ when $A\in\mathbbm{M}^{n\times k}$ | the operator norm of $A$ (see §2.3.2.3)
$\langle a,b\rangle$ | the inner product of $a$ and $b$
$g\ll h$ | function (or vector) $g$ is everwhere strictly less than $h$
$\mathbbm{1}$ | vector of ones or function everywhere equal to one
$\mathbbm{1}\\{P\\}$ | indicator, equal to 1 if statement $P$ is true and 0 otherwise
iid | independent and identically distributed

$i_{d}(v)$ | in-degree of node $v$
---|---
$o_{d}(v)$ | out-degree of node $v$
$\mathscr{I}(v)$ | set of direct predecessors of node $v$
$\mathscr{O}(v)$ | set of direct successors of node $v$
$u\to v$ | node $v$ is accessible from node $u$
$X\stackrel{{\scriptstyle d}}{{=}}Y$ |  $X$ and $Y$ have the same distribution
$X\sim F$ |  $X$ has distribution $F$
$\Pi(\varphi,\psi)$ | the set of all couplings of $(\varphi,\psi)$

###  Chapter 1 Introduction

> Relations are the fundamental fabric of reality.
>
> Michele Coscia

####  1.1 Motivation

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 text, 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.

Figures 1.1–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 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.111This figure
was constructed by QuantEcon research fellow Matthew McKay, using
International Trade Data (SITC, Rev 2) collected by The Growth Lab at Harvard
University.

Figure 1.2 shows international trade in large commercial aircraft in
2019.222This figure was also constructed by Matthew McKay, using data 2019
International Trade Data SITC Revision 2, code 7924. The data pertains to
trade in commercial aircraft weighted at least 15,000kg. It was sourced from
CID Dataverse. 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.

Figure 1.1:  International trade in crude oil 2019

Figure 1.2:  International trade in commercial aircraft during 2019

While some readers viewing Figures 1.1–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 §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 §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 and 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})$.333See §6.1.3 for a discussion of big O notation. In the
Carvalho and 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 on
page Common Symbols, as well the mathematical topics in the appendix, which
start on page 6. (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.2 Spectral 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 fundamental theorem of Perron and
Frobenius.

#####  1.2.1 Eigendecompositions

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.1 Eigenvalues

Fix $A$ in $\mathbbm{M}^{n\times n}$. A scalar $\lambda\in\mathbbm{C}$ is
called an eigenvalue of $A$ if there exists a nonzero $e\in\mathbbm{C}^{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$).

Using pencil and paper, confirm that Julia’s output is correct. In particular,
show that

$A=\begin{pmatrix}0&-1\\\
1&0\end{pmatrix}\quad\implies\quad\sigma(A)=\\{i,-i\\},$

with corresponding eigenvectors $(-1,i)^{\top}$ and $(-1,-i)^{\top}$.

For $\lambda_{1}=i$, we have

$Ae_{1}=\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\begin{pmatrix}-1\\\
i\end{pmatrix}=\begin{pmatrix}-i\\\ -1\end{pmatrix}=\lambda_{1}e_{1}.$

Similarly for $\lambda_{2}=-i$, we have

$Ae_{2}=\begin{pmatrix}0&-1\\\ 1&0\end{pmatrix}\begin{pmatrix}-1\\\
-i\end{pmatrix}=\begin{pmatrix}i\\\ -1\end{pmatrix}=\lambda_{2}e_{2}.$

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

Prove: if $(\lambda,e)$ is an eigenpair of $A$ and $\alpha$ is a nonzero
scalar, then $(\lambda,\alpha e)$ is also an eigenpair of $A$.

Fix an eigenpair $(\lambda,e)$ of $A$ and a nonzero scalar $\alpha$. We have

$A(\alpha e)=\alpha Ae=\lambda(\alpha e).$

Hence $\alpha e$ is an eigenvector and $\lambda$ is an eigenvalue, as claimed.

######  Lemma 1.2.1.

$\lambda\in\mathbbm{C}$ is an eigenvalue of $A$ if and only if $\det(A-\lambda
I)=0$.

###### Proof.

If $\lambda\in\mathbbm{R}$, then Lemma 1.2.1 follows directly from Theorem
6.1.14 on page 6.1.14, since $\det(A-\lambda I)=0$ is equivalent to existence
of nonzero vector $e$ such that $(A-\lambda I)e=0$, which in turn says that
$\lambda$ is an eigenvalue of $A$. The same arguments extend to the case
$\lambda\in\mathbbm{C}$ because the statements in Theorem 6.1.14 are also
valid for complex-valued matrices (see, e.g., Jänich, (1994)). ∎

It can be shown that $p(\lambda):=\det(A-\lambda I)$ is a polynomial of degree
$n$.444See, for example, Jänich, (1994), Chapter 6. This polynomial is called
the characteristic polynomial of $A$. By the Fundamental Theorem of Algebra,
there are $n$ roots (i.e., solutions in $\mathbbm{C}$ to the equation
$p(\lambda)=0$), although some may be repeated as in the complete
factorization of $p(\lambda)$. By Lemma 1.2.1,

  1. (i)

each of these roots is an eigenvalue, and

  2. (ii)

no other eigenvalues exist besides these $n$ roots.

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.1.1. In other words, the linear
span of $\\{e\in\mathbbm{C}^{n}:(\lambda,e)\text{ is an eigenpair}\\}$ (called
the eigenspace of $\lambda$) is one-dimensional.

For $A\in\mathbbm{M}^{n\times n}$, show that $\lambda\in\sigma(A)$ iff
$\tau\lambda\in\sigma(\tau A)$ for all $\tau>0$.

Fix $A\in\mathbbm{M}^{n\times n}$ and $\tau>0$. If $\lambda\in\sigma(A)$, then
$\tau^{n}\det(A-\lambda I)=0$, or $\det(\tau A-\tau\lambda I)=0$. Hence
$\tau\lambda\in\sigma(\tau A)$. To obtain the converse implication, multiply
by $1/\tau$.

A useful fact concerning eigenvectors is that if the characteristic polynomial
$p(\lambda):=\det(A-\lambda I)$ has $n$ distinct roots, then the $n$
corresponding eigenvectors form a basis of $\mathbbm{C}^{n}$. Prove this for
the case where all eigenvectors are real—that is show that the $n$ (real)
eigenvectors form a basis of $\mathbbm{R}^{n}$. (Bases are defined in
§6.1.4.2. Proving this for $n=2$ is also a good effort.)

If $p(\lambda):=\det(A-\lambda I)$ has $n$ distinct roots, then
$|\sigma(A)|=n$. For each $\lambda_{i}\in\sigma(A)$, let $e_{i}$ be a
corresponding eigenvector. It suffices to show that $\\{e_{i}\\}_{i=1}^{n}$ is
linearly independent. To this end, let $k$ be the largest number such that
$\\{e_{1},\ldots,e_{k}\\}$ is independent. Seeking a contradiction, suppose
that $k<n$. Then $e_{k+1}=\sum_{i=1}^{k}\alpha_{i}e_{i}$ for suitable scalars
$\\{\alpha_{i}\\}$. Hence, by $Ae_{k+1}=\lambda_{k+1}e_{k+1}$, we have

$\sum_{i=1}^{k}\alpha_{i}\lambda_{i}e_{i}=\sum_{i=1}^{k}\alpha_{i}\lambda_{k+1}e_{i}\quad\iff\quad\sum_{i=1}^{k}\alpha_{i}(\lambda_{i}-\lambda_{k+1})e_{i}=0.$

Since $\\{e_{1},\ldots,e_{k}\\}$ is independent, we have
$\alpha_{i}(\lambda_{i}-\lambda_{k+1})=0$ for all $i$. At least one
$\alpha_{i}$ is nonzero, so $\lambda_{i}=\lambda_{k+1}$ for some $i\leqslant
k$. Contradiction.

######  1.2.1.2 The Eigendecomposition

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

  * •

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

  * •

the $t$-th power $D^{t}$ is just $\operatorname{diag}(\lambda_{i}^{t})$, and

  * •

the inverse $D^{-1}$ is just $\operatorname{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 $\mathbbm{R}^{n}$ via an alternative basis. This can be extremely useful.
The key ideas are described below.

$A\in\mathbbm{M}^{n\times n}$ is called diagonalizable if

$A=PDP^{-1}\text{ for some
}D=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{n})\text{ and nonsingular
matrix }P.$

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

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

${\mathbbm{R}^{n}}$${\mathbbm{R}^{n}}$${\mathbbm{C}^{n}}$${\mathbbm{C}^{n}}$$\scriptstyle{A}$$\scriptstyle{P^{-1}}$$\scriptstyle{D}$$\scriptstyle{P}$

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

The equality $A=PDP^{-1}$ can also be written as $AP=PD$. 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.

Confirm this. Why are column vectors taken from $P$ nonzero, as required by
the definition of eigenvalues?

Suppose to the contrary that there is one zero column vector in $P$. Then $P$
is not nonsingular. Contradiction.

The trace of a matrix is equal to the sum of its eigenvalues, and the
determinant is their product. Prove this fact in the case where $A$ is
diagonalizable.

Let $A$ be as stated, with $A=PDP^{-1}$. Using elementary properties of the
trace and determinant, we have

$\operatorname{trace}(A)=\operatorname{trace}(PDP^{-1})=\operatorname{trace}(DPP^{-1})=\operatorname{trace}(D)=\sum_{i}\lambda_{i}$

and

$\det(A)=\det(P)\det(D)\det(P^{-1})=\det(P)\det(D)\det(P)^{-1}=\det(D)=\prod_{i}\lambda_{i}.$

The asymptotic properties of $m\mapsto A^{m}$ are determined by the
eigenvalues of $A$. This is clearest in the diagonalizable case, where
$A=P\operatorname{diag}(\lambda_{i})P^{-1}$. To illustrate, use induction to
show that

$A=P\operatorname{diag}(\lambda_{i})P^{-1}\;\implies\;A^{m}=P\operatorname{diag}(\lambda_{i}^{m})P^{-1}\text{
for all }m\in\mathbbm{N}.$ (1.1)

When does diagonalizability hold?

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

######  Theorem 1.2.2.

A matrix $A\in\mathbbm{M}^{n\times n}$ is diagonalizable if and only if its
eigenvectors form a basis of $\mathbbm{C}^{n}$.

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

######  Corollary 1.2.3.

If $A\in\mathbbm{M}^{n\times n}$ has $n$ distinct eigenvalues, then $A$ is
diagonalizable.

###### Proof.

See Exercise 1.2.1.1. ∎

Give a counterexample to the statement that the condition in Corollary 1.2.3
is necessary as well as sufficient.

If $I$ is the identity and $Ie=\lambda e$ for some nonzero $e$, then
$e=\lambda e$ and hence $\lambda=1$. Hence $\sigma(A)=\\{1\\}$. At the same
time, $I$ is diagonalizable, since $I=IDI^{-1}$ when $D=I$.

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.

######  Theorem 1.2.4 (Spectral theorem).

If $A\in\mathbbm{M}^{n\times n}$ is symmetric, then there exists a real
orthonormal $n\times n$ matrix $U$ such that

$A=UDU^{\top}\quad\text{with}\quad\lambda_{i}\in\mathbbm{R}_{+}\text{ for all
}i,\text{ where }D=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{n}).$

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.3 Worker 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.

unemployedemployed$\alpha$$\beta$$1-\beta$$1-\alpha$ Figure 1.3:  Worker
transition dynamics

We translate these dynamics into the matrix

$P_{w}=\begin{pmatrix}1-\alpha&\alpha\\\
\beta&1-\beta\end{pmatrix}\quad\text{where}\quad
0\leqslant\alpha,\beta\leqslant 1.$

  * •

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.

Using Lemma 1.2.1, show that the two eigenvalues of $P_{w}$ are
$\lambda_{1}:=1$ and $\lambda_{2}:=1-\alpha-\beta$. Show that, when
$\min\\{\alpha,\beta\\}>0$,

$e_{1}:=\begin{pmatrix}1\\\ 1\end{pmatrix}\quad\text{and}\quad
e_{2}:=\begin{pmatrix}-\alpha\\\ \beta\end{pmatrix}$

are two corresponding eigenvectors, and that $\lambda_{1}$ and $\lambda_{2}$
are simple.

Show that, when $\alpha=\beta=0$, the eigenvalue $\lambda_{1}$ is not simple.

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\mathbbm{N}$. This
problem is simplified if we use diagonalization.

Assume that $\min\\{\alpha,\beta\\}>0$. (When $\alpha=\beta=0$, computing the
powers of $P_{w}$ is trivial.) Show that

$P_{w}=EDE^{-1}\quad\text{when}\quad D=\begin{pmatrix}1&0\\\
0&\lambda_{2}\end{pmatrix}\quad\text{and}\quad E=\begin{pmatrix}1&-\alpha\\\
1&\beta\end{pmatrix}.$

Using (1.1), prove that

$P_{w}^{m}=\frac{1}{\alpha+\beta}\begin{pmatrix}\beta+\alpha(1-\alpha-\beta)^{m}&\alpha(1-(1-\alpha-\beta)^{m})\\\
\beta(1-(1-\alpha-\beta)^{m})&\alpha+\beta(1-\alpha-\beta)^{m}\end{pmatrix}$
(1.2)

for every $m\in\mathbbm{N}$.

######  1.2.1.4 Left Eigenvectors

A vector $\varepsilon\in\mathbbm{C}^{n}$ is called a left eigenvector of
$A\in\mathbbm{M}^{n\times n}$ if $\varepsilon$ is an eigenvector of
$A^{\top}$. In other words, $\varepsilon$ is nonzero and there exists a
$\lambda\in\mathbbm{C}$ such that $A^{\top}\varepsilon=\lambda\varepsilon$. We
can alternatively write the expression as
$\varepsilon^{\top}A=\lambda\varepsilon^{\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=PDP^{-1}$ with $D=\operatorname{diag}(\lambda_{i})$. We know from earlier
discussion that the columns of $P$ are the (right) eigenvectors of $A$.

Let $Q=(P^{\top})^{-1}$. Prove that $Q^{\top}P=I$ and $A^{\top}=QDQ^{-1}$.

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

Let $(e_{i})_{i=1}^{n}$ be right eigenvectors of $A$ and let
$(\varepsilon_{i})_{i=1}^{n}$ be the left eigenvectors. Prove that

$\left\langle{\varepsilon_{i},e_{j}}\right\rangle=\mathbbm{1}\\{i=j\\}\qquad(i,j\in[n]).$
(1.3)

(Hint: Use the results of Exercise 1.2.1.4.)

Continuing with the notation defined above and continuing to assume that $A$
is diagonalizable, prove that

$A=\sum_{i=1}^{n}\lambda_{i}e_{i}\varepsilon_{i}^{\top}\quad\text{and}\quad
A^{m}=\sum_{i=1}^{n}\lambda_{i}^{m}e_{i}\varepsilon_{i}^{\top}$ (1.4)

for all $m\in\mathbbm{N}$. The expression for $A$ on the left hand side of
(1.4) is called the spectral representation of $A$.

Prove that each $n\times n$ matrix $\lambda_{i}e_{i}\varepsilon_{i}^{\top}$ in
the sum $\sum_{i=1}^{n}\lambda_{i}e_{i}\varepsilon_{i}^{\top}$ is rank 1.

######  1.2.1.5 Similar Matrices

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

Prove that similarity between matrices is an equivalence relation (see
§6.1.1.2) on $\mathbbm{M}^{n\times n}$.

The fact that similarity is an equivalence relation on $\mathbbm{M}^{n\times
n}$ implies that this relation partitions $\mathbbm{M}^{n\times n}$ into
disjoint equivalence classes, elements of which are all similar. Prove that
all matrices in each equivalence class share the same eigenvalues.

Prove: If $A$ is similar to $B$, then $A^{m}$ is similar to $B^{m}$. In
particular

$A=PBP^{-1}\;\implies\;A^{m}=PB^{m}P^{-1}\text{ for all }m\in\mathbbm{N}.$

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.555The only concern with this shift process is that $P$ can be ill-
conditioned, implying that the inverse is numerically unstable.

#####  1.2.2 The Neumann Series Lemma

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

$\sum_{i\geqslant 0}a^{i}=\frac{1}{1-a}.$ (1.5)

This geometric series representation extends to matrices: If $A$ is a matrix
satisfying a certain condition, then (1.5) holds, in the sense that
$\sum_{i\geqslant 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.1 Spectral Radii

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

$r(A):=\max\\{|\lambda|:\lambda\text{ is an eigenvalue of }A\\}.$ (1.6)

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.

######  Remark 1.2.1.

For any square matrix $A$, we have $r(A^{\top})=r(A)$. This follows from the
fact that $A$ and $A^{\top}$ always have the same eigenvalues.

######  Example 1.2.1.

As usual, diagonal matrices supply the simplest example: If
$D=\operatorname{diag}(d_{i})$, then the spectrum $\sigma(D)$ is just
$\\{d_{i}\\}_{i\in[n]}$ and hence $r(D)=\max_{i}|d_{i}|$.

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.2 Geometric Series

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

######  Theorem 1.2.5 (Neumann series lemma (NSL)).

If $A$ is in $\mathbbm{M}^{n\times n}$ and $r(A)<1$, then $I-A$ is nonsingular
and

$(I-A)^{-1}=\sum_{m=0}^{\infty}A^{m}.$ (1.7)

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+AS=S$.
Reorganizing gives $(I-A)S=I$, which is equivalent to (1.7). The main
technical issue is showing that the power series converges. The full proof
shows that this always holds when $r(A)<1$.

Fix $A\in\mathbbm{M}^{n\times n}$. Prove the following: if $r(A)<1$, then, for
each $b\in\mathbbm{R}^{n}$ the linear system $x=Ax+b$ has the unique solution
$x^{*}\in\mathbbm{R}^{n}$ given by

$x^{*}=\sum_{m=0}^{\infty}A^{m}b.$ (1.8)

Fix $A\in\mathbbm{M}^{n\times n}$ and $b\in\mathbbm{R}^{n}$ where $r(A)<1$. We
can write $x=Ax+b$ as $(I-A)x=b$. Since $r(A)<1$, $I-A$ is invertible and
hence the linear system $(I-A)x=b$ has unique solution $x^{*}=(I-A)^{-1}b$.
The expression $x^{*}=\sum_{m=0}^{\infty}A^{m}b$ follows from the Neumann
series lemma.

#####  1.2.3 The 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.1 Order in Matrix Space

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

  * •

$A\geqslant 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 “almost everywhere
strictly positive,” which sometimes provide sufficient positivity for the
theorems that we need.

Regarding these two notions, for $A\in\mathbbm{M}^{n\times n}$, we say that
$A\geqslant 0$ is

  * •

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

  * •

primitive if there exists an $m\in\mathbbm{N}$ such that $A^{m}\gg 0$.

Evidently, for $A\in\mathbbm{M}^{n\times n}$ we have

$A\gg 0\;\implies\;A\text{ primitive }\;\implies\;A\text{ irreducible
}\;\implies\;A\geqslant 0.$

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

By examining the expression for $P_{w}^{m}$ in (1.2), show that $P_{w}$ is

  1. (i)

irreducible if and only if $0<\alpha,\beta\leqslant 1$; and

  2. (ii)

primitive if and only if $0<\alpha,\beta\leqslant 1$ and
$\min\\{\alpha,\beta\\}<1$.

((i), ($\Rightarrow$)) Suppose that $P_{w}$ is irreducible and yet $\alpha=0$.
Then, by the expression for $P^{m}_{w}$ in (1.2), we have $P_{w}^{m}(1,2)=0$
for all $m$. This contradicts irreducibility, so $\alpha>0$ must hold. A
similar argument shows that $\beta>0$.

((i), ($\Leftarrow$)) If $\alpha,\beta>0$, then the diagonal elements are
strictly positive whenever $m$ is even. A small amount of algebra shows that
the off-diagonal elements are strictly positive whenever $m$ is odd. Hence
$P_{w}+P_{w}^{2}\gg 0$ and $P_{w}$ is irreducible.

((ii), ($\Rightarrow$)) Suppose that $P_{w}$ is primitive. Then $P_{w}$ is
irreducible, so it remains only to show that $\min\\{\alpha,\beta\\}<1$.
Suppose to the contrary that $\alpha=\beta=1$. Then $P_{w}^{m}$ has zero
diagonal elements when $m$ is even and zero off-diagonal elements when $m$ is
odd. This contradicts the primitive property, so $\min\\{\alpha,\beta\\}<1$
must hold.

((ii), ($\Leftarrow$)) Suppose that $0<\alpha,\beta\leqslant 1$ and
$\alpha<1$. Some algebra shows that $P^{2}_{2}\gg 0$. The same is true when
$0<\alpha,\beta\leqslant 1$ and $\beta<1$. Hence $P_{w}$ is primitive.

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

  * •

$A\geqslant B$ if $A-B\geqslant 0$ and $A\gg B$ if $A-B\gg 0$,

  * •

$A\leqslant 0$ if $-A\geqslant 0$, etc.

Show that $\leqslant$ is a partial order (see §6.1.2.1) on
$\mathbbm{M}^{n\times k}$.

The partial order $\leqslant$ discussed in Exercise 1.2.3.1 is usually called
the pointwise partial order on $\mathbbm{M}^{n\times k}$. Analogous notation
and terminology are used for vectors.

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

Show that the map $x\mapsto Ax$ is order-preserving (see §6.1.2.3) whenever
$A\geqslant 0$ (i.e., $x\leqslant y$ implies $Ax\leqslant Ay$ for any
conformable vectors $x,y$).

Fix $A\in\mathbbm{M}^{n\times k}$ with $A\geqslant 0$, along with
$x,y\in\mathbbm{R}^{k}$. From $x\leqslant y$ we have $y-x\geqslant 0$, so
$A(y-x)\geqslant 0$. But then $Ay-Ax\geqslant 0$, or $Ax\leqslant Ay$.

######  1.2.3.2 Statement of the Theorem

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

$A=\operatorname{diag}(-1,0)\;\implies\;\sigma(A)=\\{-1,0\\}\;\text{ while
}r(A)=1.$

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

######  Theorem 1.2.6 (Perron–Frobenius).

If $A\geqslant 0$, then $r(A)$ is an eigenvalue of $A$ with nonnegative real
right and left eigenvectors:

$\exists\,\text{ nonzero }e,\varepsilon\in\mathbbm{R}^{n}_{+}\text{ such that
}Ae=r(A)e\text{ and }\varepsilon^{\top}A=r(A)\varepsilon^{\top}.$ (1.9)

If $A$ is irreducible, then, in addition,

  1. (i)

$r(A)$ is strictly positive and a simple eigenvalue,

  2. (ii)

the eigenvectors $e$ and $\varepsilon$ are everywhere positive, and

  3. (iii)

eigenvectors of $A$ associated with other eigenvalues fail to be nonnegative.

If $A$ is primitive, then, in addition,

  1. (i)

the inequality $|\lambda|\leqslant r(A)$ is strict for all eigenvalues
$\lambda$ of $A$ distinct from $r(A)$, and

  2. (ii)

with $e$ and $\varepsilon$ normalized so that
$\left\langle{\varepsilon,e}\right\rangle=1$, we have

$r(A)^{-m}A^{m}\to e\,\varepsilon^{\top}\qquad(m\to\infty).$ (1.10)

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 $\varepsilon$ 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\mathbbm{M}^{n\times n}$ is primitive and fix any
$x\in\mathbbm{R}^{n}$. Consider what happens to the point $x_{m}:=A^{m}x$ as
$m$ grows. By (1.10) we have $A^{m}x\approx r(A)^{m}ce$ for large $m$, where
$c=\varepsilon^{\top}x$. In other words, asymptotically, the sequence
$(A^{m}x)_{m\in\mathbbm{N}}$ 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.

The $n\times n$ matrix $P:=e\,\varepsilon^{\top}$ in (1.10) is called the
Perron projection of $A$. Prove that $P^{2}=P$ (a property that is often used
to define projection matrices) and $\operatorname{rank}P=1$. Describe the one-
dimensional space that $P$ projects all of $\mathbbm{R}^{n}$ into.

######  Example 1.2.2.

Fix $A\geqslant 0$. If $r(A)=1$, then $I-A$ is not invertible. To see this,
observe that, by Theorem 1.2.6, since $r(A)$ is an eigenvalue of $A$, there
exists a nonzero vector $e$ such that $(I-A)e=0$. The claim follows. (Why?)

######  1.2.3.3 Worker Dynamics II

We omit the full proof of Theorem 1.2.6, which is quite long and can be found
in Meyer, (2000), Seneta, 2006b  or Meyer-Nieberg, (2012).666See also Glynn
and Desai, (2018), which provides a new proof of the main results, based on
probabilistic arguments, including extensions to infinite state spaces.
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

$P_{w}=\begin{pmatrix}1-\alpha&\alpha\\\
\beta&1-\beta\end{pmatrix}\quad\text{with}\quad
0\leqslant\alpha,\beta\leqslant 1.$

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

You might recall from $\S\ref{sss:wdi}$ 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
($\varepsilon_{1},\varepsilon_{2}$) are, respectively,

$e_{1}:=\begin{pmatrix}1\\\ 1\end{pmatrix},\quad
e_{2}:=\begin{pmatrix}-\alpha\\\
\beta\end{pmatrix},\quad\varepsilon_{1}:=\frac{1}{\alpha+\beta}\begin{pmatrix}\alpha\\\
\beta\end{pmatrix}\quad\text{and}\quad\varepsilon_{2}:=\begin{pmatrix}\alpha\\\
-\alpha\end{pmatrix}.$

Verify these claims. (The right eigenvectors were treated in §1.2.1.3.)

Recall from Exercise 1.2.3.1 that $P_{w}$ is irreducible if and only if both
$\alpha$ and $\beta$ are strictly positive. Show that all the claims about
irreducible matrices in the Perron–Frobenius theorem are valid for $P_{w}$
under this irreducibility condition.

Recall from Exercise 1.2.3.1 that $P_{w}$ is primitive if and only if
$0<\alpha,\beta\leqslant 1$ and $\min\\{\alpha,\beta\\}<1$. Verify the
additional claim (1.10) for $P_{w}$ under these conditions. In doing so, you
can use the expression for $P_{w}^{m}$ in (1.2).

######  1.2.3.4 Bounding 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\mathbbm{M}^{n\times n}$ and set

  * •

$\operatorname{rowsum}_{i}(A):=\sum_{j}a_{ij}=$ the $i$-th row sum of $A$ and

  * •

$\operatorname{colsum}_{j}(A):=\sum_{i}a_{ij}=$ the $j$-th column sum of $A$.

######  Lemma 1.2.7.

If $A\geqslant 0$, then

  1. (i)

$\min_{i}\operatorname{rowsum}_{i}(A)\leqslant
r(A)\leqslant\max_{i}\operatorname{rowsum}_{i}(A)$ and

  2. (ii)

$\min_{j}\operatorname{colsum}_{j}(A)\leqslant
r(A)\leqslant\max_{j}\operatorname{colsum}_{j}(A)$.

###### Proof.

Let $A$ be as stated and let $e$ be the right eigenvector in (1.9). Since $e$
is nonnegative and nonzero, we can and do assume that $\sum_{j}e_{j}=1$. From
$Ae=r(A)e$ we have $\sum_{j}a_{ij}e_{j}=r(A)e_{i}$ for all $i$. Summing with
respect to $i$ gives $\sum_{j}\operatorname{colsum}_{j}(A)e_{j}=r(A)$. Since
the elements of $e$ are nonnegative and sum to one, $r(A)$ is a weighted
average of the column sums. Hence the second pair of bounds in Lemma 1.2.7
holds. The remaining proof is similar (use the left eigenvector). ∎

####  1.3 Probability

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

#####  1.3.1 Discrete Probability

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

######  1.3.1.1 Probability on Finite Sets

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

$\mathscr{D}(S):=\left\\{\varphi\in\mathbbm{R}^{S}_{+}\;:\>\sum_{x\in
S}\varphi(x)=1\right\\}$

and call $\mathscr{D}(S)$ the set of distributions on $S$. We say that a
random variable $X$ taking values in $S$ has distribution
$\varphi\in\mathscr{D}(S)$ and write $X\stackrel{{\scriptstyle
d}}{{=}}\varphi$ if

$\mathbbm{P}\\{X=x\\}=\varphi(x)\quad\text{for all }x\in S.$

A distribution $\varphi$ can also be understood as a vector
$(\varphi(x_{i}))_{i=1}^{n}\in\mathbbm{R}^{n}$ (see Lemma 6.1.2 in §6.1.1.3).
As a result, $\mathscr{D}(S)$ can be viewed as a subset of $\mathbbm{R}^{n}$.
Figure 1.4 provides a visualization when $S=\\{1,2,3\\}$. Each
$\varphi\in\mathscr{D}(S)$ is identified by the point
$(\varphi(1),\varphi(2),\varphi(3))$ in $\mathbbm{R}^{3}$.

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

Figure 1.4:  If $S=\\{1,2,3\\}$, then $\mathscr{D}(S)$ is the unit simplex in
$\mathbbm{R}^{3}$

Throughout, given $x\in S$, we use the symbol $\delta_{x}$ to represent the
element of $\mathscr{D}(S)$ that puts all mass on $x$. In other words,
$\delta_{x}(y)=\mathbbm{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$,

$\mathbbm{P}\\{X\in A\\}=\sum_{i}\mathbbm{P}\\{X\in A\,|\,X\in
B_{i}\\}\mathbbm{P}\\{X\in B_{i}\\}$ (1.11)

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

Prove (1.11) assuming $\mathbbm{P}\\{X\in B_{i}\\}>0$ for all $i$.

######  1.3.1.2 Inverse 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
$\varphi\in\mathscr{D}(S)$.

Let $W$ be uniformly distributed on $(0,1]$, so that, for any $a\leqslant
b\in(0,1]$, we have $\mathbbm{P}\\{a<W\leqslant b\\}=b-a$, which is the length
of the interval $(a,b]$.777The probability is the same no matter whether
inequalities are weak or strict. 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 $\varphi$. 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
$\varphi(x)$. More specifically, when $S=\\{x_{1},\ldots,x_{N}\\}$, we take

$I(x_{i}):=(q_{i-1},\,q_{i}]\quad\text{where}\quad
q_{i}:=\varphi(x_{1})+\cdots+\varphi(x_{i})\quad\text{and}\quad q_{0}:=0.$

You can easily confirm that the length of $I(x_{i})$ is $\varphi(x_{i})$ for
all $i$.

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

$\kappa(z):=\sum_{x\in S}x\mathbbm{1}\\{z\in I(x)\\}\qquad(z\in(0,1])$ (1.12)

where $\mathbbm{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.

Prove:

  1. (i)

For all $x\in S$, we have $\kappa(z)=x$ if and only if $z\in I(x)$.

  2. (ii)

The random variable $\kappa(W)$ has distribution $\varphi$.

For the first claim, fix $x\in S$ and $z\in(0,1]$. If $\kappa(z)=x$, then,
since all elements of $S$ are distinct, the definition of $\kappa$ implies
$z\in I(x)$. Conversely, if $z\in I(x)$, then, since all intervals are
disjoint, we have $\kappa(z)=x$.

For the second claim, pick any $x\in S$, and observe that, by the first claim,
the $\kappa(W)=x$ precisely when $W\in I(x)$. The probability of this event is
the length of the interval $I(x)$, which, by construction, is $\varphi(x)$.
Hence $\mathbbm{P}\\{\kappa(W)=x\\}=\varphi(x)$ for all $x\in S$ as claimed.

Let $\varphi$, $\kappa$ and $W$ be as defined above. Prove that
$\mathbbm{E}\mathbbm{1}\\{\kappa(W)=j\\}=\varphi(j)$ holds for all $j\in[n]$.
Fix $j\in[n]$. Observe that $Y:=\mathbbm{1}\\{\kappa(W)=j\\}$ is Bernoulli
random variable. The expectation of such a $Y$ equals $\mathbbm{P}\\{Y=1\\}$.
As $\kappa(W)\stackrel{{\scriptstyle d}}{{=}}\varphi$, this is $\varphi(j)$.

Using Julia or another language of your choice, implement the inverse
transform sampling procedure described above when $S=\\{1,2,3\\}$ and
$\varphi=(0.2,0.1,0.7)$. Generate $1,000,000$ (quasi) independent draws
$(X_{i})$ from $\varphi$ and confirm that
$(1/n)\sum_{i=1}^{n}\mathbbm{1}\\{X_{i}=j\\}\approx\varphi(j)$ for
$j\in\\{1,2,3\\}$.

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

$\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{X_{i}=j\\}\to\mathbbm{E}\mathbbm{1}\\{X_{i}=j\\}$

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

Suppose that, on a computer, you can generate only uniform random variables on
$(0,1]$, and you wish to simulate a flip of a biased coin with heads
probability $\delta\in(0,1)$. Propose a method.

Draw $U$ uniformly on $(0,1]$ and set the coin to heads if $U\leqslant\delta$.
The probability of this outcome is $\mathbbm{P}\\{U\leqslant\delta\\}=\delta$.

Suppose that, on a computer, you are able to sample from distributions
$\varphi$ and $\psi$ defined on some set $S$. The set $S$ can be discrete or
continuous and, in the latter case, the distributions are understood as
densities. Propose a method to sample on a computer from the convex
combination $f(s)=\delta\varphi(s)+(1-\delta)\psi(s)$, where $\delta\in(0,1)$.

For the solution we assume that $S$ is finite, although the argument can
easily be extended to densities. On the computer, we flip a biased coin
$B\in\\{0,1\\}$ with $\mathbbm{P}\\{B=0\\}=\delta$ and then

  1. (i)

draw $Y$ from $\varphi$ if $B=0$, or

  2. (ii)

draw $Y$ from $\psi$ if $B=1$.

With this set up, by the law of total probability,

$\mathbbm{P}\\{Y=s\\}=\mathbbm{P}\\{Y=s\,|\,B=0\\}\mathbbm{P}\\{B=0\\}+\mathbbm{P}\\{Y=s\,|\,B=1\\}\mathbbm{P}\\{B=1\\}=\delta\varphi(s)+(1-\delta)\psi(s).$

In other words, $Y\stackrel{{\scriptstyle d}}{{=}}f$.

######  1.3.1.3 Stochastic Matrices

A matrix $P=(p_{ij})\in\mathbbm{M}^{n\times n}$ is called a stochastic matrix
if

$P\geqslant 0\quad\text{and}\quad P\mathbbm{1}=\mathbbm{1},\text{ where
}\mathbbm{1}\in\mathbbm{R}^{n}\text{ is a column vector of ones}.$

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.

Let $P,Q$ be $n\times n$ stochastic matrices. Prove the following facts.

  1. (i)

$PQ$ is also stochastic.

  2. (ii)

$r(P)=1$.

  3. (iii)

There exists a row vector $\psi\in\mathbbm{R}^{n}_{+}$ such that
$\psi\mathbbm{1}=1$ and $\psi P=\psi$.

Let $P$ and $Q$ be as stated. Evidently $PQ\geqslant 0$. Moreover,
$PQ\mathbbm{1}=P\mathbbm{1}=\mathbbm{1}$, so $PQ$ is stochastic. That $r(P)=1$
follows directly from Lemma 1.2.7. By the Perron–Frobenius theorem, there
exists a nonzero, nonnegative row vector $\varphi$ satisfying $\varphi
P=\varphi$. Rescaling $\varphi$ to $\varphi/(\varphi\mathbbm{1})$ gives the
desired vector $\psi$.

The vector $\psi$ in part (iii) of Exercise 1.3.1.3 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.888Stationary distributions
of stochastic matrices were intensively studied by many mathematicians well
over a century before Larry Page and Sergey Brin patented the PageRank
algorithm, so it seems unfair to allow them to appropriate the name.
Stationary distributions play a key role in the theory of Markov chains, to be
treated in §4.1. Ranking methods are discussed again in §1.4.3. PageRank is
treated in more detail in §4.2.3.3.

#####  1.3.2 Power Laws

Next we discuss distributions on the (non-discrete) sets $\mathbbm{R}$ and
$\mathbbm{R}_{+}$. 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

$F(t):=\mathbbm{P}\\{X\leqslant t\\}\qquad(t\in\mathbbm{R})$

is called the cumulative distribution function (cdf) of $X$. The counter cdf
(ccdf) of $X$ is the function $G(t):=\mathbbm{P}\\{X>t\\}=1-F(t)$.

A useful property that holds for any nonnegative random variable $X$ and
$p\in\mathbbm{R}_{+}$ is the identity

$\mathbbm{E}\,X^{p}=\int_{0}^{\infty}pt^{p-1}\mathbbm{P}\\{X>t\\}\mathop{}\\!\mathrm{d}t.$
(1.13)

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

######  1.3.2.1 Heavy Tails

Recall that a random variable $X$ on $\mathbbm{R}$ is said to be normally
distributed with mean $\mu$ and variance $\sigma^{2}$, and we write
$X\stackrel{{\scriptstyle d}}{{=}}N(\mu,\sigma^{2})$, if $X$ has density

$\varphi(t):=\sqrt{\frac{1}{2\pi\sigma^{2}}}\exp\left(\frac{-(t-\mu)^{2}}{2\sigma^{2}}\right)\qquad(t\in\mathbbm{R}).$

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

A random variable $X$ on $\mathbbm{R}_{+}$ is called exponentially distributed
and we write $X\stackrel{{\scriptstyle d}}{{=}}\operatorname{Exp}(\lambda)$
if, for some $\lambda>0$, $X$ has density

$p(t)=\lambda\mathrm{e}^{-\lambda t}\qquad(t\geqslant 0).$

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.

Figure 1.5:  Independent draws from Student’s t- and normal distributions

Formally, a random variable $X$ on $\mathbbm{R}$ is called light-tailed if its
moment generating function

$m(t):=\mathbbm{E}\mathrm{e}^{tX}\qquad(t\geqslant 0)$ (1.14)

is finite for at least one $t>0$. Otherwise $X$ is called heavy-
tailed.999Terminology on heavy tails varies across the literature but our
choice is increasingly standard. See, for example, Foss et al., (2011) or Nair
et al., (2021).

######  Example 1.3.1.

If $X\stackrel{{\scriptstyle d}}{{=}}N(\mu,\sigma^{2})$, the the moment
generating function of $X$ is known to be

$m(t)=\exp\left(\mu t+\frac{t^{2}\sigma^{2}}{2}\right)\qquad(t\geqslant 0).$

Hence $X$ is light tailed.

######  Example 1.3.2.

A random variable $X$ on $(0,\infty)$ is said to have the lognormal density
and we write $X\stackrel{{\scriptstyle d}}{{=}}LN(\mu,\sigma^{2})$ if $\ln
X\stackrel{{\scriptstyle d}}{{=}}N(\mu,\sigma^{2})$. The mean and variance of
this distribution are, respectively,

$\mathbbm{E}\,X=\exp(\mu+\sigma^{2}/2)\quad\text{and}\quad\operatorname{Var}\,X=(\exp(\sigma^{2})-1)\exp(2\mu+\sigma^{2}).$

The moment generating function $m(t)$ is known to be infinite for all $t>0$,
so any lognormally distributed random variable is heavy-tailed.

For any random variable $X$ and any $r\geqslant 0$, the (possibly infinite)
expectation $\mathbbm{E}|X|^{r}$ called the $r$-th moment of $X$.

######  Lemma 1.3.1.

Let $X$ be a random variable on $\mathbbm{R}_{+}$. If $X$ is light-tailed,
then all of its moments are finite.

###### Proof.

Pick any $r>0$. We will show that $\mathbbm{E}X^{r}<\infty$. Since $X$ is
light-tailed, there exists a $t>0$ such that
$m(t)=\mathbbm{E}\exp(tX)<\infty$. For a sufficiently large constant $\bar{x}$
we have $\exp(tx)\geqslant x^{r}$ whenever $x\geqslant\bar{x}$. As a
consequence, with $F$ as the distribution of $X$, we have

$\mathbbm{E}X^{r}=\int_{0}^{\bar{x}}x^{r}F(\mathop{}\\!\mathrm{d}x)+\int_{\bar{x}}^{\infty}x^{r}F(\mathop{}\\!\mathrm{d}x)\leqslant\bar{x}^{r}+m(t)<\infty.\qed$

Prove that the lognormal distribution has finite moments of every order.

Fix $p>0$ and let $X$ be $LN(\mu,\sigma^{2})$. We have

$\mathbbm{E}|X|^{p}=\mathbbm{E}X^{p}=\mathbbm{E}\exp(p\mu+p\sigma
Z)\quad\text{ for }Z\stackrel{{\scriptstyle d}}{{=}}N(0,1).$

Since $p\mu+p\sigma Z\stackrel{{\scriptstyle d}}{{=}}N(p\mu,p^{2}\sigma^{2})$,
we can apply the formula for the mean of a lognormal distribution to obtain
$m_{p}=\exp(p\mu+(p\sigma)^{2}/2)<\infty$.

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

######  1.3.2.2 Pareto 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

$\lim_{t\to\infty}t^{\alpha}\,\mathbbm{P}\\{X>t\\}=c.$ (1.15)

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

$G(t)\approx ct^{-\alpha}\text{ for large }t.$ (1.16)

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

######  Example 1.3.3.

A random variable $X$ on $\mathbbm{R}_{+}$ is said to have a Pareto
distribution with parameters $\bar{x},\alpha>0$ if its ccdf obeys

$G(t)=\begin{cases}1&\text{ if }t<\bar{x}\\\
\left(\bar{x}/t\right)^{\alpha}&\text{ if }t\geqslant\bar{x}\end{cases}$
(1.17)

It should be clear that such an $X$ has a Pareto tail with tail index
$\alpha$.

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.

Show that, if $X$ has a Pareto tail with tail index $\alpha$, then
$\mathbbm{E}[X^{r}]=\infty$ for all $r\geqslant\alpha$. [Hint: Use (1.13).]

Let $X$ have a Pareto tail with tail index $\alpha$ and let $G$ be its ccdf.
Fix $r\geqslant\alpha$. Under the Pareto tail assumption, we can take positive
constants $b$ and $\bar{x}$ such that $G(t)\geqslant bt^{-\alpha}$ whenever
$t\geqslant\bar{x}$. Using (1.13) we have

$\mathbbm{E}X^{r}=r\int_{0}^{\infty}t^{r-1}G(t)\mathop{}\\!\mathrm{d}t\geqslant
r\int_{0}^{\bar{x}}t^{r-1}G(t)\mathop{}\\!\mathrm{d}t+r\int_{\bar{x}}^{\infty}t^{r-1}bt^{-\alpha}\mathop{}\\!\mathrm{d}t.$

But $\int_{\bar{x}}^{\infty}t^{r-\alpha-1}\mathop{}\\!\mathrm{d}t=\infty$
whenever $r-\alpha-1\geqslant-1$. Since $r\geqslant\alpha$, we have
$\mathbbm{E}X^{r}=\infty$.

From Exercise 1.3.2.2 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.15) is very specific. Despite this, it turns out that many heavy-
tailed distributions encountered in the study of networks are, in fact,
Pareto-tailed.

Prove: If $X\stackrel{{\scriptstyle d}}{{=}}\operatorname{Exp}(\lambda)$ for
some $\lambda>0$, then $X$ does not obey a power law.

Fix $\lambda>0$ and suppose $X\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Exp}(\lambda)$. A simple integration exercise shows that
$\mathbbm{P}\\{X>t\\}=\mathrm{e}^{-\lambda t}$. Now fix $\alpha>0$. Since
$\lim_{t\to\infty}t^{\alpha}\mathrm{e}^{-\lambda t}=0$, the random variable
$X$ does not obey a power law.

######  1.3.2.3 Empirical 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.

Figure 1.6:  ccdf plots for the Pareto and exponential distributions

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.

Figure 1.7:  Empirical ccdf plots for largest firms (Forbes)

######  1.3.2.4 Discrete 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)=ct^{-\gamma}$ with $c:=\alpha\bar{x}^{\alpha}$ and
$\gamma:=\alpha+1$. The next exercise extends this idea.

Let $X$ be a random variable with density $p$ on $\mathbbm{R}_{+}$. Suppose
that, for some constants $c>0$, $\gamma>1$ and $\bar{x}\in\mathbbm{R}_{+}$, we
have

$p(t)=ct^{-\gamma}\quad\text{whenever}\quad t\geqslant\bar{x}.$ (1.18)

Prove that $X$ is Pareto-tailed with tail index $\alpha:=\gamma-1$.

Let $p$ and the constants $\gamma,c>0$ and $\bar{x}\in\mathbbm{R}_{+}$ be as
described in the exercise. Pick any $t\geqslant\bar{x}$. By the usual rules of
integration,

$\mathbbm{P}\\{X>t\\}=c\int_{t}^{\infty}u^{-\gamma}\mathop{}\\!\mathrm{d}u=-\frac{c}{1-\gamma}t^{1-\gamma}.$

With $\alpha:=\gamma-1$, we then have
$t^{\alpha}\mathbbm{P}\\{X>t\\}=c/\alpha$, and $X$ is Pareto-tailed with tail
index $\alpha$.

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

$f(k)=ck^{-\gamma}$ (1.19)

for large $k$. In the special case where this equality holds for all
$k\in\mathbbm{N}$, and $c$ is chosen so that $\sum_{k\in\mathbbm{N}}f(k)=1$,
we obtain the zeta distribution.101010Obviously the correct value of $c$
depends on $\gamma$, so we can write $c=H(\gamma)$ for some suitable function
$H$. The correct function for this normalization is called the Riemann zeta
function.

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

Figure 1.8:  Zeta and Pareto distributions

####  1.4 Graph 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 and fast-moving introduction to graph theory
suitable for our purposes.111111Graph theory is often regarded as originating
from work by the brilliant Swiss mathematician Leonhard Euler (1707–1783),
including his famous paper on the “Seven Bridges of Königsberg.”

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
loss of 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.1 Unweighted Directed Graphs

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

######  1.4.1.1 Definition and Examples

A directed graph or digraph is a pair $\mathscr{G}=(V,E)$, where

  * •

$V$ is a finite nonempty set called the vertices or nodes of $\mathscr{G}$,
and

  * •

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

Intuitively and visually, $(u,v)$ is understood as an arrow from vertex $u$ to
vertex $v$.

Two graphs are given in Figures 1.9–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.

poormiddle classrich

Figure 1.9:  A digraph of classes

middle classrichpoor

Figure 1.10:  An alternative edge list

For a given edge $(u,v)$, the vertex $u$ is called the tail of the edge, while
$v$ is called the head. Given $u,v\in V$, if there exists an edge in $E$ such
that $u$ is the tail and $v$ is the head, then $u$ is called a direct
predecessor of $v$ and $v$ is called a direct successor of $u$. The set of all
direct predecessors of $v\in V$ will be written as $\mathscr{I}(v)$, while the
set of all $v$’s direct successors will be denoted $\mathscr{O}(v)$.

The in-degree $i_{d}(v)$ of a vertex $v\in V$ counts the number of edges that
point at $v$, so that

$i_{d}(v)=\sum_{u\in V}\mathbbm{1}\\{(u,v)\in E\\}=|\mathscr{I}(v)|.$

The out-degree $o_{d}(v)$ counts the number of edges that leave $v$:

$o_{d}(v)=\sum_{u\in V}\mathbbm{1}\\{(v,u)\in E\\}=|\mathscr{O}(v)|.$

If $i_{d}(v)=0$ and $o_{d}(v)>0$, then $v$ is called a source. If either
$\mathscr{O}(v)=\emptyset$ or $\mathscr{O}(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.2 Digraphs 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 the additional two imports:

⬇

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 $\mathscr{G}_{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 $\mathscr{G}_{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.

Figure 1.11:  Networkx digraph plot

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.3 Communication

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 $\mathscr{G}$ 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 $\mathscr{G}$. 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$, while $(3,2,1)$ is a directed path 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$.

######  Example 1.4.1.

Let $\mathscr{G}=(V,E)$ be a digraph representing a production network, where
elements of $V$ are sectors and $(i,j)\in E$ means that $i$ supplies to $j$.
Then sector $m$ is an upstream supplier of sector $\ell$ whenever $m\to\ell$.

123 Figure 1.12:  Strongly connected components of a digraph (rectangles)

######  Example 1.4.2.

The vertex $\\{\text{poor}\\}$ in the Markov digraph displayed in Figure 1.10
is absorbing, since $\\{\text{middle, rich}\\}$ is not accessible from
$\\{\text{poor}\\}$.

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

Let $(V,E)$ be a directed graph and write $u\sim v$ if $u$ and $v$
communicate. Show that $\sim$ is an equivalence relation (see §6.1.1.2).

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.

######  Example 1.4.3.

Figure 1.12 shows a digraph with strongly connected components $\\{1\\}$ and
$\\{2,3\\}$. The digraph is not strongly connected.

######  Example 1.4.4.

In Figure 1.9, the digraph is strongly connected. In contrast, in Figure 1.10,
rich is not accessible from poor, so the graph is not strongly connected.

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)

\parlist(nx.strongly_connected_components(G))

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

######  1.4.1.4 Aperiodicity

A cycle $(u,v,w,\ldots,u)$ of a directed graph $\mathscr{G}=(V,E)$ is a
directed walk in $\mathscr{G}$ such that (i) the first and last vertices are
equal and (ii) no other vertex is repeated. The graph is called periodic if
there exists a $k>1$ such that $k$ divides the length of every cycle. A graph
that fails to be periodic is called aperiodic.

######  Example 1.4.5.

In Figure 1.13, the cycles are $(a,b,a)$, $(b,a,b)$, $(b,c,b)$, $(c,b,c)$,
$(c,d,c)$ and $(d,c,d)$. Hence the length of every cycle is $2$ and the graph
is periodic.

abcd Figure 1.13:  A periodic digraph

An obvious sufficient condition for aperiodicity is existence of even one
self-loop. The digraphs in Figures 1.9–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 et al., (2002) and Norris, (1998).

######  Lemma 1.4.1.

Let $\mathscr{G}=(V,E)$ be a digraph. If $\mathscr{G}$ is strongly connected,
then $\mathscr{G}$ is aperiodic if and only if, for all $v\in V$, there exists
a $q\in\mathbbm{N}$ such that, for all $k\geqslant q$, there exists a directed
walk of length $k$ from $v$ to $v$.

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.5 Adjacency 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
§1.4.2.

Let $\mathscr{G}=(V,E)$ be a digraph and let $|V|=n$. If we enumerate the
elements of $V$, writing them as $(v_{1},\ldots,v_{n})$, then the $n\times n$
adjacency matrix corresponding to $(V,E)$ is defined by121212Note that, in
some applied fields, the adjacency matrix is transposed: $a_{ij}=1$ if there
is an edge from $j$ to $i$, rather than from $i$ to $j$. We will avoid this
odd and confusing definition (which contradicts both standard graph theory and
standard notational conventions in the study of Markov chains).

$A=(a_{ij})_{1\leqslant i,j\leqslant n}\quad\text{with}\quad
a_{ij}=\mathbbm{1}\\{(v_{i},v_{j})\in E\\}.$ (1.20)

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

$A=\begin{pmatrix}1&0&0\\\ 1&1&1\\\ 1&1&1\end{pmatrix}.$ (1.21)

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\leqslant i,j\leqslant n}$ with binary
entries generates a digraph $\mathscr{G}$ with vertices $V$ and edges $E$
equal to all $(v_{i},v_{j})\in V\times V$ with $a_{ij}=1$. The adjacency
matrix of this graph $(V,E)$ is $A$.

A digraph $(V,E)$ is called undirected if $(u,v)\in E$ implies $(v,u)\in E$.
What property does this imply on the adjacency matrix?

If $(V,E)$ is undirected, then the adjacency matrix is symmetric.

######  Remark 1.4.1.

The idea that a digraph can be undirected, presented in Exercise 1.4.1.5,
seems contradictory. After all, a digraph is a _directed_ graph. Another way
to introduce undirected graphs is to define them as a vertex-edge pair
$(V,E)$, where each edge $\\{u,v\\}\in E$ is an unordered pair, rather than an
ordered pair $(u,v)$. However, the definition in Exercise 1.4.1.5 is
essentially equivalent and more convenient for our purposes, since we mainly
study directed graphs.

Like Networkx, the QuantEcon Python library quantecon supplies a graph object
that implements certain graph-theoretic algorithms. The set of available
algorithms is more limited but each one is faster, accelerated by just-in-time
compilation. In the case of QuantEcon’s DiGraph object, an instance is created
via the adjacency matrix. For example, to construct a digraph corresponding to
Figure 1.10 we use the corresponding adjacency matrix (1.21), as follows:

⬇

import quantecon as qe

import numpy as np

\parA = ((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.2 Weighted 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.131313Data for the figure
was obtained from the BIS consolidated banking statistics, for Q4 of 2019. Our
calculations used the immediate counterparty basis for financial claims of
domestic and foreign banks, which calculates the sum of cross-border claims
and local claims of foreign affiliates in both foreign and local currency. The
foreign claim of a node to itself is set to zero. The country codes are given
in Table 1.1.

Figure 1.14:  International private credit flows by country AU | Australia | DE | Germany | CL | Chile | ES | Spain
---|---|---|---|---|---|---|---
PT | Portugal | FR | France | TR | Turkey | GB | United Kingdom
US | United States | IE | Ireland | AT | Austria | IT | Italy
BE | Belgium | JP | Japan | SW | Switzerland | SE | Sweden
Table 1.1:  Codes for the 16-country financial network

In this network, an edge $(u,v)$ exists for almost every choice of $u$ and $v$
(i.e., almost every country in the network).141414In fact arrows representing
foreign claims less than US$10 million are cut from Figure 1.14, so the
network is even denser than it appears. 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.1 Definitions

A weighted digraph $\mathscr{G}$ 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.

######  Remark 1.4.2.

Weights are traditionally regarded as nonnegative. In this text we insist that
weights are also positive, in the sense that $w(u,v)>0$ for all $(u,v)\in E$.
The reason is that the intuitive notion of zero weight is understood, here and
below, as absence of a connection. In other words, if $(u,v)$ has “zero
weight,” then $(u,v)$ is not in $E$, so $w$ is not defined on $(u,v)$.

######  Example 1.4.6.

As suggested by the discussion above, the graph shown in Figure 1.14 can be
viewed as a weighted digraph. Vertices are countries of origin and an edge
exists between country $u$ and country $v$ when private banks in $u$ lend
nonzero quantities to banks in $v$. The weight assigned to edge $(u,v)$ gives
total loans from $u$ to $v$ as measured according to the discussion of Figure
1.14.

######  Example 1.4.7.

Figure 1.15 shows a weighted digraph, with arrows representing edges of the
induced digraph (compare with the unweighted digraph in Figure 1.9). The
numbers next to the edges are the weights. In this case, you can think of the
numbers on the arrows as transition probabilities for a household over, say,
one year. For example, a rich household has a 10% chance of becoming poor.

poormiddle classrich$0.1$$0.4$$0.1$$0.2$$0.1$$0.9$$0.4$$0.8$

Figure 1.15:  A weighted digraph

The definitions of accessibility, communication, periodicity and connectedness
extend to any weighted digraph $\mathscr{G}=(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.2 Adjacency Matrices of Weighted Digraphs

In §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

$A=(a_{ij})_{1\leqslant i,j\leqslant n}\quad\text{with}\quad
a_{ij}=\begin{cases}w(v_{i},v_{j})&\text{ if }(v_{i},v_{j})\in E\\\ 0&\text{
otherwise}.\end{cases}$

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

######  Example 1.4.8.

With $\\{$poor, middle, rich$\\}$ mapped to $(1,2,3)$, the adjacency matrix
corresponding to the weighted digraph in Figure 1.15 is

$A=\begin{pmatrix}0.9&0.1&0\\\ 0.4&0.4&0.2\\\ 0.1&0.1&0.8\end{pmatrix}.$
(1.22)

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.

######  Example 1.4.9.

The digraph in Figure 1.16 can be interpreted as a stylized version of a
financial network, with vertices as banks and edges showing flow of funds,
similar to Figure 1.14 on page 1.14. For example, we see that bank 2 extends a
loan of size 200 to bank 3. The corresponding adjacency matrix is

$A=\begin{pmatrix}0&100&0&0&0\\\ 50&0&200&0&0\\\ 0&0&0&100&0\\\
0&500&0&0&50\\\ 150&0&250&300&0\end{pmatrix}.$ (1.23)

The transposition is

$A^{\top}=\begin{pmatrix}0&50&0&0&150\\\ 100&0&0&500&0\\\ 0&200&0&0&250\\\
0&0&100&0&300\\\ 0&0&0&50&0\end{pmatrix}.\vspace{0.3em}$ (1.24)

The corresponding network is visualized in Figure 1.17. This figure shows the
network of liabilities after the loans have been granted. Both of these
networks (original and transpose) are useful for analysis of financial markets
(see, e.g., Chapter 5).

12345$100$$50$$200$$100$$500$$250$$300$$50$$150$ Figure 1.16:  A network of
credit flows across institutions
12345$100$$50$$200$$100$$500$$250$$300$$50$$150$ Figure 1.17:  The transpose:
a network of liabilities

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 $[n]$. The weighted digraph $\mathscr{G}=(V,E,w)$ in
question is formed by setting

$V=[n],\quad E=\\{(i,j)\in V\times V:a_{ij}>0\\}\quad\text{and}\quad
w(i,j)=a_{ij}\text{ for all }(i,j)\in E.$

We call $\mathscr{G}$ the weighted digraph induced by $A$.

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

Let $A=(a_{ij})$ be a nonnegative $n\times n$ matrix and let
$\mathscr{G}=([n],E,w)$ and $\mathscr{G}^{\prime}=([n],E^{\prime},w^{\prime})$
be the weighted digraphs induced by $A$ and $A^{\top}$, respectively. Show
that

  1. (i)

$(j,k)\in E^{\prime}$ if and only if $(k,j)\in E$.

  2. (ii)

$j\to k$ in $\mathscr{G}^{\prime}$ if and only if $k\to j$ in $\mathscr{G}$.

Let $A^{\top}=(a^{\prime}_{ij})$, so that $a^{\prime}_{ij}=a_{ji}$ for each
$i,j$. By definition, we have

$(j,k)\in E^{\prime}\;\iff\;a^{\prime}_{jk}>0\;\iff\;a_{kj}>0\;\iff\;(k,j)\in
E,$

which proves (i). Regarding (ii), to say that $k$ is accessible from $j$ in
$\mathscr{G}^{\prime}$ means that we can find vertices $i_{1},\ldots,i_{m}$
that form a directed path from $j$ to $k$ under $\mathscr{G}^{\prime}$, in the
sense that such that $i_{1}=j$, $i_{m}=k$, and each successive pair
$(i_{\ell},i_{\ell+1})$ is in $E^{\prime}$. But then, by (i),
$i_{m},\ldots,i_{1}$ provides a directed path from $k$ to $j$ under
$\mathscr{G}$, since and each successive pair $(i_{\ell+1},i_{\ell})$ is in
$E$.

######  1.4.2.3 Application: Quadratic Network Games

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

$u_{k}(x):=-\frac{1}{2}x_{k}^{2}+\alpha x^{\top}Ax+x_{k}\varepsilon_{k}.$
(1.25)

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
$\varepsilon=(\varepsilon_{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\not=k$ when maximizing
(1.25).

In this context, $A$ is understood as the adjacency matrix of a graph with
vertices $V=[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 $[n]\times[n]$ with $a_{ij}>0$. The weights identify some
form of relationship between the agents, such as influence or friendship.

A Nash equilibrium for the quadratic network game is a vector
$x^{*}\in\mathbbm{R}^{n}$ such that, for all $i\in[n]$, the choice $x_{i}^{*}$
of agent $i$ maximizes (1.25) taking $x_{j}^{*}$ as given for all $j\not=i$.
Show that, whenever $r(A)<1/\alpha$, a unique Nash equilibrium $x^{*}$ exists
in $\mathbbm{R}^{n}$ and, moreover, $x^{*}:=(I-\alpha A)^{-1}\varepsilon$.

Recalling that $\partial/(\partial x_{k})x^{\top}Ax=(x^{\top}A)_{k}$, the
first order condition corresponding to (1.25), taking the actions of other
players as given, is

$x_{k}=\alpha(x^{\top}A)_{k}+\varepsilon_{k}\qquad(k\in[n]).$

Concatenating into a row vector and then taking the transpose yields $x=\alpha
Ax+\varepsilon$, where we used the fact that $A$ is symmetric. Since $r(\alpha
A)=\alpha r(A)$, the condition $r(A)<1/\alpha$ implies that $r(\alpha A)<1$,
so, by the Neumann series lemma, the unique solution is $x^{*}=(I-\alpha
A)^{-1}\varepsilon$.

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

######  1.4.2.4 Properties

In this section, we examine some of the fundamental properties of and
relationships among digraphs, weight functions and adjacency matrices.
Throughout this section, the vertex set $V$ of any graph we examine will be
set to $[n]$. This costs no loss of generality, since, in this text, the
vertex set of a digraph is always finite and nonempty.

Also, while we refer to weighted digraphs for their additional generality, the
results below connecting adjacency matrices and digraphs are valid for
unweighted digraphs. Indeed, an unweighted digraph $\mathscr{G}=(V,E)$ can be
mapped to a weighted digraph by introducing a weight function that maps each
element of $E$ to unity. The resulting adjacency matrix agrees with our
original definition for unweighted digraphs in (1.20).

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^{s+t}_{ij}=\sum_{\ell=1}^{n}a^{s}_{i\ell}\,a^{t}_{\ell
j}\qquad(i,j\in[n],\;\;s,t\in\mathbbm{N}).$ (1.26)

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

######  Proposition 1.4.2.

Let $\mathscr{G}$ be a weighted digraph with adjacency matrix $A$. For
distinct vertices $i,j\in[n]$ and $k\in\mathbbm{N}$, we have

$a^{k}_{ij}>0\;\iff\;\text{ there exists a directed walk of length $k$ from
$i$ to $j$}.$

###### Proof.

($\Leftarrow$ ). The statement is true by definition when $k=1$. Suppose in
addition that $\Leftarrow$ holds at $k-1$, and suppose there exists a directed
walk $(i,\ell,m,\ldots,n,j)$ of length $k$ from $i$ to $j$. By the induction
hypothesis we have $a^{k-1}_{in}>0$. Moreover, $(n,j)$ is part of a directed
walk, so $a_{nj}>0$. Applying (1.26) now gives $a^{k}_{ij}>0$.

($\Rightarrow$). Left as an exercise (just use the same logic). ∎

######  Example 1.4.10.

In §4.1 we show that if elements of $A$ represent one-step transition
probabilities across states, then elements of $A^{t}$, the $t$-th power of
$A$, provide $t$-step transition probabilities. In Markov process theory,
(1.26) is called the _Chapman–Kolmogorov equation_.

In this context, the next result is fundamental.

######  Theorem 1.4.3.

Let $\mathscr{G}$ be a weighted digraph. The following statements are
equivalent:

  1. (i)

$\mathscr{G}$ is strongly connected.

  2. (ii)

The adjacency matrix generated by $\mathscr{G}$ is irreducible.

###### Proof.

Let $\mathscr{G}$ be a weighted digraph with adjacency matrix $A$. By
Proposition 1.4.2, strong connectedness of $\mathscr{G}$ is equivalent to the
statement that, for each $i,j\in V$, we can find a $k\geqslant 0$ such that
$a^{k}_{ij}>0$. (If $i=j$ then set $k=0$.) This, in turn, is equivalent to
$\sum_{m=0}^{\infty}A^{m}\gg 0$, which is irreducibility of $A$. ∎

######  Example 1.4.11.

Strong connectivity fails in the digraph in Figure 1.18, since vertex 4 is a
source. By Theorem 1.4.3, the adjacency matrix must be reducible.

1234$a_{12}$$a_{21}$$a_{23}$$a_{31}$$a_{43}$$a_{11}$ Figure 1.18:  Failure of
strong connectivity

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?

######  Theorem 1.4.4.

For a weighted digraph $\mathscr{G}=(V,E,w)$, the following statements are
equivalent:

  1. (i)

$\mathscr{G}$ is strongly connected and aperiodic.

  2. (ii)

The adjacency matrix generated by $\mathscr{G}$ is primitive.

###### Proof of Theorem 1.4.4.

Throughout the proof we set $V=[n]$. First we show that, if $\mathscr{G}$ is
aperiodic and strongly connected, then, for all $i,j\in V$, there exists a
$q\in\mathbbm{N}$ such that $a^{k}_{ij}>0$ whenever $k\geqslant q$. To this
end, pick any $i,j$ in $V$. Since $\mathscr{G}$ is strongly connected, there
exists an $s\in\mathbbm{N}$ such that $a^{s}_{ij}>0$. Since $\mathscr{G}$ is
aperiodic, we can find an $m\in\mathbbm{N}$ such that $\ell\geqslant m$
implies $a^{\ell}_{jj}>0$. Picking $\ell\geqslant m$ and applying (1.26), we
have

$a^{s+\ell}_{ij}=\sum_{r\in V}a^{s}_{ir}a^{\ell}_{rj}\geqslant
a^{s}_{ij}a^{\ell}_{jj}>0.$

Thus, with $t=s+m$, we have $a^{k}_{ij}>0$ whenever $k\geqslant t$.

((i) $\Rightarrow$ (ii)). By the preceding argument, given any $i,j\in V$,
there exists an $s(i,j)\in\mathbbm{N}$ such that $a^{m}_{ij}>0$ whenever
$m\geqslant s(i,j)$. Setting $k:=\max s(i,j)$ over all $(i,j)$ yields
$A^{k}\gg 0$.

((ii) $\Rightarrow$ (i)). Suppose that $A$ is primitive. Then, for some
$k\in\mathbbm{N}$, we have $A^{k}\gg 0$. Strong connectedness of the digraph
follows directly from Proposition 1.4.2. It remains to check aperiodicity.

Aperiodicity will hold if we can establish that $a^{k+t}_{ii}>0$ for all
$t\geqslant 0$. To show this, it suffices to show that $A^{k+t}\gg 0$ for all
$t\geqslant 0$. Moreover, to prove the latter, we need only show that
$A^{k+1}\gg 0$, since the claim then follows from induction.

To see that $A^{k+1}\gg 0$, observe that, for any given $i,j$, the relation
(1.26) implies

$a^{k+1}_{ij}=\sum_{\ell\in V}a_{i\ell}a^{k}_{\ell
j}\geqslant\bar{a}\sum_{\ell\in V}a_{i\ell}.$

where $\bar{a}:=\min_{\ell\in V}a^{k}_{\ell j}>0$. The proof will be done if
$\sum_{\ell\in V}a_{i\ell}>0$. But this must be true, since otherwise vertex
$i$ is a sink, which contradicts strong connectedness. ∎

######  Example 1.4.12.

In Exercise 1.2.3.1 we worked hard to show that $P_{w}$ is irreducible if and
only if $0<\alpha,\beta\leqslant 1$, using the approach of calculating and
then examining the powers of $P_{w}$ (as shown in (1.2)). However, the result
is trivial when we examine the corresponding digraph in Figure 1.3 and use the
fact that irreducibility is equivalent to strong connectivity. Similarly, the
result in Exercise 1.2.3.1 that $P_{w}$ is primitive if and only if
$0<\alpha,\beta\leqslant 1$ and $\min\\{\alpha,\beta\\}<1$ becomes much easier
to establish if we examine the digraph and use Theorem 1.4.4.

#####  1.4.3 Network 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. Other applications pertain to
economics. Here are some examples:

  * •

In which industry will one dollar of additional demand have the most impact on
overall 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?

  * •

Consider the impact of a negative shock that endangers the solvency of a large
part of the banking sector. In this setting, which institution should the
government rescue, if any?

  * •

In the network games considered briefly in §1.4.2.3, we obtained
$x^{*}=(I-\alpha A)^{-1}\varepsilon$ as the Nash equilibrium. Notice that
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.151515Centrality measures are sometimes called “influence
measures,” particularly in connection with social networks.

######  1.4.3.1 Centrality Measures

Let $G$ be the set of weighted digraphs. A centrality measure is a map $m$
from each $\mathscr{G}=(V,E,w)$ in $G$ to a real-valued vector
$m(\mathscr{G})\in\mathbbm{R}^{|V|}$, where the $i$-th element of
$m(\mathscr{G})$ is interpreted as the centrality (or rank) of vertex $v_{i}$.
In most cases $m(\mathscr{G})$ is nonnegative. In what follows, to simplify
notation, we take $V=[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 fully consistent with Benzi and Klymko, (2015).)

######  1.4.3.2 Authorities vs Hubs

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

hubauthority Figure 1.19:  Hub vs authority

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.3 Degree Centrality

As suggested above, two of of the most elementary measures of “importance” of
a vertex in a given digraph $\mathscr{G}=(V,E)$ are its in-degree and out-
degree. Both of these provide a centrality measure. For example, in-degree
centrality $i(\mathscr{G})$ is the vector $(i_{d}(v))_{v\in V}$. Out-degree
centrality $o(\mathscr{G})$ is defined analogously. If $\mathscr{G}$ is
expressed as a Networkx DiGraph called G (see, e.g., §1.4.1.2), then
$i(\mathscr{G})$ can be calculated via

⬇

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

This method is relatively slow when $\mathscr{G}$ 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.23), to a
binary matrix that corresponds to the adjacency matrix of the same network
viewed as an unweighted graph:

$U=\begin{pmatrix}0&1&0&0&0\\\ 1&0&1&0&0\\\ 0&0&0&1&0\\\ 0&1&0&0&1\\\
1&0&1&1&0\end{pmatrix}$ (1.27)

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

$o(\mathscr{G})=U\mathbbm{1}\quad\text{and}\quad
i(\mathscr{G})=U^{\top}\mathbbm{1},$ (1.28)

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.2.2).

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

$o(\mathscr{G})=A\mathbbm{1}\quad\text{and}\quad
i(\mathscr{G})=A^{\top}\mathbbm{1},$ (1.29)

respectively, by analogy with (1.28). We present some intuition for these
measures in applications below.

Unfortunately, while in- and out-degree measures of centrality are simple to
calculate, they are not always informative. As an example, consider again the
international credit network shown in Figure 1.14. There, an edge exists
between almost every node, so the in- or out-degree based centrality ranking
fails to effectively separate the countries. This can be seen in the out-
degree ranking of countries corresponding to that network in the top left
panel of Figure 1.20, and in the in-degree ranking in the top right.

Figure 1.20:  Centrality measures for the credit network

There are other limitations of degree-based centrality rankings. For example,
suppose web page A has many inbound links, while page B has fewer. Even though
page A dominates in terms of in-degree, it might be less important than web
page B to, say, a potential advertiser, when the links into B are from more
heavily trafficked pages. Thinking about this point suggests that importance
can be recursive: the importance of a given node depends on the importance of
other nodes that link to it. The next set of centrality measures we turn to
has this recursive property.

######  1.4.3.4 Eigenvector Centrality

Let $\mathscr{G}=(V,E,w)$ be a weighted digraph with adjacency matrix $A$.
Recalling that $r(A)$ is the spectral radius of $A$, the hub-based eigenvector
centrality of $\mathscr{G}$ is defined as the $e\in\mathbbm{R}^{n}_{+}$ that
solves

$e=\frac{1}{r(A)}Ae.$ (1.30)

Element-by-element, this is

$e_{i}=\frac{1}{r(A)}\sum_{j\in[n]}a_{ij}e_{j}\qquad\text{for all }i\in[n].$
(1.31)

Note the recursive nature of the definition: the centrality obtained by vertex
$i$ is proportional to a sum of the centrality of all vertices, weighted by
the “rates of flow” from $i$ into these vertices. A vertex $i$ is highly
ranked if (a) there are many edges leaving $i$, (b) these edges have large
weights, and (c) the edges point to other highly ranked vertices.

When we study demand shocks in §2.1.3, we will provide a more concrete
interpretation of eigenvector centrality. We will see that, in production
networks, sectors with high hub-based eigenvector centrality are important
_suppliers_. In particular, they are activated by a wide array of demand
shocks once orders flow backwards through the network.

Show that (1.31) has a unique solution, up to a positive scalar multiple,
whenever $A$ is strongly connected.

When $A$ is strongly connected, the Perron–Frobenius theorem tells us that
$r(A)>0$ and $A$ has a unique (up to a scalar multiple) dominant right
eigenvector satisfying $r(A)e=Ae$. Rearranging gives (1.31).161616While the
dominant eigenvector is only defined up to a positive scaling constant, this
is no reason for concern, since positive scaling has no impact on the ranking.
In most cases, users of this centrality ranking choose the dominant
eigenvector $e$ satisfying $\|e\|=1$.

As the name suggests, hub-based eigenvector centrality is a measure of hub
centrality: vertices are awarded high rankings when they _point to_ important
vertices. The next two exercises help to reinforce this point.

Show that nodes with zero out-degree always have zero hub-based eigenvector
centrality.

To compute eigenvector centrality when the adjacency matrix $A$ is primitive,
we can employ the Perron–Frobenius Theorem, which tells us that
$r(A)^{-m}A^{m}\to e\,\varepsilon^{\top}$ as $m\to\infty$, where $\varepsilon$
and $e$ are the dominant left and right eigenvectors of $A$. This implies that

$r(A)^{-m}A^{m}\mathbbm{1}\to ce\quad\text{where
}c:=\varepsilon^{\top}\mathbbm{1}.$

Thus, evaluating $r(A)^{-m}A^{m}\mathbbm{1}$ at large $m$ returns a scalar
multiple of $e$. The following function uses this approach and then normalizes
the dominant eigenvector so that it sums to unity. The authority option is
explained below and the function spec_rad was defined on page 1.2.1. Executing
import numpy as np is required.

⬇

def eigenvector_centrality(A, m=40, authority=False):

"""

Computes the dominant eigenvector of A. Assumes A is

primitive and uses the power method.

"""

A_temp = A.T if authority else A

n = len(A_temp)

r = spec_rad(A_temp)

e = r**(-m) * (np.linalg.matrix_power(A_temp, m) @ np.ones(n))

return e / np.sum(e)

The package Networkx also provides routines for computing eigenvector
centrality, as does the Julia package Graphs.jl.

Using the code above or another suitable routine, compute the hub-based
eigenvector centrality rankings for the simple digraph in Figure 1.21. You
should obtain $e=(0.4,0.2,0.4,0.0)$. Hence, the source vertex (vertex 1)
obtains equal highest rank and the sink vertex (vertex 4) obtains the lowest
rank.

1234$1$$\frac{1}{2}$$1$$\frac{1}{2}$ Figure 1.21:  A network with a source and
a sink

The middle left panel of Figure 1.20 shows the hub-based eigenvector
centrality ranking for the international credit network shown in Figure 1.14.
Countries that are rated highly according to this rank tend to be important
players in terms of supply of credit. Japan takes the highest rank according
to this measure, although countries with large financial sectors such as Great
Britain and France are not far behind. (The color scheme in Figure 1.14 is
also matched to hub-based eigenvector centrality.)

The authority-based eigenvector centrality of $\mathscr{G}$ is defined as the
$e\in\mathbbm{R}^{n}_{+}$ solving

$e=\frac{1}{r(A)}A^{\top}e.$ (1.32)

The difference between (1.32) and (1.31) is just transposition of $A$.
(Transposes do not affect the spectral radius of a matrix.) Element-by-
element, this is

$e_{j}=\frac{1}{r(A)}\sum_{i\in[n]}a_{ij}e_{i}\qquad\text{for all }j\in[n].$
(1.33)

We see $e_{j}$ will be high if many nodes with high eigenvector authority
rankings link to $j$.

The middle right panel of Figure 1.20 shows the authority-based eigenvector
centrality ranking for the international credit network shown in Figure 1.14.
Highly ranked countries are those that attract large inflows of credit, or
credit inflows from other major players. The US clearly dominates the rankings
as a target of interbank credit.

Assume that $A$ is strongly connected. Show that authority-based eigenvector
centrality is uniquely defined up to a positive scaling constant and equal to
the dominant _left_ eigenvector of $A$.

######  1.4.3.5 Katz Centrality

Eigenvector centrality can be problematic. Although the definition in (1.31)
makes sense when $A$ is strongly connected (so that, by the Perron–Frobenius
theorem, $r(A)>0$), strong connectedness fails in many real world networks. We
will see examples of this in §2.1, for production networks defined by input-
output matrices.

In addition, while strong connectedness yields strict positivity of the
dominant eigenvector, many vertices can be assigned a zero ranking when it
fails (see, e.g., Exercise 1.4.3.4). This zero ranking often runs counter to
our intuition when we examine specific networks.

Considerations such as these encourage use of an alternative notion of
centrality for networks called Katz centrality, originally due to Katz,
(1953), which is positive under weaker conditions and uniquely defined up to a
tuning parameter. Fixing $\beta$ in $(0,1/r(A))$, the hub-based Katz
centrality of weighted digraph $\mathscr{G}$ with adjacency matrix $A$, at
parameter $\beta$, is defined as the vector
$\kappa:=\kappa(\beta,A)\in\mathbbm{R}^{n}_{+}$ that solves

$\kappa_{i}=\beta\sum_{j\in[n]}a_{ij}\kappa_{j}+1\qquad\text{for all
}i\in[n].$ (1.34)

The intuition is very similar to that provided for eigenvector centrality:
high centrality is conferred on $i$ when it is linked to by vertices that
themselves have high centrality. The difference between (1.34) and (1.31) is
just in the additive constant $1$.

Show that, under the stated condition $0<\beta<1/r(A)$, hub-based Katz
centrality is always finite and uniquely defined by

$\kappa=(I-\beta A)^{-1}\mathbbm{1}=\sum_{\ell\geqslant 0}(\beta
A)^{\ell}\mathbbm{1},$ (1.35)

where $\mathbbm{1}$ is a column vector of ones.

When $\beta<1/r(A)$ we have $r(\beta A)<1$. Hence, we can express (1.34) as
$\kappa=\mathbbm{1}+\beta A\kappa$ and employ the Theorem 1.2.5 to obtain the
stated result.

We know from the Perron–Frobenius theorem that the eigenvector centrality
measure will be everywhere positive when the digraph is strongly connected. A
condition weaker than strong connectivity is that every vertex has positive
out-degree. Show that the Katz measure of centrality is strictly positive on
each vertex under this condition.

The attenuation parameter $\beta$ is used to ensure that $\kappa$ is finite
and uniquely defined under the condition $0<\beta<1/r(A)$. It can be proved
that, when the graph is strongly connected, hub-based (resp., authority-based)
Katz centrality converges to the hub-based (resp., authority-based)
eigenvector centrality as $\beta\uparrow 1/r(A)$.171717See, for example, Benzi
and Klymko, (2015). This is why, in the bottom two panels of Figure 1.20, the
hub-based (resp., authority-based) Katz centrality ranking is seen to be close
to its eigenvector-based counterpart.

When $r(A)<1$, we use $\beta=1$ as the default for Katz centrality
computations.

Compute the hub-based Katz centrality rankings for the simple digraph in
Figure 1.21 when $\beta=1$. You should obtain $\kappa=(5,4,5,1)$. Hence, the
source vertex (vertex 1) obtains equal highest rank and the sink vertex
(vertex 4) obtains the lowest rank.

Analogously, the authority-based Katz centrality of $\mathscr{G}$ is defined
as the $\kappa\in\mathbbm{R}^{n}_{+}$ that solves

$\kappa_{j}=\beta\sum_{i\in[n]}a_{ij}\kappa_{i}+1\qquad\text{for all
}j\in[n].$ (1.36)

Show that, under the restriction $0<\beta<1/r(A)$, the unique solution to
(1.36) is given by

$\kappa=(I-\beta
A^{\top})^{-1}\mathbbm{1}\quad\iff\quad\kappa^{\top}=\mathbbm{1}^{\top}(I-\beta
A)^{-1}.$ (1.37)

(Verify the stated equivalence.)

Compute the authority-based Katz centrality rankings for the digraph in Figure
1.21 when $\beta=1$. You should obtain $\kappa=(1,6,4,4)$. Notice that the
source vertex now has the lowest rank. This is due to the fact that hubs are
devalued relative to authorities.

#####  1.4.4 Scale-Free Networks

What kinds of properties do large, complex networks typically possess? One of
the most striking facts about complex networks is that many exhibit the scale-
free property, which means, loosely speaking, that the number of connections
possessed by each vertex in the network follows a power law. The scale-free
property is remarkable because it holds for a wide variety of networks, from
social networks to citation, sales, financial and production networks, each of
which is generated by different underlying mechanisms. Nonetheless, they share
this specific statistical structure.

We begin this section by defining the degree distribution and then discuss its
properties, including possible power law behavior.

######  1.4.4.1 Empirical Degree Distributions

Let $\mathscr{G}=(V,E)$ be a digraph. Assuming without loss of generality that
$V=[n]$ for some $n\in\mathbbm{N}$, the in-degree distribution of $G$ is the
sequence $(\varphi_{in}(k))_{k=0}^{n}$ defined by

$\varphi_{in}(k)=\frac{\sum_{v\in
V}\mathbbm{1}\\{i_{d}(v)=k\\}}{n}\qquad(k=0,\ldots,n),$ (1.38)

where $i_{d}(v)$ is the in-degree of vertex $v$. In other words, the in-degree
distribution evaluated at $k$ is the fraction of nodes in the network that
have in-degree $k$. In Python, when $\mathscr{G}$ is expressed as a Networkx
DiGraph called G and

    import numpy as np} has been executed, the in-degree
    distribution can be calculated via
    %
    \begin

mintedpython def in_degree_dist(G): n = G.number_of_nodes() iG =
np.array([G.in_degree(v) for v in G.nodes()]) phi = [np.mean(iG == k) for k in
range(n+1)] return phi The out-degree distribution is defined analogously,
replacing $i_{d}$ with $o_{d}$ in (1.38), and denoted by
$(\varphi_{out}(k))_{k=0}^{n}$. Recall that a digraph $\mathscr{G}=(V,E)$ is
called undirected if $(u,v)\in E$ implies $(v,u)\in E$. If $\mathscr{G}$ is
undirected, then $i_{d}(v)=o_{d}(v)$ for all $v\in V$. In this case we usually
write $\varphi$ instead of $\varphi_{in}$ or $\varphi_{out}$ and refer simply
to the degree-distribution of the digraph. A scale-free network is a network
whose degree distribution obeys a power law, in the sense that there exist
positive constants $c$ and $\gamma$ with

$\varphi(k)\approx ck^{-\gamma}\quad\text{for large }k.$ (1.39)

Here $\varphi(k)$ can refer to in-degree or the out-degree (or both),
depending on our interest. In view of the discussion in §1.3.2.4, this can be
identified with the idea that the degree distribution is Pareto-tailed with
tail index $\alpha=\gamma-1$. Although we omit formal tests, the degree
distribution for the commercial aircraft international trade network shown in
Figure 1.2 on page 1.2 is approximately scale-free. Figure 1.22 illustrates
this by plotting the degree distribution alongside $f(x)=cx^{-\gamma}$ with
$c=0.2$ and $\gamma=1.1$. (In this calculation of the degree distribution,
performed by the Networkx function degree_histogram, directions are ignored
and the network is treated as an undirected graph.)

Figure 1.22:  Degree distribution for international aircraft trade

Attention was drawn to the scale-free nature of many networks by Barabási and
Albert, (1999). They found, for example, that the in-degree and out-degree
distributions for internet pages connected by hyperlinks both follow power
laws. In subsequent years, many networks have been found to have the scale-
free property, up to a first approximation, including networks of followers on
Twitter (Pearce,, 2017; Punel and Ermagun,, 2018), other social networks
(Rybski et al.,, 2009) and academic collaboration networks (e.g., papers plus
citations). Within economics and finance, Carvalho, (2014) shows that the
weighted out-degree distribution for US input-output data (discussed further
in Chapter 2) obeys a power law, as does the Katz centrality measure. Carvalho
et al., (2021) document power law tails for the in-degree (suppliers) and out-
degree (customers) distributions in a Japanese network of interacting firms.
Scale-free degree distributions have also been observed in a number of
financial and inter-bank credit networks (Kim et al.,, 2007; Ou et al.,, 2007;
De Masi et al.,, 2011). In many cases, the scale-free property of a given
network has significant implications for economic outcomes and welfare. For
example, a power law in input-output networks often typically indicates
dominance by a small number of very large sectors or firms. This in turn
affects both the dynamism of industry and the likelihood of aggregate
instability caused by firm-level shocks. We explore some of these issues in
Chapter 2.

######  1.4.4.2 Random Graphs

One way to explore the implications of different dynamics for the degree
distribution of graphs is to specify a law for generating graphs randomly and
then examine the degree distribution that results. This methodology leads to
insights on the kinds of mechanisms that can generate scale-free networks. We
begin with one of the most popular and elementary ways of randomly generating
an undirected graph, originally examined by Erdös and Rényi, (1960). The
process to generate a graph $\mathscr{G}=(V,E)$ is

  1. (i)

fix an integer $n\in\mathbbm{N}$ and a $p\in(0,1)$,

  2. (ii)

view $V:=[n]$ as a collection of vertices,

  3. (iii)

let $E=\\{\emptyset\\}$, and

  4. (iv)

for each $(i,j)\in V\times V$ with $i\neq j$, add the undirected edge
$\\{i,j\\}$ to the set of edges $E$ with probability $p$.

In the last step additions are independent—each time, we flip an unbiased iid
coin with head probability $p$ and add the edge if the coin comes up heads.
The Python code below provides a function that can be called to randomly
generate an undirected graph using this procedure. It applies the combinations
function from the itertools library, which, for the call combinations(A, k),
returns a list of all subsets of $A$ of size $k$. For example,

⬇

import itertools

letters = ’a’, ’b’, ’c’

list(itertools.combinations(letters, 2))

returns [(’a’, ’b’), (’a’, ’c’), (’b’, ’c’)]. We use combinations to produce
the set of all possible edges and then add them to the graph with probability
$p$:

⬇

def erdos_renyi_graph(n=100, p=0.5, seed=1234):

"Returns an Erdos-Renyi random graph."

np.random.seed(seed)

edges = itertools.combinations(range(n), 2)

G = nx.Graph()

\parfor e in edges:

if np.random.rand() < p:

G.add_edge(*e)

return G

(The code presented here is a simplified version of functionality provided by
the library Networkx. It is written for clarity rather than efficiency. More
efficient versions can be found both in Networkx and in Julia’s Graphs.jl
library.) The left hand side of Figure 1.23 shows one instance of a graph that
was generated by the erdos_renyi_graph function, with $n=100$ and $p=0.05$.
Lighter colors on a node indicate higher degree (more connections). The right
hand side shows the degree distribution, which exhibits a bell-shaped curve
typical for Erdos–Renyi random graphs. In fact one can show (see, e.g.,
Bollobás, (1999) or Durrett, (2007)) that the degree distribution is binomial,
with

$\varphi(k)=\binom{n-1}{k}p^{k}(1-p)^{n-1-k}\qquad(k=0,\ldots,n-1).$

Figure 1.23:  An instance of an Erdos–Renyi random graph

######  1.4.4.3 Preferential Attachment

Clearly Erdos–Renyi random graphs fail to replicate the heavy right hand tail
of the degree distribution observed in many networks. In response to this,
Barabási and Albert, (1999) proposed a mechanism for randomly generating
graphs that feature the scale-free property. The stochastic mechanism they
proposed is called preferential attachment. In essence, each time a new vertex
is added to an undirected graph, it is attached by edges to $m$ of the
existing vertices, where the probability of vertex $v$ being selected is
proportional to the degree of $v$. Barabási and Albert, (1999) showed that the
resulting degree distribution exhibits a Pareto tail in the limit, as the
number of vertices converges to $+\infty$. A careful proof can be found in
Chapter 4 of Durrett, (2007). Although we omit details of the proof, we can
see the power law emerge in simulations. For example, Figure 1.24 shows a
random graph with 100 nodes generated by Networkx’s barabasi_albert_graph
function. The number of attachments $m$ is set to 5. The simulated degree
distribution on the right hand side of Figure 1.24 already exhibits a long
right tail.

Figure 1.24:  An instance of a preferential attachment random graph

The preferential attachment model is popular not just because it replicates
the scale-free property of many real-world networks, but also because its
mechanism is simple and plausible. For example, in citation networks, we can
imagine that a well-cited paper is more likely to attract additional citations
than a poorly-cited paper. Similar intuition can be applied to an individual
on a social network, where the number of links is measured in terms of the
number of followers.

####  1.5 Chapter Notes

The Perron–Frobenius theorem is due to Oskar Perron (1880–1975) and Ferdinand
Georg Frobenius (1849–1917). The main results were proved by 1912\. As early
as 1915, Dénes König (1884–1944) saw the connection between the
Perron–Frobenius theorem and graph theory, and provided an alternative proof
using bipartite graphs. Some of the history is discussed in Schrijver, (2005).
We have already mentioned the textbooks on economic and social networks by
Jackson, (2010), Easley et al., (2010) and Borgatti et al., (2018), as well as
the handbook by Bramoullé et al., (2016). Jackson, (2014) gives a survey of
the literature. Within the realm of network science, the high level texts by
Newman, (2018), Menczer et al., (2020) and Coscia, (2021) are excellent. One
good text on graphs and graph-theoretic algorithms is Kepner and Gilbert,
(2011). Ballester et al., (2006) provide an interpretation of Katz centrality
(which they call Bonacich centrality) in terms of Nash equilibria of quadratic
games. Du et al., (2015) show how PageRank can be obtained as a competitive
equilibrium of an economic problem. Calvó-Armengol et al., (2009) develop a
model in which the outcomes for agents embedded in a network are proportional
to the Katz centrality. Elliott and Golub, (2019) show that, in a setting
where agents can create nonrival, heterogeneous public goods, an important set
of efficient solutions are characterized by contributions being proportional
to agents’ eigenvector centralities in the network. Kumamoto and Kamihigashi,
(2018) provide a detailed survey of power laws in economics and social
sciences, including a discussion of the preferential attachment model of
Barabási and Albert, (1999). Newman, (2005) is also highly readable. The
textbook of Durrett, (2007) is rigorous, carefully written and contains
interesting motivational background, as well as an extensive citation list for
studies of scale-free networks. It should be clear from the symbol $\approx$
in (1.39) that the definition of scale-free networks is not entirely rigorous.
Moreover, when connecting the definition to observed networks, we cannot
obtain complete clarity by taking a limit, as we did when we defined power
laws in §1.3.2, since the number of vertices is always finite. This
imprecision in the definition has led to heated debate (see, e.g., Holme,
(2019)). Given the preponderance of positive empirical studies, we take the
view that, up to a reasonable degree of approximation, the scale-free property
is remarkably widespread. In §1.4.2.3 we briefly mentioned network games,
social networks and key players. These topics deserve more attention than we
have been able to provide. An excellent overview is given in Zenou, (2016).
Amarasinghe et al., (2020) apply these ideas to problems in economic
development. Valuable related papers include Allouch, (2015), Belhaj et al.,
(2016), Demange, (2017), Belhaj and Deroïan, (2019), Galeotti et al., (2020).
Candogan et al., (2012) study the profit maximization problem for a monopolist
who sells items to participants in a social network. The main idea is that, in
certain settings, the monopolist will find it profitable to offer discounts to
key players in the network. Atalay et al., (2011) argue that in-degrees
observed in US buyer-supplier networks have lighter tails than a power law,
and supply a model that better fits their data.

###  Chapter 2 Production

In this chapter we study production in multisector environments. The basic
framework is input-output analysis, which was initiated by Wassily Leontief
(1905–1999) and popularized in Leontief, (1941). Input-output analysis is
routinely used to organize national accounts and study inter-industry
relationships. In 1973, Leontief received the Nobel Prize in Economic Sciences
for his work on input-output systems. Input-output analysis is currently being
incorporated into modern theories of trade, growth, shock propagation and
aggregate fluctuations in multisector models (§2.4 provides a detailed list of
references). One of the reasons for renewed interest is that the introduction
of concepts from network analysis and graph theory has yielded new insights.
This chapter provides an introduction to the main ideas.

####  2.1 Multisector Models

In this section we introduce the basic input output model, explain the network
interpretation of the model, and connect traditional questions, such as the
relative impact of demand shocks across sectors, to network topology and
network centrality.

#####  2.1.1 Production Networks

We begin with the foundational concepts of input-output tables and how they
relate to production networks. To simplify the exposition, we ignore imports
and exports in what follows. (References for the general case are discussed in
§2.4.)

######  2.1.1.1 Input-Output Analysis

Agencies tasked with gathering national and regional production accounts (such
as the US Bureau of Economic Analysis) compile input-output data based on the
structure set out by Leontief, (1941). Firms are divided across $n$ sectors,
each of which produces a single homogeneous good. These sectors are organized
into an input-output table, a highly simplified example of which is

| sector 1 | sector 2 | sector 3
---|---|---|---
sector 1 | $a_{11}$ | $a_{12}$ | $a_{13}$
sector 2 | $a_{21}$ | $a_{22}$ | $a_{23}$
sector 3 | $a_{31}$ | $a_{32}$ | $a_{33}$

Entries $a_{ij}$ are called the input-output coefficients;

$a_{ij}=\frac{\text{value of sector $j$'s inputs purchased from sector
$i$}}{\text{total sales of sector $j$}}.$

Thus, $a_{ij}$ is large if sector $i$ is an important supplier of intermediate
goods to sector $j$. The sum of the $j$-th column of the table gives the value
of all inputs to sector $j$. The $i$-th row shows how intensively each sector
uses good $i$ as an intermediate good. The production coefficient matrix
$A=(a_{ij})$ induces a weighted digraph $\mathscr{G}=(V,E,w)$, where $V=[n]$
is the list of sectors and

$E:=\\{(i,j)\in V\times V:a_{ij}>0\\}$

is the edge set. The values $a_{ij}$ show backward linkages across sectors.
Given $i\in V$, the set $\mathscr{O}(i)$ of direct successors of $i$ is all
sectors to which $i$ supplies a positive quantity of output. The set
$\mathscr{I}(i)$ is all sectors that supply a positive quantity to $i$. Figure
2.1 illustrates the weighted digraph associated with the 15 sector version of
the input-output tables provided by the Bureau of Economic Analysis for the
year 2019\. The data source is the US Bureau of Economic Analysis’s 2019
Input-Output Accounts Data.111We obtain input expenditures and total sales for
each sector from the Make-Use Tables. The figure was created using Python’s
Networkx library. An arrow from $i$ to $j$ indicates a positive weight
$a_{ij}$. Weights are indicated by the widths of the arrows, which are
proportional to the corresponding input-output coefficients. The sector codes
are provided in Table 2.1. The size of vertices is proportional to their share
of total sales across all sectors. A quick look at Figure 2.1 shows that
manufacturing (ma) is an important supplier for many sectors, including
construction (co) and agriculture (ag). Similarly, the financial sector (fi)
and professional services (pr) supply services to a broad range of sectors. On
the other hand, education (ed) is relatively downstream and only a minor
supplier of intermediate goods to other sectors. The color scheme for the
nodes is by hub-based eigenvector centrality, with hotter colors indicating
higher centrality. Later, in §2.1.3 we will give an interpretation of hub-
based eigenvector centrality for this setting that connects to relative impact
of demand shocks.

Figure 2.1:  Backward linkages for 15 US sectors in 2019 Table 2.1: Sector codes for the 15 good case Label | Sector
---|---
ag | Agriculture, forestry, fishing, and hunting
mi | Mining
ut | Utilities
co | Construction
ma | Manufacturing
wh | Wholesale trade
re | Retail trade
tr | Transportation and warehousing
in | Information
fi | Finance, insurance, real estate, rental, and leasing
pr | Professional and business services
ed | Educational services, health care, and social assistance
ar | Arts, entertainment, accommodation, and food services
ot | Other services, except government
go | Government

######  2.1.1.2 Connectedness

We will gain insights into input-output networks by applying some of the
graph-theoretic notions studied in Chapter 1.4. One elementary property we can
investigate is connectedness. We can imagine that demand and productivity
shocks diffuse more widely through a given production network when the network
is relatively connected. Conversely, the impact of a demand shock occurring
within an absorbing set will be isolated to sectors in that set. The 15 sector
network in Figure 2.1 is strongly connected. Checking this visually is hard,
so instead we use a graph-theoretic algorithm that finds strongly connected
components from QuantEcon’s DiGraph class. (This class is convenient for the
current problem because instances are created directly from the adjacency
matrix.) Examining the attributes of this class when the weights are given by
the 15 sector input-output model confirms its strong connectedness. The same
class can be used to verify that the network is also aperiodic. Hence, the
input-output matrix $A$ is primitive. This fact will be used in computations
below.

######  2.1.1.3 Disaggregation

Figure 2.2 repeats the graphical representation for the more disaggregated 71
sector case. Sector codes are provided in Table 2.2. Input-output coefficients
below $0.01$ were rounded to zero to increase visual clarity. As in the 15
sector case, the size of vertices and edges is proportional to share of sales
and input-output coefficients respectively. Hotter colors indicate higher hub-
based eigenvector centrality (which we link to propagation of demand shocks in
§2.1.3).