assertionAssertion conjectureConjecture definitionDefinition
hypothesisHypothesis remarkRemark noteNote observationObservation
problemProblem questionQuestion algorithmAlgorithm exampleExample
notationNotation 05C40, 05C50, 05C20, 05C81, 94C15. Maseeh Dept. of Math. and
Stat., Portland State Univ., Portland, OR, USA

# Diffusion and consensus on weakly connected directed graphs

J. J. P. Veerman  E. Kummel<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a weakly connected directed graph with asymmetric graph Laplacian
${\cal L}$. Consensus and diffusion are dual dynamical processes defined on
$G$ by $\dot{x}=-{\cal L}x$ for consensus and $\dot{p}=-p{\cal L}$ for
diffusion. We consider both these processes as well their discrete time
analogues. We define a basis of row vectors $\\{\bar{\gamma}_{i}\\}_{i=1}^{k}$
of the left null-space of ${\cal L}$ and a basis of column vectors
$\\{\gamma_{i}\\}_{i=1}^{k}$ of the right null-space of ${\cal L}$ in terms of
the partition of $G$ into strongly connected components. This allows for
complete characterization of the asymptotic behavior of both diffusion and
consensus — discrete and continuous — in terms of these eigenvectors.

As an application of these ideas, we present a treatment of the pagerank
algorithm that is dual to the usual one. We further show that the
_teleporting_ (see below) feature usually included in the algorithm is not
strictly necessary.

Together with [13], this is a complete and self-contained treatment of the
asymptotics of consensus and diffusion on digraphs. Many of the ideas
presented here can be found scattered in the literature, though mostly outside
mainstream mathematics and not always with complete proofs. This paper seeks
to remedy this by providing a compact and accessible survey.

##  1 Introduction

Directed graphs are an important generalization of undirected graphs because
they have wide-ranging applications. Examples include models of the internet
[11] and social networks [12], food webs [28], epidemics [23], chemical
reaction networks [33], databases [4], communication networks [3], and
networks of autonomous agents in control theory [18]; to name but a few. In
each of these examples, the relation defining adjacency between neighboring
vertices is often not symmetric. Such networks are most naturally represented
by directed graphs. Still, in many standard references, directed graphs rate
no more than one section or chapter out of many. A notable exception to this
is [5], but even here, little mention is made of the _algebraic_ theory for
digraphs. One reason for this is perhaps that adjacency matrices (and hence
Laplacians) of undirected graphs are symmetric and thus there is a complete
basis of orthonormal eigenvectors, which is not generally true for digraphs.

One aim of this article is to collect and explain some important results in
algebraic digraph theory in a unified context. We will see that the lack of
symmetry, referred to above, can actually be used to reveal a great deal of
structure in general digraphs that has _no counterpart_ in undirected graphs.
Many of these results are known or published in varied disciplines outside the
mainstream of mathematics, but frequently are only stated in the case of
strongly connected graphs and not always with proofs that apply more
generally.

In considering applications, such as those mentioned in the first paragraph,
we found it a useful heuristic to fix once and for all _the direction of the
edges in the digraph as the direction of the flow of information_. In most
cases, this is a convenient way to determine the (ultimately arbitrary)
direction of the arrows of the graph, and unify the treatment of these
different applications. In our article, the direction of the flow of
information is exemplified by the consensus problem (see below): if $i$’s
opinion is influenced by $j$, then there is an edge from $j$ to $i$. We will
see that a random walk on the same digraph naturally is defined to go in the
_opposite_ direction, i.e. from $i$ to $j$. One of our main conclusions is
that these processes in opposite directions can be considered as _duals_ of
one another.

Finally, we apply some of these insights to the pagerank algorithm most
famously associated with Google founders Brin and Page. The usual treatment of
this algorithm involves a random walk in a graph defined by web links,
together with some random jumps. We give a dual interpretation in terms of how
information added to one page influences the collective network as a whole.

The outline of this article is as follows. In the next section, we give
important definitions and some background relating to our topic. In Section 3,
we describe the structure of the right kernel of the random walk Laplacian
${\cal L}$ of a directed graph $G$ (with or without teleporting). In
particular, we show how it relates to the way strongly connected components of
$G$ are linked. Most of this section is based on [13]. In Section 4, we give
the structure of the left kernel of ${\cal L}$ and similarly relate it to how
the different components of $G$ are linked. Furthermore, we show that the left
kernel encodes the asymptotic behavior of a random walk defined on $G$. In
Section 5, we use both left and right kernels, and show that the asymptotic
behavior of the random walk on the one hand and consensus on the other, are
natural duals. In Section 6, we give the dual interpretation of the classical
pagerank algorithm, and show that the common practice of adding “teleporting”
to so-called “dangling nodes” adds no new information to the ranking order.
Finally, in Section 7, we illustrate our definitions and algorithms in one
(small) graph.

##  2 Definitions and Background

We now give an overview of the most relevant definitions concerning digraphs.

Let $G$ be a directed graph on $V=\\{1,\dots,n\\}$ with (directed) edge-set
$E\subseteq V\times V$. A directed edge $j\rightarrow i$ will be referred to
as $ji$. We also write $j\rightsquigarrow i$ if there exists a directed path
in $G$ from vertex $j$ to vertex $i$. To each (directed) edge $ji\in E$, we
assign a positive weight $w_{ji}>0$. The _adjacency matrix_ $Q$ is the
$n\times n$ matrix whose $ij$ entry equals $w_{ji}>0$ if $ji\in E$ and zero
otherwise.

The notion of “connectedness” in undirected graphs has several natural
extensions to directed graphs. See [5] for more information. A digraph $G$
with vertex set $V$ is _strongly connected_ if for all $i$ and $j$ in $V$,
there is a path $i\rightsquigarrow j$ (and thus also a path $j\rightsquigarrow
i$). Such components are called _strong components_. A much weaker form of
connectedness is the following. $G$ is _weakly connected_ if for all $i$ and
$j$ in $V$, there is an undirected path in G from $i$ to $j$. Equivalently,
$G$ is weakly connected if its underlying undirected graph (all edges replaced
by undirected edges) is connected. There is an intermediate form of
connectedness, called _unilateral connectedness_ in [5]. $G$ is _unilaterally
connected_ if for all $i$ and $j$ in $V$, there is a undirected path
$i\rightsquigarrow j$ or $j\rightsquigarrow i$. A digraph that is not weakly
connected is disconnected. To study its properties, it is sufficient to study
the properties of its weakly connected components. Thus in this article, we
assume without loss of generality that our digraphs are weakly connected, but
not necessarily unilaterally connected. From now on, we will abbreviate
_(weighted) directed graph_ to _graph_ unless misunderstanding is possible.

######  Definition 2.1.

[13] For any vertex $j$, we define the _reachable set_ $R(j)$ of vertex $j$ to
be the set containing $j$ and all vertices $i$ such that $j\rightsquigarrow
i$.

######  Definition 2.2.

[13] A set $R$ of vertices in a graph will be called a _reach_ if it is a
maximal reachable set; in other words, $R$ is a reach if $R=R(i)$ for some $i$
and there is no $j$ such that $R(i)\subsetneq R(j)$. Since our graphs all have
finite vertex sets, such maximal sets exist and are uniquely determined by the
graph. For each reach $R_{i}$ of a graph, we define the _exclusive part_ of
$R_{i}$ to be the set $H_{i}=R_{i}\backslash\cup_{j\neq i}R_{j}$. Likewise, we
define the _common part_ of $R_{i}$ to be the set $C_{i}=R_{i}\backslash
H_{i}$.

Thus, a reach is a maximal unilaterally connected set. A graph will typically
contain more than one reach. Note that, by definition, the pairwise
intersection of two exclusive sets is empty: $H_{i}\cap H_{j}=\emptyset$ if
$i\neq j$. The common sets can, however, intersect. Note further that each
reach $R$ contains at least one vertex $r$ such that its reachable set $R(r)$
equals the entire reach. Such a vertex is called a _root_ of $R$. By
definition, any root must be contained in the exclusive part of its reach.

######  Definition 2.3.

Let $G$ be a digraph. Then each reach $R_{i}$ of $G$ contains a set of roots
$B_{i}$. The set $B_{i}$ is called the _cabal_ of $R_{i}$ and is contained in
$H_{i}$. (A cabal consisting of 1 vertex is usually called a leader [35].)

Dynamical processes on $G$ are most often defined using a version of the
Laplacian operator. In this paper we find it convenient to define these
Laplacians in terms of a normalized adjacency matrix $Q$ obtained by dividing
each row by its sum. This is straightforward, unless $Q$ contains a row
$\\{Q_{ij}\\}_{j=1}^{n}$ that consists of entirely of zeroes. One possible
solution is to replace $Q_{ii}$ with a 1. We will denote the resulting matrix
also by $Q$. Another possibility is to replace each entry of the row with
$1/n$. The resulting matrix will also be called $Q$. This variation is often
called _teleporting_. The reason for that name will be made clear in Section
4. Define the _in-degree_ matrix $D$ is the $n\times n$ diagonal matrix whose
$i$-th diagonal entry equals the sum of the $i$-th row of $Q$. Then, $S\equiv
D^{-1}Q$. If we used “teleporting”, we will denote the resulting matrix by
$S_{t}$. Both $S$ and $S_{t}$ are _row stochastic_ matrices, that is: they are
non-negative and have row sum one. We can now list three commonly used
Laplacians together with their names:

  1. 1.

