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 only positive values.
• Count the Katz centrality in a $k$-regular graph.

Solution:

• We want to show that $\mathbf{A}\cdot\mathbf{1} = k \cdot \mathbf{1}$. Let us realize that in the adjacency matrix of a $k$-regular graph there are exactly $k$ ones in each row, the result of matrix multiplication with a vector of all ones will be $k$ for every row, which is exactly the values in each coordinate of the vector $k \cdot \mathbf{1}$. We can write it as $\sum_{j \in [n]} A_{ij} = k$ and thus $\sum_{j \in [n]} A_{ij}\cdot \mathbf{1}_i = k \cdot \mathbf{1}_i$.
• In the previous part we have found out that $\mathbf{1}$ is an eigenvector of matrix $\mathbf{A}$. We will use the fact that all eigenvectors are orthogonal. For each eigenvector $x$ of matrix $\mathbf{A}$ then holds $\mathbf{x} \cdot \mathbf{1}^T = \mathbf{0}$. As all the coordinates of $\mathbf{1}$ are positive, any other eigenvector of matrix $\mathbf{A}$ must have at least one negative coordinate.
• In Katz centrality, each vertex is given a constant value $\beta$ at the beginning and in each step every vertex gets a value equal to the sum of the values of its neighbours until the values do not change.
  As we begin with the same values for all vertices and all vertices have the same degree, we get $x_1 = x_2 = \dots = x_n = x$. By using the formula for centrality of a vertex we get $x=\alpha\cdot\sum_{j \in [n]} A_{ij} \cdot x + \beta$. We have already shown that $\sum_{j \in [n]} A_{ij} = k$, so we get $x = \alpha \cdot kx + \beta$, which gives after modifications $x = \frac{\beta}{1-\alpha \cdot k}$. As a result, Katz centrality grows with growing $k$. We also see why it is reasonable to choose $\alpha < \frac{1}{k}$.

Task 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$.

Solution: Let us start with realizing how PageRank works. At the beginning, each vertex gets a constant value $\beta$. In each step, each vertex gets the centrality value (multiplied by $\alpha$) of the vertices from whose there exists an edge oriented towards it. Leafs will have value $1$, any neighbour of a leaf $y$ will have the value $\alpha \cdot (\deg(y) + 1)$, any neighbour $z$ of $y$ will have value $\deg(z) \cdot \alpha(\alpha (\deg(y) + 1))$ and so on. The central vertex then gets the value $$\sum_{d=1}^\infty |\Gamma_d| \cdot \alpha^d.$$