18.2: Diffusion on Networks
- Page ID
- 7879
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Many important dynamical network models can be formulated as a linear dynamical system. The first example is the diffusion equation on a network that we discussed in Chapter 16:
\[\frac{dc}{dt} =-\alpha{Lc} \label{(18.5)} \]
This is a continuous-time version, but you can also write a discrete-time equivalent. As we discussed before, \(L = D−A\) is the Laplacian matrix of the network. It is a symmetric matrix in which diagonal components are all non-negative (representing node degrees) while other components are all non-positive. This matrix has some interesting, useful dynamical properties:
A Laplacian matrix of an undirected network has the following properties:
- At least one of its eigenvalues is zero.
- All the other eigenvalues are either zero or positive.
- The number of its zero eigenvalues corresponds to the number of connected components in the network.
- If the network is connected, the dominant eigenvector is a homogeneity vector \(h = (1 1 ...1)^{T}\)a.
- The smallest non-zero eigenvalue is called the spectral gap of the network, which determines how quickly the diffusion takes place on the network.
aEven if the network is not connected, you can still take the homogeneity vector as one of the bases of its dominant eigenspace.
The first property is easy to show, because \(Lh = (D −A)h = d−d = 0\), where \(d\) is the vector made of node degrees. This means that \(h\) can be taken as the eigenvector that corresponds to eigenvalue 0. The second property comes from the fact that the Laplacian matrix is positive-semidefinite, because it can be obtained by \(L = M^{T}M\) where \(M\) is the signed incidence matrix of the network (not detailed in this textbook).
To understand the rest of the properties, we need to consider how to interpret the eigenvalues of the Laplacian matrix. The actual coefficient matrix of the diffusion equation is \(−αL\), and its eigenvalues are \({−αλ_i}\), where \({λ_i}\) are \(L\)’s eigenvalues. According to the first two properties discussed above, the coefficient matrix of the equation has at least one eigenvalue 0, and all the eigenvalues are 0 or negative. This means that the zero eigenvalue is actually the dominant one in this case, and its corresponding dominant eigenvector (\(h\), or eigenspace, if the network is not connected) will tell us the asymptotic state of the network.
Let’s review the other properties. The third property arises intuitively because, if the network is made of multiple connected components, each of those components behaves as a separate network and shows diffusion independently, converging to a different asymptotic value, and therefore, the asymptotic state of the whole network should have as many degrees of freedom as the connected components. This requires that the dominant eigenspace have as many dimensions, which is why there should be as many degenerate dominant eigenvalue 0’s as the connected components in the network. The fourth property can be derived by combining this with the argument on property 1 above.
And finally, the spectral gap. It is so called because the list of eigenvalues of a matrix is called a matrix spectrum in mathematics. The spectral gap is the smallest non-zero eigenvalue of \(L\), which corresponds to the largest non-zero eigenvalue of \(−αL\) and thus to the mode of the network state that shows the slowest exponential decay over time. Ifthe spectral gap is close to zero, this decay takes a very long time, resulting in slow diffusion. Or if the spectral gap is far above zero, the decay occurs quickly, and so does the diffusion. In this sense, the spectral gap of the Laplacian matrix captures some topological aspects of the network, i.e., how well the nodes are connected to each other from a dynamical viewpoint. The spectral gap of a connected graph (or, the second smallest eigenvalue of a Laplacian matrix in general) is called the algebraic connectivity of a network.
Here is how to obtain a Laplacian matrix and a spectral gap in NetworkX:
So, the spectral gap (= algebraic connectivity in this case) of the Karate Club graph is about 0.4685. This value doesn’t tell us much about the speed of the diffusion on that network. We will need to compare spectral gaps between different network topologies.
Randomize the topology of the Karate Club graph several times and measure their spectral gaps. Compare the result with the original value obtained above and discuss what it means in terms of the speed of diffusion.
Generate the following network topologies with comparable size and density:
• random graph
• barbell graph
• ring-shaped graph (i.e., degree-2 regular graph)
Measure their spectral gaps and see how topologies quantitatively affect the speed of diffusion.