the _combinatorial Laplacian_ $L=D-Q$;

  2. 2.

the _random walk (rw) Laplacian_ ${\cal L}=I-S$;

  3. 3.

the _rw Laplacian with teleporting_ ${\cal L}=I-S_{t}$.

All these Laplacians share the fact that they can be written as follows.

######  Definition 2.4.

[13] We define the following (non-symmetric) Laplacian matrix:

$M\equiv D-DS\;,$

where $D$ is non-negative on the diagonal and zero elsewhere, and $S$ is a row
stochastic matrix. $M$ has non-negative diagonal entries and non-positive off-
diagonal entries and any row-sum is zero.

There are many other conventions that may give different Laplacians for a
given graph. For example, if $Q$ is _irreducible_ , there is a leading all-
positive eigenvector $r$ with (real) eigenvalue $\lambda$. Let $R$ be the
diagonal matrix whose diagonal entries equal $r_{i}$. Then
$S=\lambda^{-1}R^{-1}QR$ is the _stochasticization_ [8] of $Q$. If $Q$ is
undirected (symmetric), then the _normalized_ adjacency is
$S=D^{-\frac{1}{2}}QD^{-\frac{1}{2}}$. This normalized matrix has the
advantage that it is symmetric if and only if $Q$ is symmetric. More
sophisticated definitions that give symmetric Laplacians for digraphs can be
found in [14] and [15]. We will, however, not pursue these in this article.

The statement that $i$ is in the same strong component as $j$ is an
equivalence relation on the vertices of the graph $G$. Thus the vertices can
be partitioned into strong components. In turn, this generates a partial order
on strong components $S_{i}\subset V$. Namely, $S_{1}<S_{2}$ if $S_{2}$ is
reachable from $S_{1}$. The fact that a partial order can be extended to a
total order implies [5] that the strong components themselves can be ordered
in such a way that the adjacency matrix becomes block triangular, in such a
way that each diagonal block is the adjacency matrix of the subgraph of $G$ by
induced by one of the strong components. Thus, the spectrum of $Q$ in is one-
to-one correspondence with the union of the spectra of the strong components
and gives no information of how the strong components are linked together.
Even though this is not entirely true for the eigenvalues of the various
_Laplacians_ , we take this as a cue to study the _eigenvectors_ of the
Laplacians, in particular those that correspond to the eigenvalue 0. We will
see that the structure of these eigenvectors is intimately related to how the
strong components — and, indeed, the unilateral components or reaches — are
connected to one another.

Next we define two important dynamical processes on digraphs, diffusion and
consensus. we consider them from the start as dual to each other.

######  Definition 2.5.

Let ${\cal L}$ be the rw Laplacian (with or without teleporting).
i) The _consensus problem_ on $G$ is the differential equation $\dot{x}=-{\cal
L}x$.
ii) The _diffusion problem_ on $G$ is the differential equation
$\dot{p}=-p{\cal L}$.
From hereon, $x$ is a column vector and $p$ is a row vector.

If we discretize both these problems with time-steps of size 1, we get (noting
that $-{\cal L}=S-I$)

$\displaystyle\dot{x}=(S-I)x$ $\displaystyle\longrightarrow$ $\displaystyle
x^{(n+1)}=Sx^{(n)}\;,$ $\displaystyle\dot{p}=p(S-I)$
$\displaystyle\longrightarrow$ $\displaystyle p^{(n+1)}=p^{(n)}S\;.$

This inspires our next definition.

######  Definition 2.6.

Let $S=I-{\cal L}$ where ${\cal L}$ is the rw Laplacian (with or without
teleporting). i) The _discrete consensus problem_ on $G$ is the difference
equation $x^{(n+1)}=Sx^{(n)}$.
ii) The _discrete diffusion problem_ or _random walk_ on $G$ is the difference
equation $p^{(n+1)}=p^{(n)}S$.

Note that the second process is also known as a discrete-time finite-state
Markov chain [25].

In the above definition, $S$ can be either the matrix $D^{-1}Q$ or
$D^{-1}Q_{t}$ that we defined earlier. The difference is that in the former
case, if the walker reaches a vertex with in-degree zero, it will stay there
forever, while in the latter case, the walker will be sent to an arbitrary
vertex (with uniform distribution) in the graph. Hence the annotation “with
teleporting” for the corresponding Laplacian. Note that the random walker
moves in the direction _opposite_ the direction of the flow of information.

The (continuous) consensus problem can be characterized by two requirements.
First, we require that ${\bf 1}$, the vector of all ones, is an equilibrium.
Second, if ${\bf 1}_{\\{i\\}}$ is the vector that is 1 on the $i$th vertex and
0 everywhere else, then $-{\cal L}{\bf 1}_{\\{i\\}}$ must be non-negative
except on the $i$th vertex. This requirement indicates that $i$ pulls other
vertices in _its_ direction. It is easy to see that the first requirement is
equivalent to saying that ${\cal L}$ has row sum zero, while the second
indicates that off-diagonal components of ${\cal L}$ are non-positive.

A similar characterization can be given for the diffusion problem. First, we
need this definition.

######  Definition 2.7.

A probability vector or a (discrete) _measure_ on $G$ is a row-vector in
$\mathbb{R}^{V}$ such that for all $i$, $p(i)\geq 0$ and $\sum_{i}\,p(i)=1$.
The _support_ , $\emph{supp}(p)$, of the measure $p$, is the set of vertices
on which $p$ takes a positive value.

The characterization of the diffusion problem is as follows. First, total
probability is conserved, or $\sum_{i}p_{i}=0$. Second, all components except
the $i$th of $-{\bf 1}_{\\{i\\}}^{T}{\cal L}$ are non-negative, because
probability streams from vertex $i$ to other vertices. One immediately sees
that this gives the same requirements on ${\cal L}$. Similar characterizations
can be given for the discrete equivalent of these problems.

Thus the discrete versions of each process can be treated in pretty much the
same way. In the interest of brevity, we will limit the remainder of the
exposition to considering only the discrete diffusion problem and the
continuous consensus problem. The other two problems can be treated in the
same way and with the same conclusions. A more rigorous treatment of the
discrete/continuous distinction is deferred to the appendix.

##  3 The Right Kernel of $D-DS$

In this section, we analyze the right kernel of the Laplacian.

######  Lemma 3.1.

(i): There are _no_ edges from the complement $H_{i}^{c}$ of an exclusive set
to $H_{i}$.
(ii): There are _no_ edges from the complement $B_{i}^{c}$ of a cabal to
$B_{i}$.
(iii): The graph induced by a cabal $B_{i}$ is strongly connected.

######  Proof 3.2.

(i): Suppose that for $j\neq i$, $v\in R_{j}$ and $vu\in E$. Then by the
definition of reach, $u\in R_{j}$. Thus, by the definition of exclusive set,
$u\not\in H_{i}$.
(ii): Suppose $u\in B_{i}$ and $vu\in E$. By the definition of cabal, the
entire reachable from u and therefore from $v$. So $v\in B_{i}$.
(iii): Suppose $v$ and $w$ in $B_{i}$ and there is no path $v\rightsquigarrow
w$ in $B_{i}$. Then $v$ cannot be a root, which is a contradiction.

######  Theorem 3.3.

[13] Suppose $M=D-DS$, where $D$ is a nonnegative $n\times n$ diagonal matrix
and $S$ is (row) stochastic. Suppose $G$ has $k$ reaches, denoted $R_{1}$
through $R_{k}$, where we denote the exclusive and common parts of each
$R_{i}$ by $H_{i}$, $C_{i}$ respectively. Then the eigenvalue 0 has algebraic
and geometric multiplicity $k$ and the kernel of $M$ has a basis $\gamma_{1}$,
$\gamma_{2}$, … $\gamma_{k}$ in $\mathbb{R}^{n}$ whose elements satisfy:
(i) $\gamma_{i}(v)=1$ for $v\in H_{i}$;
(ii) $\gamma_{i}(v)\in(0,1)$ for $v\in C_{i}$;
(iii) $\gamma_{i}(v)=0$ for $v\not\in R_{i}$;
(iv) $\sum_{i}\gamma_{i}={\bf 1}_{n}$ (the all ones vector).

######  Theorem 3.4.

[2], [13] Any nonzero eigenvalue of a Laplacian matrix of the form $D-DS$,
where $D$ is nonnegative diagonal and $S$ is stochastic, has (strictly)
positive real part.

The definitions of reach, cabal, exclusive part, and common part are
illustrated in Section 7. Here we wish to note that the reaches of even a
large graph $G$ are relatively easy to compute by first computing the
condensation digraph $SC(G)$. This is the graph whose vertices are the strong
components $S_{i}$ of $G$ and $S_{i}\rightarrow S_{j}$ if there is an edge
from $S_{i}$ to $S_{j}$. Let $V_{0}$ be the vertices of $SC(G)$ with in-degree
0\. Since $SC(G)$ has no directed cycles, there must be at least one such
vertex. Any such vertex $v$ represents a cabal in $G$ by Lemma 3.1. We can
then use breadth first search from $v$ to find the reach of $v$ in $SC(G)$ and
finally recover a reach in $G$.

