Objective
- how does the topology of a network influence diffusion speed?
- how fast the stationary distribution can be reached?
- eigenvalues of transition matrix: captures the influence of a network on diffusion process
- eigenvectors: define feedback centrality
Questions
- what is the largest eigenvalue of a transition matrix?
- 1.
- what can we learn from the second-largest eigenvalue of a transition matrix?
- the speed of convergence to stationary distribution
- the influence of the network topology on the diffusion speed.
- how is the diffusion speed related to the eigenvalues of the transition matrix?
- the second largest eigenvalue.
- what is the minimum time $t_\epsilon$, s.t. $\delta(\pi^{(t)}, \pi^{(0)})\leq \epsilon, \forall\epsilon>0$
- $t\propto\frac{\log\epsilon}{\log \lambda_2}$
- what is the spectrum of a transition matrix?
- the sequence of ascending ordered eigenvalues
- what is the spectral gap? what does it tell us about the underlying network?
- 1-second largest eigenvalue.
- the speed of diffusion
- what is the spectral gap of a network that is not strongly connected?
- much less than 1.
- what is the algebraic connectivity of a network?
- the second smallest eigenvalue of the Laplacian matrix.
- what is the Fiedler vector of a network? What does it tell us about the topology?
- the second smallest eigenvectors.
- the cluster belonging.
Keywords
diffusion speed, Laplacian spectrum, algebraic connectivity, Fiedler vector
Eigen-decomposition
For aperiodic and irreducible stochastic matrix T
$$
|\lambda_i|<1%2C\forall i\geq 2
$$
- is the transition matrix always has a eigenvalue of 1?
- I think so. Even i haven’t proved this.
Rewrite the t-th step distribution
$$
\pi^{(t)}=\pi^{(0)}\cdot T^t
$$
$$
T = U^{-1}DU, T^t = U^{-1}D^tU
$$
$$
\pi^{(t)}=\pi^{(0)}\cdot U^{-1}D^t U=\sum_{i=1}^n\alpha_i\lambda_i^tu_i=\pi,\sum_{i=2}^n\alpha_i\lambda_i^tu_i
$$
we set $\pi^{(0)}U^{-1}=\alpha$
The last equation is the property of eigenvalue 1’s eigenvector.
Total variation distance
Compared to the final stable distribution
$$
\delta(\pi^{(t)},\pi)=\frac{1}{2}\sum_{j=1}^n|\pi_j-\pi^{(t)}_j|
$$
$$
=\frac{1}{2}\sum_{j=1}^n|(\sum_{i=2}^n\alpha_i\lambda_i^tu_i)_j|
$$
To control the distance by epsilon and use approximation,
$$
\delta(\pi, \pi^{(t)})<\epsilon\sim \frac{1}{2}\sum_{j=1}^n|\lambda_2^t \alpha_2(u_2)_j|<\epsilon
$$
$$
t\propto\frac{\log\epsilon}{\log \lambda_2}
$$
The second largest eigenvalue captures the influence of network topology on diffusion speed
Spectrum
Definition
the descending-ordered sequence of the absolute value of eigenvalues of the transition matrix.
Spectral/eigenvalue gap
$$
1-|\lambda_2|
$$
- the value range is (0,1)
- the larger the spectral gap, the faster the diffusion, $t$ is smaller
- the smaller, the slower, $t$ is larger
Allows to study the efficiency of network topologies.
Laplacian matrix
Definition
$$
L=D-A
$$
- $D$ is a diagonal matrix, with the total degree of node $i$ as the $i$-th diagonal.
- $A$: the adjacency matrix
- the row of $L$ is 0.
Continuous time differential model
$$
\frac{dx^{(t)}}{dt}=C(A-D)x^{(t)}
$$
Which is from
$$
\frac{\mathrm{d}x_i^{(t)}}{\mathrm{d}t}=C\sum_{j=1}^nA_{ij}[x^{(t)}_j-x^{(t)}_i]
$$
Written by Laplacian matrix is
$$
\frac{\mathrm{d}x^{(t)}}{\mathrm{d}t}=-CLx^{(t)}
$$
Using the knowledge of ODE, we will get
$$
x^{(t)}=\sum_{i=1}^n \alpha_i e^{-C\lambda_i t}\vec{v}_i
$$
- $C>0$
- eigenvalues must be larger than or equal to 0.
Eigenvalues
sort eigenvalues in ascending order
smallest eigenvalue is 0. And its eigenvector is $(1,\cdots,1)$. Because $(1,\cdots,1)L=0L$ , the sum of each column/row of $L$ is 0
Algebraic connectivity
the second eigenvalue of Laplacian matrix is called algebraic connectivity
$\lambda_2=0\Leftrightarrow$ the network is disconnected.
number of 0 eigenvalues is the number of components
Diffusion speed
if we hold $\lambda t$ as fixed, the larger $\lambda$ is, the smaller $t$ is required, which means faster diffusion.
$$
x^{(t)}=\sum_{i=1}^n \alpha_i e^{-C\lambda_i t}\vec{v}_i
$$
$$
=\alpha_1\vec{v_1}+\sum_{i=2}^n \alpha_i e^{-C\lambda_i t}\vec{v}_i
$$
The second smallest eigenvalue will control the $t$.
- $\lambda_2$ captures how well connected the network is.
- $\lambda_2$ captures the influence of network topology on diffusion speed.
Fiedler vector
$\vec{v_2}$ is called Fiedler vector
the eigenvector of the Laplacian matrix corresponding to the second smallest eigenvalue.
- sign of this vector allows to detect communities. Bisect the network.
- It can be applied recursively to detect more than two communities.
Summary
| matrix | Adjacency A | Transition T | Laplacian L |
|---|---|---|---|
| meaning | simple representation of networks | transition probabilities | generalization of Laplacian operator |
| eigenvalue | largest: 1, second-largest: diffusion speed, spectral gap | smallest: 0, second smallest: algebraic connectivity, connectedness/diffusion speed | |
| eigenvector | largest: eigenvector centrality, not necessarily | largest :1, stable distribution | second-smallest: Fiedler vector |
| suitable network | undirected/directed/weighted | directed/undirected/weighted | undirected, more complicated for directed |
