Tutorial 8: Spectral characteristics

Eigenvector centrality represents the "recursive" importance of vertices, i.e. not only number of neighbours, but also number of their neighbours etc. It is equal to the size of the eigenvector corresponding to the largest eigenvalue, $$ A\mathbf{x} = \lambda_1 \mathbf{x}$$ for $A$ adjacency matrix and $\lambda_1$ the largest eigenvalue. Vertex with large eigenvector centrality has either many neighbours, or important neighbours, or both.

Lemma (Spectral properties of adjacency matrix)

Let $A$ be adjacency matrix of (unoriented) graph $G$ with eigenvalues $\lambda_1, \lambda_2, \ldots, \lambda_n$ such that $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Then it holds that 1) $\sum_{i=1}^n \lambda_i = 0$

2) Largest eigenvalue is $\lambda_1 \geq 0$

3) $\det(A) = \prod_{i=1}^n \lambda_i$

Theorem (Positivity of eigenvalue and eigenvector, Perron-Frobenius)

Let $A$ be adjacency matrix of (unoriented) graph $G$ with eigenvalues $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Then the largest eigenvalue $\lambda_1 \geq |\lambda_i|$ for all $i \in [n]$ and corresponding eigenvector is non-negative.

In contrast to eigenvalue centrality, Katz centrality starts with each vertex having a centrality of size $\alpha$. $$x_i = \alpha\sum_j A_{ij}x_j + \beta$$ Normally we consider $\beta = 1$. Katz centrality then converges to $$\mathbf{x} = (I - \alpha A)^{-1} \mathbf{1}.$$

PageRank is similar to Katz centrality, but id divides the contributions of the neighbours by their degree. $$x_i = \alpha\sum_j A_{ij}\frac{x_j}{\max\{deg^-(x), 1\}} + \beta$$ For $\beta = 1$ it converges to $$\mathbf{x} = (I - \alpha AD^{-1}) \mathbf{1}.$$

Browsing the Internet can be modelled as a random walk with the probability of moving to other page $$P_{ij} = \begin{cases} \frac{1}{d_{j}} & \text{ if $A_{ij} = 1$}\\ 0 & \text{ otherwise} \end{cases} \quad \text{in the random walk representation as} \quad \mathbf{x} = P \mathbf{x}$$

Extension of this is lazy random walk defined as $$P = \frac{(I + P)}{2}$$ where with probability $\frac{1}{2}$ we stay where we are. This corresponds to $$\mathbf{x} = \alpha \mathbf{x} P + (1-\alpha)\mathbf{\frac{1}{n}}.$$

Tasks

Task 1: Let us have $k$-regular unoriented graph $G$.

• Show, that the all one's vector is the eigenvector of the adjacency matrix of $G$ and its eigenvalue is $k$.
• Show, that this is the only eigenvector with non-zero values.
• Count the Katz centrality in a $k$-regular graph.

Úloha 2: Count PageRank of the central vertex $c$ of a tree with root $c$ (see picture below). Suppose that we are given $\alpha$ and the distance $d_i$ between $i$ and $c$ for each vertex $i \in V(G) \setminus c$. Consider $\beta = 1$.