Theorem 3.3 also shows that the underlying unweighted graph of $G$ gives a
great deal of information about the basis of the kernel. In particular, it
determines $\gamma_{i}$ on $H_{i}$ and on the complement of $R_{i}$. However,
the exact value of $\gamma_{i}(v)$ if $v$ is a vertex in a common part is only
determined once the weights on the edges are fixed.

##  4 Random Walks on Directed Graphs

In this section, we analyze random walks on $G$ and analyze its invariant
measure in terms of the left kernel of the Laplacian of $G$.

######  Definition 4.1.

The probability vector $p$ is an _invariant probability measure_ (or a
_stationary distribution_) for $T$ if $pS=p$. $K\subseteq V(G)$ is a forward
invariant set under $T$ if $\emph{supp}(p)\subseteq K$ implies
$\emph{supp}(pS)\subseteq K$.

######  Lemma 4.2.

Given a random walk random walk $T$, every exclusive set $H_{i}$ and its cabal
$B_{i}$ are forward invariant sets under $T$.

######  Proof 4.3.

A walker leaving $C_{i}$ means that the graph must have an edge into $C_{i}$.
This contradicts Lemma 3.1. The same holds for $B_{i}$.

######  Theorem 4.4.

Let $G$ be a weighted digraph with Laplacian ${\cal L}$ and $k$ reaches. The
probability that a random walker under $T$ starting at $v$ is absorbed into
the cabal $B_{r}$ equals $\gamma_{r}(v)$ (defined in Theorem 3.3).

######  Proof 4.5.

Let $q(j)$ be the probability that a random walker starting at $j\in V$
reaches $B_{m}$ for some fixed $m$. (Note that $q$ is not a probability
vector.) Then $q:V\rightarrow[0,1]$ is well-defined and is constant in time.
Since, by Lemma 4.2, $B_{m}$ is forward invariant, $q(j)$ is also equal to the
probability that the walker starting at $j$ ends up and stays in $B_{m}$.

The probability $q(j)$ concerns the future (under $T$) of the walker on $j$.
Therefore it is equal to the appropriately weighted average of $q(i)$ of $j$’s
successors under $T$. Thus from Definition 2.6,

$q(j)=\sum_{i}\,\mbox{prob}(j\rightarrow i)q(i)=\sum_{i}\,S_{ji}q(i)\;.$

From this we conclude $q=Sq$, which is equivalent to ${\cal L}q=0$. Thus $q$
is in the kernel of ${\cal L}$, and therefore

$q(j)=\sum_{m}\,\alpha_{m}\gamma_{m}(j)\;.$

By Lemma 4.2, if $j$ is a vertex in $B_{r}$, then $q(j)=1$. Also if $j$ is in
any $B_{m}$ with $m\neq r$, then $q(j)=0$. Since the cabals are disjoint, we
must have that $\alpha_{r}=1$ and $\alpha_{m}=0$ if $m\neq r$.

We remark that it follows from Theorem 3.3(iv) that the probability is one
that a walker will be absorbed in $B_{r}$ for some $r$.

######  Lemma 4.6.

Let $G$ be a digraph that has a reach $R$, consisting of an exclusive part $H$
which contains a cabal $B$, and a common part $C$. Under the random walk $T$
on $G$, there is a unique invariant measure $p$ with support in $R$.
Furthermore, _supp_ $(p)$ equals $B$.

######  Proof 4.7.

Consider a reach $R$ with its cabal $B$ and denote the vertex set $R\backslash
B$ by $Y$ and the vertex set $V\backslash R$ by $Z$. Since directed paths in
$G$ cannot leave the reach $R$, we have $S_{ZB}=S_{ZY}=0$. By Lemma 3.1,
$S_{BY}=S_{BZ}=0$. So

$S=\begin{pmatrix}S_{BB}&{\bf 0}&{\bf 0}\\\ S_{YB}&S_{YY}&S_{YZ}\\\ {\bf
0}&{\bf 0}&S_{ZZ}\end{pmatrix}\;.$

We solve for $p$ in $pS=p$, where $p=(a_{B},b_{Y},c_{Z})$ and assume
$c_{Z}=0$. This gives

$a_{B}S_{BB}+b_{Y}S_{YB}=a_{B}\;,b_{Y}S_{YY}=b_{Y}\;\;{\rm
and}\;\;b_{Y}S_{ZY}+c_{Z}S_{ZZ}=c_{Z}\;.$

The proof of Theorem 2.7 in [13] establishes that the spectral radius of
$S_{YY}$ is strictly less than 1. Thus the middle equation can only be
satisfied if $b_{Y}=0$. Since $B$ is a strong component, $S_{BB}$ is
irreducible. It follows directly from the Perron-Frobenius theorem (see [8,
34]) that the eigenvalue 1 is simple and its associated eigenvector is
strictly positive.

######  Theorem 4.8.

Let $G$ be a graph with Laplacian ${\cal L}=I-S$ with $k$ reaches. Then the
eigenvalue 0 of ${\cal L}$ has algebraic and geometric multiplicity $k$. The
left kernel of ${\cal L}$ has a basis $\bar{\gamma}_{1}$, $\bar{\gamma}_{2}$,
… $\bar{\gamma}_{k}$ in $\mathbb{R}^{n}$ whose elements satisfy:
(i) For all $i\in\\{1,\cdots k\\}$ and all $v\in\\{1,\cdots n\\}$:
$\bar{\gamma}_{i}(v)\geq 0$;
(ii) supp$(\bar{\gamma}_{i})=B_{i}$;
(iii) $\sum_{v}\,\bar{\gamma}_{i}(v)=1$;
(iv) The vectors $\\{\bar{\gamma}_{i}\\}_{i=1}^{k}$ are orthogonal.

######  Proof 4.9.

The first statement (the multiplicity of $0$) is in fact part of Theorem 3.3.
For each reach $R_{i}$, Lemma 4.6 gives an invariant measure
$\bar{\gamma}_{i}$ satisfying (i), (ii), and (iii). Since
$\bar{\gamma}_{i}S=\bar{\gamma}_{i}$, we have that $\bar{\gamma}_{i}$ is a
left null vector of ${\cal L}$. These $k$ vectors are orthogonal, because the
sets $B_{i}$ are mutually disjoint.

######  Corollary 4.10.

Let $G$ be a graph with Laplacian $L=D-DS$ with $k$ reaches. Then the left
kernel of $L$ has a basis $\left\\{\bar{\gamma}_{i}D^{-1}\right\\}_{i=1}^{k}$,
where the $\\{\bar{\gamma}_{i}\\}_{i=1}^{k}$ are as in Theorem 4.8.

######  Proof 4.11.

Construct the basis $\bar{\gamma}_{1}$, $\bar{\gamma}_{2}$, …
$\bar{\gamma}_{k}$ of the left kernel of $I-S$. Then it is easy to see that
the $\bar{\gamma}_{i}D^{-1}$ form a basis of the left kernel of $D-DS$.

##  5 The Left and Right Kernels of ${\cal L}$

We start this section with a general lemma and a definition that will be used
at the end of the section. Subsequently, we establish the dual relationship
between the equilibria of the random walk and those of the consensus problem.
In this context, the duality is very natural. The matrix is multiplied from
the _left_ by probability vectors (measures) and from the right by vectors
whose Laplacian is zero. The latter are also known as _harmonic vectors or
functions_ and have many other applications in graph theory. Two notable
examples focused on undirected graphs are [7] and [10]. The latter reference
also discusses the duality mentioned above in the context of electrical
networks. At the end of the section, we briefly note that the duality is
independent of the discrete or continuous nature of the processes discussed.
This has also been observed by other authors, for example [27] and [31].

######  Lemma 5.1.

Let $A$ be an $n\times n$ matrix. There are bases of (generalized) right
eigenvectors (columns), $\\{\eta_{i}\\}_{i=1}^{n}$, and of (generalized) left
eigenvectors (rows), $\\{\bar{\eta}_{i}\\}_{i=1}^{n}$, such that the matrices:

$\Gamma=\left(\begin{array}[]{cccc}\eta_{1}&\eta_{2}&\cdots&\eta_{n}\end{array}\right)\;\;{\rm
and}\;\;\bar{\Gamma}=\left(\begin{array}[]{c}\bar{\eta}_{1}\\\
\bar{\eta}_{2}\\\ \vdots\\\ \bar{\eta}_{n}\end{array}\right)$

are inverses of one another. We will assume the basis-vectors ordered
according to ascending eigenvalue.

######  Proof 5.2.

This follows directly from the Jordan Decomposition Theorem [21]. Let $J$ be
the Jordan normal form of $A$. Then that theorem tells us that there is an
invertible matrix $\Gamma$ such that $A\Gamma=\Gamma J$ or
$\Gamma^{-1}A=J\Gamma^{-1}$. Right multiply the first equation by the standard
column basis vector ${\bf 1}_{\\{i\\}}$ to show that the $i$th column of
$\Gamma$ is a generalized right eigenvector. Left multiply by ${\bf
1}_{\\{i\\}}^{T}$ to see that the $i$th row of $\Gamma^{-1}$ is a generalized
left eigenvector.

######  Definition 5.3.

Let $G$ have $k$ reaches. Let $\\{\gamma_{i}\\}_{i=1}^{k}$ be the (column)
vectors of Theorem 3.3 and $\\{\bar{\gamma}_{i}\\}_{i=1}^{k}$ the (row)
vectors of Theorem 4.8. Define

$\Gamma^{0}=\left(\begin{array}[]{cccc}\gamma_{1}&\gamma_{2}&\cdots&\gamma_{k}\end{array}\right)\;\;{\rm
and}\;\;\bar{\Gamma}^{0}=\left(\begin{array}[]{c}\bar{\gamma}_{1}\\\
\bar{\gamma}_{2}\\\ \vdots\\\ \bar{\gamma}_{k}\end{array}\right)\;.$

######  Theorem 5.4.

Let $G$ be a graph with random walk laplacian ${\cal L}=I-S$ with $k$ reaches
$\\{R_{i}\\}_{i=1}^{k}$. Let $p^{(0)}$ be an initial measure (at $t=0$). Then

$\lim_{\ell\rightarrow\infty}\frac{1}{\ell}\sum_{i=0}^{\ell-1}\,T_{*}^{i}p^{(0)}=\sum_{m=1}^{k}\,\left(p^{(0)}\gamma_{m}\right)\,\bar{\gamma}_{m}\;.$

Note that $(p^{(0)}\gamma_{m})$ is a scalar. (Recall that $p$ is a row vector
and $\gamma$ is a column vector.)

######  Proof 5.5.

Given an initial measure $p^{(0)}$, then Theorem 4.4 implies that
$\alpha_{r}\equiv p^{(0)}\gamma_{r}$ is the probability to be absorbed in the
cabal $B_{r}$. By Lemma 3.1, the graph induced by $B_{i}$ is strongly
connected. This is equivalent with the matrix $S_{B_{i}B_{i}}$ being
_irreducible_. The Perron-Frobenius theorem (see [8, 34]) implies that
$S_{B_{i}B_{i}}$ satisfies:
1. eigenvalue 1 has algebraic and geometric multiplicity 1, and
2. there are possibly other eigenvalues that are roots of 1, all with multiplicity 1, and
3. all eigenvalues not listed under cases 1 or 2, have absolute value less than 1.
The eigenvector corresponding to case 1 is the unique invariant measure in
$B_{r}$. For the eigenvector $p$ of case 2, we have that
$T_{*}^{i}p=\lambda^{i}p$ with $\lambda$ a root of unity. This implies that

$\lim_{\ell\rightarrow\infty}\frac{1}{\ell}\sum_{i=0}^{\ell-1}\,T_{*}^{i}p=0\;.$

The same holds for case 3.

Thus for each $r$, the probability is $\alpha_{r}$ that a random walker is
absorbed in $B_{r}$. Thus for large $i$, $T_{*}^{i}p$ is a combination of
invariant measures in $B_{r}$, a finite number of periodic measures, and a
remainder that decays exponentially. The averaging cancels the periodic (case
2) and decaying (case 3) parts. Hence,

$\lim_{\ell\rightarrow\infty}\frac{1}{\ell}\sum_{i=0}^{\ell-1}\,T_{*}^{i}p^{(0)}=\sum_{m=1}^{k}\,\alpha_{r}\,\bar{\gamma}_{m}=\sum_{m=1}^{k}\,\left(p^{(0)}\gamma_{m}\right)\,\bar{\gamma}_{m}\;.$

######  Corollary 5.6.

Assume the hypotheses of Theorem 5.4. Suppose that in addition the following
is true: for each cabal $B_{i}$, there is a $k_{i}$ so that the $k_{i}$-th
power of $S_{B_{i}B_{i}}$ is strictly positive, then

$\lim_{\ell\rightarrow\infty}\,T_{*}^{\ell}p^{(0)}=\sum_{m=1}^{k}\,\left(p^{(0)}\gamma_{m}\right)\,\bar{\gamma}_{m}\;.$

######  Proof 5.7.

The proof of this statement is exactly the same as the proof of Theorem 5.4,
except that now each matrix $S_{B_{i}B_{i}}$ is _primitive_. Primitivity
guarantees that case 2 of that proof does not occur. For a (generalized)
eigenvector $p$ as in case 3, $T_{*}^{i}p$ converges to 0. Hence the averaging
is not necessary.

######  Theorem 5.8.

Let $G$ be a graph with Laplacian ${\cal L}=I-S$ with $k$ reaches
$\\{R_{i}\\}_{i=1}^{k}$. Then the solution of the consensus problem of
Definition 2.5 with initial condition (at $t=0$) $x^{(0)}$ satisfies

$\lim_{t\rightarrow\infty}\,x^{(t)}=\sum_{m=1}^{k}\,\left(\bar{\gamma}_{m}x^{(0)}\right)\,\gamma_{m}\;.$

Note that $(\bar{\gamma}_{m}x^{(0)})$ is a scalar.

######  Proof 5.9.

The right and left eigenvectors of ${\cal L}$ defined in Theorems 3.3 and 4.8
satisfy $\bar{\gamma}_{i}\gamma_{j}=\delta_{ij}$ for $i,j\in\\{1,\cdots k\\}$.
According to Lemma 5.1, one can extend theses sets of vectors to dual bases of
right and left (generalized) eigenvectors $\\{\gamma_{\ell}\\}_{\ell=1}^{n}$
and $\\{\bar{\gamma}_{\ell}\\}_{\ell=1}^{n}$ such that for $i\leq k$ and
$\ell>k$

$\bar{\gamma}_{i}\gamma_{\ell}=\bar{\gamma}_{\ell}\gamma_{i}=0\;.$

Let $\lambda_{i}$ be the $i$th eigenvalue associated with the (generalized)
eigenvector $\gamma_{i}$ (or $\bar{\gamma}_{i}$). Now we consider the
consensus problem with initial condition $x^{(0)}=y^{(0)}+z^{(0)}$ where

$x^{(0)}=y^{(0)}+z^{(0)}\;\;{\rm
where}\;\;y^{(0)}=\sum_{i=1}^{k}\,\alpha_{i}\gamma_{i}\;\;{\rm
and}\;\;z^{(0)}=\sum_{i=k+1}^{n}\,\alpha_{i}\gamma_{i}\;.$ (1)

From the standard theory of linear differential equations (see, for example,
[1]), one easily derives that the general solution of the consensus problem is
given by

$x^{(t)}=e^{-{\cal
L}t}x^{(0)}=\sum_{i=1}^{n}\,\beta_{i}\gamma_{i}e^{-\lambda_{i}t}p_{i}(t)\;,$
(2)

where $\beta_{i}$ are constants. Here $p_{i}(t)$ are polynomials whose degree
is less than the size of the corresponding Jordan block. Furthermore, if
$\gamma_{i}$ is an actual eigenvector (not a generalized one), then
$\alpha_{i}=\beta_{i}$.

By Theorem 3.3, we have that in equation (2), $\lambda_{i}=0$ for
$i\in\\{1,\cdots k\\}$. Also, the eigenvalue zero has only trivial Jordan
blocks and so for $i\in\\{1,\cdots k\\}$, $p_{i}=1$ and
$\beta_{i}=\alpha_{i}$. By Theorem 3.4, we have that all the other terms (for
$i>k$) converge to zero. Therefore, using equation (1),

$\lim_{t\rightarrow\infty}\,x^{(t)}=\sum_{m=1}^{k}\,\alpha_{m}\,\gamma_{m}=y^{(0)}\;.$

Next, we determine the $\alpha_{i}$. Let $\Gamma$ be the matrix whose $i$th
column equals $\gamma_{i}$. The previous equation implies that ($\gamma_{i}$
being he columns of $\Gamma$)

$\Gamma\left(\sum_{i=1}^{k}\,\alpha_{i}{\bf
1}_{\\{i\\}}\right)=y^{(0)}\Longrightarrow\sum_{m=1}^{k}\,\alpha_{m}{\bf
1}_{m}=\bar{\Gamma}y^{(0)}\;.$

With the definition of $x^{(0)}$ and first paragraph of this proof, this
implies that

$\alpha_{m}=\bar{\gamma}_{m}y^{(0)}=\bar{\gamma}_{m}x^{(0)}\;,$

from which the result follows.

An alternate proof of this result can be found in [31].

There is a striking way to express the duality between consensus and
diffusion. In Theorem 5.8, the factor within the parentheses in
$\left(\bar{\gamma}_{m}x^{(0)}\right)\,\gamma_{m}$ is a real number. Since
multiplication of a real and vector is commutative, it can be written as
$\gamma_{m}\,\left(\bar{\gamma}_{m}x^{(0)}\right)$. But multiplication is
associative, and thus this is equal to
$\left(\gamma_{m}\,\bar{\gamma}_{m}\right)\,x^{(0)}$. The same reasoning works
for the corresponding expression in Theorem 5.4. The notation becomes more
compact upon observing that
$\left[\sum_{m=1}^{k}\gamma_{m}\,\bar{\gamma}_{m}\right]=\Gamma^{0}\bar{\Gamma}^{0}$.
Thus we obtain the following.

######  Corollary 5.10.

Let $G$ be a graph with Laplacian ${\cal L}=I-S$ with $k$ reaches
$\\{R_{i}\\}_{i=1}^{k}$. Then the solution of the random walker with initial
condition $p^{(0)}$ and of the consensus problem with initial condition
$x^{(0)}$, respectively, satisfy

$\lim_{\ell\rightarrow\infty}\frac{1}{\ell}\sum_{i=0}^{\ell-1}\,T_{*}^{i}p^{(0)}=p^{(0)}\,\Gamma^{0}\bar{\Gamma}^{0}\;\;{\rm
and}\;\;\lim_{t\rightarrow\infty}\,x^{(t)}=\Gamma^{0}\bar{\Gamma}^{0}\,x^{(0)}\;.$

Equivalently,
$\lim_{\ell\rightarrow\infty}\frac{1}{\ell}\sum_{i=0}^{\ell-1}\,S^{j}=\lim_{t\rightarrow\infty}\,e^{-{\cal
L}t}=\Gamma^{0}\bar{\Gamma}^{0}$.

Of course, the same result also holds for the discrete version of the
consensus and the continuous version of diffusion mentioned in Definitions 2.5
and 2.6. Note that the matrix $e^{-{\cal L}t}$ is well studied in the context
of a continuous-time Markov chains where it is called the _heat kernel_. We
refer the reader to [25] for more details.

##  6 Application to Ranking Algorithms

In this section, we derive the pagerank algorithm using the consensus problem.
This explanation is the “dual” of the usual one, which is in terms of the
random walk. We also show that pageranks “with teleporting” can be easily
expressed in terms of pageranks “without teleporting”.

For a graph with vertex set $V$ and $U\subseteq V$, let ${\bf 1}_{U}$ denote
the (column) vector that has the value 1 on $U$ and 0 elsewhere. We set ${\bf
1}_{V}\equiv{\bf 1}$ (as before). The second part of Corollary 5.10 tells us
that in the consensus problem the final displacements when the initial
condition is ${\bf 1}_{\\{v\\}}$ are equal to
$\left[\sum_{m}\,\gamma_{m}\bar{\gamma}_{m})\right]\,{\bf 1}_{\\{v\\}}$. As
first noted in [26], the _mean_ of these displacements over all vertices is a
good measure of the influence that vertex $v$ exerts over the long term
behavior of the solution to the consensus problem. This naturally leads to the
following definition.

######  Definition 6.1.

For a graph $G$ with $n$ vertices, the _influence_ of a vertex $v$ is given by

$I(v)=\frac{{\bf 1}^{T}}{n}\,\Gamma^{0}\bar{\Gamma}^{0}\,{\bf 1}_{\\{v\\}}\;.$

The _influence vector_ $I$ is the row vector whose $j$th component equals
$I(j)$ or

$I=\frac{{\bf 1}^{T}}{n}\,\Gamma^{0}\bar{\Gamma}^{0}\;.$

From this we see that the influence of $v$ equals the average of the $v$th
column of the matrix $\Gamma^{0}\bar{\Gamma}^{0}$. It is nonnegative. It is
positive if and only if some $\bar{\gamma}_{m}$ is non-zero at $v$, that is:
if $v$ is part of a cabal. The sum of all influences equals 1. Thus the
influence vector is a probability measure. It is straightforward to see that
the influence of a subset $U$ of vertices equals: $\frac{{\bf
1}^{T}}{n}\,\left[\sum_{m}\,\gamma_{m}\bar{\gamma}_{m}\right]\,{\bf 1}_{U}$.

The fact that $I(v)>0$ only if $v$ is part of a cabal is not entirely
realistic for networks such as the internet. A page may contain information
even though it has both in- and out-links. That information, of course, had to
be put there by some other entity in the first place. Following [26], one
could say that, in fact, each page $v$ has an associated (meta) page $b_{v}$
together with an edge $b_{v}\rightarrow v$.

######  Definition 6.2.

Let $G$ be a graph with $n$ vertices and stochastic weighted adjacency matrix
$S$. The _extended graph_ $E_{\alpha}[G]$ is defined as the graph $G$ together
with one new vertex $b_{v}$ and one new edge $b_{v}\rightarrow v$ of weight
$\alpha>0$ for each $v\in V$.

The new graph $E_{\alpha}[G]$ has exactly $n$ reaches
$\\{\tilde{R}_{i}\\}_{i=1}^{n}$ and $R_{i}$ the new vertex $b_{i}$ as leader.
The natural choice for the weight $\alpha$ would appear to be 1, but in actual
applications it tends to have different values. So we keep it as a (positive)
parameter. In what follows we need to distinguish vectors in $\mathbb{R}^{2n}$
from those in $\mathbb{R}^{n}$. To do that we mark the former with a tilde.
The same device is used to distinguish $2n\times 2n$ matrices from $n\times n$
matrices. We label the vertices of $E_{\alpha}[G]$ in the following order:
$\\{b_{1},\cdots b_{n},1,\cdots n\\}$. The first $n$ vertices are the leaders
and this set will be denoted by $B$. The second set of $n$ vertices we
continue to refer to as $V$.

The Laplacian and the random walk Laplacian associated with $E_{\alpha}[G]$
are

$\tilde{L}=\begin{pmatrix}{\bf 0}&{\bf 0}\\\ -\alpha
I&(1+\alpha)I-S\end{pmatrix}\Longrightarrow\ \tilde{{\cal
L}}=\begin{pmatrix}{\bf 0}&{\bf 0}\\\
-\frac{\alpha}{1+\alpha}I&I-\frac{1}{1+\alpha}S\end{pmatrix}\;.$

The normalized Laplacian with teleportation is given in the same way, except
that we use $S_{t}$ instead of $S$. We are now ready to discuss pagerank. We
begin with an alternate formulation. In Corollary 6.6, we will show how this
is equivalent to the standard treatment (as found, for example, in [34]).

######  Definition 6.3.

For a graph $G$ with $n$ vertices, the _pagerank_ of a vertex $v$ is given by

$\wp(v)=2\tilde{I}(b_{v})-\frac{1}{n}\;.$

Here, $\tilde{I}$ is the influence of $b_{v}$ in the extended graph
$E_{\alpha}[G]$. The _pagerank vector_ $\wp\in\mathbb{R}^{n}$ is the row
vector whose $j$th component equals $\wp(j)$.

######  Theorem 6.4.

Let $G$ be a graph with vertex set $V$, $|V|=n$, and Laplacian ${\cal L}=I-S$
or ${\cal L}=I-S_{t}$. The pagerank vector of Definition 6.3 is the unique
probability measure on $\mathbb{R}^{n}$ that satisfies

$\wp=\dfrac{\alpha}{n}{\bf 1}^{T}(\alpha I+{\cal L})^{-1}\;.$

######  Proof 6.5.

From the comments after Definition 6.1, we know that the sum of the influences
equals 1. We know that the influence of non-leaders is zero and so
$\sum_{v}\,\left(2\tilde{I}(b_{v})-\frac{1}{n}\right)=2-1=1$. Also $\wp(v)\geq
0$, because the displacement of $b_{v}$ in the consensus problem is 1 and the
others are non-negative (Theorem 5.8).

Sections 3 and 4 provides us with appropriate bases
$\\{\tilde{\bar{\gamma}}_{i}\\}_{i=1}^{n}$ and
$\\{\tilde{{\gamma}}_{i}\\}_{i=1}^{n}$ of the left and right kernels of
$\tilde{\cal{L}}$. From Theorems 4.8 and 3.3 we know that for $1\leq m\leq n$,

$\tilde{\bar{\gamma}}_{m}=({\bf 1}_{\\{m\\}}^{T},{\bf 0}^{T})\;\;{\rm
and}\;\;\tilde{{\gamma}}_{m}=\begin{pmatrix}{\bf 1}_{\\{m\\}}\\\
\eta_{m}\end{pmatrix}\;.$

With these constraints, $\tilde{\gamma}_{m}$ is entirely determined by
$\tilde{L}\tilde{{\gamma}}_{m}=0$. This is equivalent to

$(\alpha I+{\cal L})\eta_{m}=\alpha{\bf 1}_{\\{m\\}}\;.$

Since $\alpha>0$ and ${\cal L}$ has no negative eigenvalues, the matrix
$(\alpha I+{\cal L})$ can be inverted. Thus $\wp(m)$ is the average over $V$
of the displacements $\eta_{m}$:

$\wp(m)=\frac{{\bf 1}^{T}}{\alpha}\eta_{m}=\dfrac{\alpha}{n}{\bf 1}^{T}(\alpha
I+{\cal L})^{-1}{\bf 1}_{\\{m\\}}\;.$

The result follows immediately from this.

We use the vectors $\tilde{\bar{\gamma}}_{m}$ and $\tilde{\bar{\gamma}}_{m}$
to define the matrices $\tilde{\Gamma}^{0}$ and $\tilde{\bar{\Gamma}}^{0}$
analogous to Definition 5.3. From Definition 6.1, we obtain that

$\tilde{I}(b_{v})=\frac{\tilde{{\bf
1}}^{T}}{2n}\,\tilde{\Gamma}^{0}\tilde{\bar{\Gamma}}^{0}\,\tilde{{\bf
1}}_{\\{b_{v}\\}}=\frac{\tilde{{\bf 1}}_{B}^{T}+\tilde{{\bf
1}}_{V}^{T}}{2n}\,\tilde{\Gamma}^{0}\tilde{\bar{\Gamma}}^{0}\,\tilde{{\bf
1}}_{\\{b_{v}\\}}\;.$

The initial condition $\tilde{{\bf 1}}_{\\{b_{v}\\}}$ in the consensus problem
for $E_{\alpha}[G]$ displaces no leaders, except $b_{v}$ itself by one unit.
Thus $\frac{\tilde{{\bf
1}}_{V}^{T}}{2n}\,\tilde{\Gamma}^{0}\tilde{\bar{\Gamma}}^{0}\,\tilde{{\bf
1}}_{\\{b_{v}\\}}=\dfrac{1}{2n}$. Putting this together, we see that

$\wp(v)=\frac{\tilde{{\bf
1}}_{B}^{T}}{n}\,\tilde{\Gamma}^{0}\tilde{\bar{\Gamma}}^{0}\,\tilde{{\bf
1}}_{\\{b_{v}\\}}\;.$

In other words, the pagerank of the vertex $v$ is in fact the mean over _only_
the vertices in $V$ of the “old” graph $G$ of the displacements in the
consensus problem on $E_{\alpha}[G]$ caused by initial condition ${\bf
1}_{\\{b_{v}\\}}$. We now turn to a different interpretation of the pagerank.

######  Corollary 6.6.

Let $G$ be a graph with vertex set $V$, $|V|=n$, and Laplacian ${\cal L}=I-S$.
The pagerank vector of Definition 6.3 is the probability measure on
$\mathbb{R}^{n}$ that satisfies

$\wp=\wp\left(\beta S+\dfrac{1-\beta}{n}J\right)=\beta\wp
S+\dfrac{1-\beta}{n}\,{\bf 1}^{T}=0\;,$

where $J$ is the all ones matrix and $\beta\equiv\dfrac{1}{1+\alpha}\in(0,1)$.

######  Proof 6.7.

Since $\wp$ is a probability measure, we have that ${\bf 1}^{T}=\wp J$, where
$J$ is the all ones matrix. Substituting this in Theorem 6.4 and right
multiplying by $(\alpha I+{\cal L})$ gives

$\wp\left(\alpha I+{\cal L}-\dfrac{\alpha}{n}J\right)=0\;.$

Substitute ${\cal L}=I-S$ and divide by $1+\alpha$ to get

$\wp\left(I-\dfrac{1}{1+\alpha}S-\dfrac{\alpha}{n(1+\alpha)}J\right)=0\;.$

Substituting $\beta$ for $\alpha$ gives the required statement.

The traditional interpretation of the pagerank (as discussed in [34]) is
evident in this result. The pagerank vector is the unique invariant
probability measure that results from applying the random walk with
probability $\beta$ and uniform teleporting with probability $1-\beta$. It is
clear that the resulting matrix $S_{pagerank}\equiv\beta
S+\dfrac{1-\beta}{n}J$ is row stochastic and primitive. Thus standard
arguments using the Perron-Frobenius theorem show that the eigenvalue 1 is
simple and all other eigenvalues are strictly smaller. In fact, since
(generalized) eigenvectors of $S$ are eigenvectors of $J$, it follows that all
other eigenvalues have modulus less than $\beta$. The leading eigenvector is
strictly positive. Google’s pagerank algorithm takes $\beta=0.85$ [34], and so
after roughly 57 iterates, convergence of $S_{pagerank}^{n}$ to the pagerank
is already accurate to 4 decimal places. The quick convergence plus the fact
that $S_{pagerank}^{n}$ can be cheaply computed without using the full matrix,
guarantees efficient algorithms for the computation of the pagerank vector.

The last result describes essentially two ranking algorithms, depending on how
$S$ is defined. In the introduction, we gave the definition of $S$ and of
$S_{t}$ with teleporting. These give rise to pageranks $\wp$ and $\wp_{t}$.
These two ranks have an interesting relation to one another, essentially that
of deck of cards before and after one shuffle.

To see this, denote the set of vertices that are leaders by $L$ and the rest
by $R$. Thus

$S=\begin{pmatrix}S_{LL}&S_{LR}\\\
S_{RL}&S_{RR}\end{pmatrix}\;,\wp=(\wp_{L},\wp_{R})\;,{\bf 1}^{T}=({\bf
1}^{T}_{L},{\bf 1}^{T}_{R})\;,{\textrm{e}tc}.$

######  Proposition 6.8.

With the above notation, we have

$\displaystyle\wp_{t,L}$ $\displaystyle=$
$\displaystyle\left(\beta\pi_{t}+(1-\beta)\right)\wp_{L}\;,$
$\displaystyle\wp_{t,R}$ $\displaystyle=$
$\displaystyle\left(\dfrac{\beta}{1-\beta}\,\pi_{t}+1\right)\,\wp_{R}\;,$

where $\pi_{t}=\sum_{j\in L}\,\wp_{t}(j)$.

######  Proof 6.9.

Corollary 6.6 says:

$\displaystyle\wp_{L}(I-\beta
S_{LL})=\beta\wp_{R}S_{RL}+\dfrac{1-\beta}{n}\,{\bf 1}_{L}^{T}\;,$
$\displaystyle\wp_{R}(I-\beta
S_{RR})=\beta\wp_{L}S_{LR}+\dfrac{1-\beta}{n}\,{\bf 1}_{R}^{T}\;.$

In the case without teleporting, we get:

$S_{LL}=I_{LL}\;\;{\rm and}\;\;S_{LR}=0\;.$

With teleporting, this becomes:

$S_{LL}=\dfrac{1}{n}J_{LL}\;\;{\rm and}\;\;S_{LR}=\dfrac{1}{n}J_{LR}\;.$

The former will not receive a subscript, the latter will be denoted with the
subscript “t”. Denote $\pi=\sum_{j\in L}\,\wp(j)$ and $\pi_{t}=\sum_{j\in
L}\,\wp_{t}(j)$. Thus, without teleporting, the equations of Corollary 6.6
become:

$\begin{array}[]{ccl}\wp_{L}&=&\dfrac{\beta}{1-\beta}\,\wp_{R}S_{RL}+\dfrac{1}{n}\,{\bf
1}_{L}^{T}\;,\\\\[8.5359pt] \wp_{R}&=&\dfrac{1-\beta}{n}\,{\bf
1}_{R}^{T}(I-\beta S_{RR})^{-1}\;.\\\ \end{array}$

Since $S$ has spectral radius 1 and $\beta\in(0,1)$, the inverse is well-
defined. Noting that $\wp_{t,L}J_{LR}=\pi_{t}{\bf 1}_{R}$ and
$\wp_{t,L}J_{LL}=\pi_{t}{\bf 1}_{L}$, the equations _with_ teleporting become

$\begin{array}[]{ccl}\wp_{t,L}&=&\beta\wp_{t,R}S_{RL}+\dfrac{1}{n}\,\left(\beta\,\pi_{t}+(1-\beta)\right)\,{\bf
1}_{L}^{T}\;,\\\
\wp_{t,R}&=&\dfrac{1-\beta}{n}\,\left(\dfrac{\beta}{1-\beta}\,\pi_{t}+1\right)\,{\bf
1}_{R}^{T}(I-\beta S_{RR})^{-1}\;.\end{array}$

This gives the required relation between $\wp_{t,R}$ and $\wp_{R}$.
Substituting these expressions into $\wp_{L}$ and $\wp_{t,L}$, respectively,
gives:

$\begin{array}[]{ccl}\wp_{L}&=&\dfrac{\beta}{n}\,{\bf 1}_{R}^{T}\,(I-\beta
S_{RR})^{-1}\,S_{RL}+\dfrac{1}{n}\,{\bf 1}_{L}^{T}\;.\\\\[8.5359pt]
\wp_{t,L}&=&\dfrac{\beta}{n}\,\left(\beta\,\pi_{t}+(1-\beta)\right)\,{\bf
1}_{R}^{T}\,{\bf 1}_{R}^{T}(I-\beta
S_{RR})^{-1}\,S_{RL}+\dfrac{1}{n}\,\left(\beta\,\pi_{t}+(1-\beta)\right)\,{\bf
1}_{L}^{T}\;.\end{array}$

And this yields the relation between $\wp_{t,L}$ and $\wp_{L}$.

To express $\wp_{t}$ completely in terms of $\wp$, we add the following
result.

######  Corollary 6.10.

With the above notation, we also have

$\displaystyle\begin{array}[]{ccl}\pi_{t}&=&\dfrac{(1-\beta)\pi}{1-\beta\pi}\;.\end{array}$

######  Proof 6.11.

Summing the coefficients on the left and right hand sides of the equations of
Proposition 6.8, and taking into account that $\sum_{j\in R}\,\wp_{(}j)=1-\pi$
(and similar for $\pi_{t}$), we get

$\displaystyle\begin{array}[]{ccl}\pi_{t}&=&\left(\beta\pi_{t}+(1-\beta)\right)\pi\\\\[8.5359pt]
1-\pi_{t}&=&\dfrac{1}{1-\beta}\,\left(\beta\pi_{t}+(1-\beta)\right)(1-\pi)\;.\end{array}$

Dividing the first equation by the second gives
$\dfrac{\pi_{t}}{1-\pi_{t}}=(1-\beta)\,\dfrac{\pi}{1-\pi}$, which is
equivalent to the statement of the Corollary.

##  7 A Simple Example

In this section, we illustrate the definitions and results with the graph
given in Figure 1. The unweighted Laplacian matrix equals (row and column $i$
correspond to vertex $i$)

$M=\left(\begin{array}[]{ccccccc}0&0&0&0&0&0&0\\\ -1&1&0&0&0&0&0\\\
0&0&1&0&-1&0&0\\\ 0&0&-1&1&0&0&0\\\ 0&0&0&-1&1&0&0\\\ -1&0&0&0&0&2&-1\\\
0&0&-1&0&0&-1&2\end{array}\right)\;.$

By ordering the vertices so that we list the exclusive part first, we see that
the matrix $M$ is lower block-triangular. In the exclusive blocks, we list the
vertices in the cabal first, and then the others. The exclusive block itself
is then also lower block-triangular.

Figure 1: _A graph (vertices as labeled) with two reaches
$R_{1}=\\{1,2,6,7\\}$ and $R_{2}=\\{3,4,5,6,7\\}$. Each reach $R_{i}$ has
cabal $B_{i}$, exclusive part $H_{i}$, and common part $C_{i}$. According to
the definitions in the text: $B_{1}=\\{1\\}$, $H_{1}=\\{1,2\\}$,
$C_{1}=\\{6,7\\}$, $B_{2}=\\{3,4,5\\}$, $H_{2}=\\{3,4,5\\}$,
$C_{2}=\\{6,7\\}$._

The algorithm at the beginning of Section 4 gives the stochastic matrix $S$ as

$S=\left(\begin{array}[]{ccccccc}1&0&0&0&0&0&0\\\ 1&0&0&0&0&0&0\\\
0&0&0&0&1&0&0\\\ 0&0&1&0&0&0&0\\\ 0&0&0&1&0&0&0\\\ 1/2&0&0&0&0&0&1/2\\\
0&0&1/2&0&0&1/2&0\end{array}\right)\;\;{\rm and}\;\;{\cal
L}=\left(\begin{array}[]{ccccccc}0&0&0&0&0&0&0\\\ -1&1&0&0&0&0&0\\\
0&0&1&0&-1&0&0\\\ 0&0&-1&1&0&0&0\\\ 0&0&0&-1&1&0&0\\\ -1/2&0&0&0&0&1&-1/2\\\
0&0&-1/2&0&0&-1/2&1\end{array}\right)\;.$

The stochastic matrix with teleporting $S_{t}$ is nearly the same: the second
row entries are replaced by 1/7.

The bases of the left and right kernels of the Laplacian ${\cal L}=I-S$ of
Theorems 3.3 and 4.8 are, respectively,

$\begin{array}[]{c}\gamma_{1}^{T}=\left(\begin{array}[]{ccccccc}1,&1,&0,&0,&0,&\frac{2}{3},&\frac{1}{3}\end{array}\right)\;\;{\rm
and}\;\;\gamma_{2}^{T}=\left(\begin{array}[]{ccccccc}0,&0,&1,&1,&,1,&\frac{1}{3},&\frac{2}{3}\end{array}\right)\;,\\\\[14.45377pt]
\bar{\gamma}_{1}=\left(\begin{array}[]{ccccccc}1,&0,&0,&0,&0,&0,&0\end{array}\right)\;\;{\rm
and}\;\;\bar{\gamma}_{2}=\left(\begin{array}[]{ccccccc}0,&0,&\frac{1}{3},&\frac{1}{3},&\frac{1}{3}&0,&0\end{array}\right)\;.\end{array}$

The general solutions to both the random walk and the consensus problems are
given in terms of these vectors as in Theorems 5.4 and 5.8. Note that for the
former, Corollary 5.6 does not hold. In this example, the matrix
$\left[\frac{1}{n}\sum_{m}\,\gamma_{m}\bar{\gamma}_{m}(v)\right]$ is:

$\frac{1}{7\cdot 9}\,\left(\begin{array}[]{ccccccc}9&0&0&0&0&0&0\\\
9&0&0&0&0&0&0\\\ 0&0&3&3&3&0&0\\\ 0&0&3&3&3&0&0\\\ 0&0&3&3&3&0&0\\\
6&0&1&1&1&0&0\\\ 3&0&2&2&2&0&0\end{array}\right)\;.$

Thus the influence vector is

$\left(\begin{array}[]{ccccccc}\frac{3}{7},&0,&\frac{4}{21},&\frac{4}{21},&\frac{4}{21},&0,&0\end{array}\right)$

Next, we solve for the pageranks with $\alpha=1$ (or $\beta=\frac{1}{2}$).
Without teleporting we get

$(I+{\cal L})^{-1}=\dfrac{1}{14\cdot
15}\,\left(\begin{array}[]{ccccccc}210&0&0&0&0&0&0\\\ 105&105&0&0&0&0&0\\\
0&0&120&30&60&0&0\\\ 0&0&60&120&30&0&0\\\ 0&0&30&60&120&0&0\\\
56&0&8&2&4&112&28\\\ 14&0&32&8&16&28&112\\\ \end{array}\right)\;.$

From this the pagerank vector follows from Theorem 6.4:

$\wp=\dfrac{1}{294}\left(\begin{array}[]{ccccccc}77,&21,&50,&44,&46,&28,&28\end{array}\right)\;.$

The same calculation using ${\cal L}_{t}=I-S_{t}$ gives:

$\wp_{t}=\dfrac{1}{273}\left(\begin{array}[]{ccccccc}56,&21,&50,&44,&46,&28,&28\end{array}\right)\;.$

Notice that the teleporting decreases the rank of vertex 1 and re-distributes
the remaining measure over the other vertices. It is easy to check that
$L=\\{1\\}$ and $\wp_{t}(1)=\dfrac{(1-\beta)\wp(1)}{1-\beta\wp(1)}$ (Corollary
6.10).

##  8 Appendix: Discrete versus Continuous Consensus

We briefly discuss the way discrete and continuous consensus relate to one
another. The case of diffusion is exactly the same.

If we start with the flow defined by $\dot{x}=-{\cal L}x$ on a digraph $G$
then, we can easily determine its time 1 map, namely $x^{(n+1)}=e^{-{\cal
L}}x^{(n)}$, as well as its properties. A graph $\tilde{G}$ is a _transitive
closure_ of the graph $\tilde{G}$ if for every possible (directed) path in
$i\rightsquigarrow j$ in $G$ there is a (directed) edge $i\rightarrow j$ in
${\tilde{G}}$.

######  Proposition 8.1.

Consider a non-negative row-stochastic adjacency matrix $S$ associated with
the graph $G$ and a (rw) Laplacian ${\cal L}=I-S$. Then
(i) $e^{-{\cal L}}$ is row-stochastic,
(ii) $e^{-{\cal L}}$ is non-negative, and
(iii) $e^{-{\cal L}}$ is the adjacency matrix of a transitive closure of $G$.

######  Proof 8.2.

(i) From the expansion $e^{-{\cal L}}$ in powers of ${\cal L}$, we see that
$e^{-{\cal L}}$ must have row sum 1. (ii) If we expand $e^{-{\cal
L}}=e^{S-I}=e^{-1}e^{S}$ in powers of $S$, we see that $e^{-{\cal L}}$ is non-
negative. (iii) By (i) and (ii), we may consider $e^{-{\cal L}}$ as a
(weighted) adjacency matrix ${\tilde{S}}$ of a graph ${\tilde{G}}$. The $ji$
entry of $S^{k}$ positive if and only if there is a path $i\rightsquigarrow j$
of length $k$ in $G$. The expansion in $e^{S}$ shows that every power of S
occurs with a positive coefficient. Thus the $ji$ entry of ${\tilde{S}}$ is
positive if and only if there is a path $i\rightsquigarrow j$.

Now let us start with a time 1 map $x^{(n+1)}=Sx^{(n)}$ and consider the much
more challenging problem of constructing (if possible) a flow $\dot{x}=-{\cal
L}x$ that generates it. The matrix ${\cal L}$ is sometimes referred as the
_logarithm_ of $S$ [20]. A stochastic matrix (or its corresponding Markov
chain) for which such a flow exists is called _embeddable_. The problem of
characterizing the embeddable stochastic matrices is known as the _embedding
problem for finite Markov chains_ and is an area of current research interest.
The general problem of determining if a given stochastic matrix has such a
flow has been recently shown to be NP-complete [16]. Recent characterizations
for special classes of stochastic matrices can be found in [22] and [36].

There is an obvious obstruction to the construction of a continuous flow
$\dot{x}=-{\cal L}x$ that generates a given discrete system
$x^{(n+1)}=Sx^{(n)}$ as its time 1 map $x^{(n+1)}=e^{-{\cal L}}x^{(n)}$.
Namely, if $S$ has an eigenvalue 0, then there is there is no flow whose time
1 map generates it. Intuitively, this is because $e^{-{\cal L}}v=0$ would
imply that ${\cal L}v$ diverges, which, as we have seen, is impossible for a
laplacian ${\cal L}$. For more details we refer the reader to [20] (under
_logarithms of matrices_).

A more interesting obstruction follows from Proposition 8.1. If the matrix $S$
does not correspond to a transitively closed graph, then the logarithm of $S$
(if it exists) cannot be rw Laplacian. Here is an example.

$S=\begin{pmatrix}1&0&0\\\ 1/2&1/2&0\\\ 0&3/5&2/5\end{pmatrix}\quad\;\;{\rm
and}\;\;\quad\ln(S)=\begin{pmatrix}0&0&0\\\ \ln(2)&-\ln(2)&0\\\
\ln(2^{11}/5^{5})&\ln(5^{6}/2^{12})&\ln(2/5)\end{pmatrix}\;.$

Perhaps surprisingly, transitive closure of the graph associated with a
stochastic matrix $S$ is not sufficient to ensure that $S$ is embeddable.
Examples can be found in [22]. These examples give real logarithms of $S$
which are not Laplacians. One can show that there are no other real logarithms
(c.f. Theorem 2 in [17]).

######  Corollary 8.3.

The right kernels of ${\cal L}$ an ${\tilde{\cal L}}$ are equal. Similar for
the left kernels.

######  Proof 8.4.

The structure of the reaches in a graph is entirely determined by the paths in
that graph. Thus, the reaches and in particular their subdivision in cabals,
exclusive parts, and common parts are the same for $G$ and ${\tilde{G}}$. Thus
dimension of the kernels is the same. Since kernels are linear spaces, it is
sufficient to show that $\ker{\cal L}\subseteq\ker{\tilde{\cal L}}$. So, let
$v\in{\cal L}$, then

${\tilde{\cal L}}v=\left(I-e^{-{\cal L}}\right)v=0\;,$

where the last equality follows upon expanding the exponential.

Remark: As we observed above, there is one substantial difference between $S$
an $e^{-\cal L}$. While the strongly connected components of the two are
equal, the restriction of ${\tilde{S}}$ to such a component is strictly
positive. That means that the matrix restricted to such a component is
_primitive_ , and no periodic behavior occurs. Hence the averaging we see in
Theorem 5.4 for a discrete system is replaced by a straightforward limit for
continuous systems (Theorem 5.8).

###### Acknowledgements.

The authors gratefully acknowledge a useful conversation with Jeff Ovall.

## References

  * [1] V. I. Arnold, Ordinary Differential Equations, 3rd edn (Springer, Berlin, 1992).
  * [2] R. Agaev P. Chebotarev, ‘On the spectra of non-symmetric laplacian matrices’, Lin. Alg. and its Appl. 399 (2005) 157-168
  * [3] R. Ahlswede _et al._ , ‘Network information flow’, IEEE Transactions on Information Theory 46 (2000) no. 4, 1204-1216.
  * [4] R. Angles C. Guiterrez, ‘Survey of graph database models’, ACM Computing Surveys 40 (2008) No. 1, 1-39.
  * [5] J. Bang-Jensen G. Gutin, _Digraphs: Theory, Algorithms, and Applications_ , (Springer, Berlin, 2007).
  * [6] F. Bauer, ‘Normalized graph laplacians for directed graphs’, Lin. Alg. and its Appl. 436 (2012) 4193-4222.
  * [7] I. Benjamini L. Lovász, ‘Harmonic and analytic functions on graphs’, J. Geom. 76 (2003) 3-15.
  * [8] M. Boyle, _Notes on Perron-Frobenius theory of nonnegative matrices_ , 2005,
`www.math.umd.edu/~mboyle/courses/475sp05/spec.pdf`

  * [9] D. Boley, G. Ranjan, Z. Zhang, ‘Commute times for a directed graph using an asymmetric laplacian’,Lin. Alg. and its Appl. 435 (2011) 224-242.
  * [10] B. Bollobás, _Modern Graph Theory_ , (Springer, Berlin, 1998).
  * [11] A. Broder _et al._ , ‘Graph structure of the web’,Computer Networks 33 (2000) 309-322.
  * [12] P. Carrington, J. Scott, S. Wasserman, _Models and Methods in Social Network Analysis_ , (Cambridge University Press, Cambridge, 2005).
  * [13] J. S. Caughman J. J. P. Veerman, ‘Kernels of directed graph laplacians’, Electronic Journal of Combinatorics 13 (2006) No 1, R39.
  * [14] F. Chung, ‘Laplacians and the Cheeger inequality for directed graphs’, Annals of Combinatorics 9 (2005) 1-19.
  * [15] F. Chung W. Zhao, ‘Pagerank and random walks of graphs‘, Fete of Combinatorics and Computer Science, (eds G. O. H. Katona, A. Schrijver and T. Szonyi.; Springer, Berlin, 2010) 43-63.
  * [16] J. Bausch T. Cubitt, ‘The complexity of divisibility’, Lin. Alg. and its Appl. 504 (2016) 64-107.
  * [17] W. Culver, ‘On the existence and uniqueness of the real logarithm of a matrix’, Proceedings of the American Mathematical Society 17 (1966) No 5, 1146-1151.
  * [18] J. Fax R Murray, ‘Information flow and cooperative control of vehicle formations’, IEEE Transactions on Automatic Control 49 (2004) No. 9, 1465-1476.
  * [19] J. L. Gross, J. Zellen, P. Zhang, _Handbook of Graph Theory_ , 2nd edn (CRC Press, Boca Raton, 2014).
  * [20] N. Higham, _Functions of Matrices. Theory and Computation_ , (SIAM, Philadelphia, 2008).
  * [21] R. A. Horn C. R. Johnson, _Matrix Analysis_ , 2nd Edn (Cambridge University Press, New York, 2017).
  * [22] C. Jia, ‘A solution to the reversible embedding problem for finite Markov chains’, Statistics and Probability Letters 116 (2016) 122-130.
  * [23] T. Jombert _et al._ , ‘Reconstructing disease outbreaks from genetic data: a graph approach’,Heredity 106 (2011) 383-390.
  * [24] A. Langville C. Meyer, _Google’s PageRank and Beyond_ , (Princeton University Press, Princeton, 2011).
  * [25] D. A. Levin Yuval Peres, _Markov Chains and Mixing Times_ , 2nd Edn (American Mathematical Society, Providence, 2017).
  * [26] N. Masuda H. Kori, ‘Dynamics based centrality for directed networks’, Phys. Review E 82 (2010) 056107, doi:10.1103/PhysRevE.82.056107.
  * [27] N. Masuda, ‘Random walks and diffusion on networks’, Physics Reports 716-717 (2017) 1-59.
  * [28] R. M. May, ‘Qualitative stability in model ecosystems’, Ecology 54 (1973) No. 3, 638-641.
  * [29] P. McGraw M. Menzinger, ‘Laplacian spectra as a diagnostic tool for network structure and dynamics’, Physical Review E 77 (2008) 031102, doi:10.1103/PhysRevE.77.031102.
  * [30] M. Mesbahi M. Egerstedt, _Graph Theoretic Methods in Multiagent Networks_ , (Princeton University Press, Princeton, 2010).
  * [31] I. Mirzaev J. Gunawardena, ‘Laplacian dynamics on general graphs‘, Bull. Math. Biol. (11) 75 (2013) 2118-2149.
  * [32] G. Punzo _et al._ , ‘Using network dynamical influence to drive consensus’, Sci. Rep. 6 (2016) 26318, doi:10.1038/srep26318.
  * [33] S. Rao _et al._ , ‘A graph-theoretical approach for the analysis and model reduction of complex-balanced chemical reaction networks’, J. Math. Chem. 51 (2013) No. 9, 2401-2422.
  * [34] S. Sternberg, _Dynamical Systems_ , (Dover Publications, Mineola NY, 2010).
  * [35] J. J. P. Veerman _et al._ ,‘Flocks and formations’, J. Stat. Phys. (5-6) 121 (2005) 901-936.
  * [36] A. Van-Brunt, ‘Infinitely divisible nonnegative matrices, M-matrices, and the embedding problem for finite state stationary Markov chains’, Lin. Alg. and its Appl. 541 (2018) 163-176.
  * [37] D. Wagner, ‘The critical group of a graph’, preprint, https://arxiv.org/abs/math/0010241 Retrieved 2018.
  * [38] D. B. West, _Introduction to Graph Theory_ , 2nd Edn (Prentice-Hall, Upper Saddle River NJ, 2001).

J. J. P. Veerman and E. Kummel
Portland State University
PO Box 751
Portland, OR 97207-0751
United States of America