Centralita vlastních čísel (eigenvector centrality) závisí na skóre/důležitosti vrcholů, "rekurzivně", odpovídá velikosti vlastního vektoru odpovídajícímu největšímu vlastnímu číslu $$ A\mathbf{x} = \lambda_1 \mathbf{x}$$ pro $A$ matici sousednosti a $\lambda_1$ největší vlastní číslo. Vrchol s velikou centralitou vlastních čísel má tedy buď mnoho sousedů, nebo důležité sousedy, nebo obojí.
Lemma (O spektrálních vlastnostech matice sousednosti)
Buď $A$ matice sousednosti (neorientovaného) grafu $G$ s vlastními čísly $\lambda_1, \lambda_2, \ldots, \lambda_n$ takovými, že $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Potom platí 1) Součet vlastních čísel $\sum_{i=1}^n \lambda_i = 0$
2) Největší vlastní číslo je $\lambda_1 \geq 0$
3) $\det(A) = \prod_{i=1}^n \lambda_i$
Věta (O pozitivitě vlastního čísla a vektoru, Perron-Frobenius)
Buď $A$ matice sousednosti (neor.) grafu $G$ s vlastními čísly $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n$. Potom největší vlastní číslo $\lambda_1 \geq |\lambda_i|$ pro všechna $i \in [n]$ a odpovídající vlastní vektor je nezáporný.
Katzova centralita oproti centralitě vlastních čísel přidává každému vrcholu na začátku centralitu velikosti $\alpha$. $$x_i = \alpha\sum_j A_{ij}x_j + \beta$$ Obyčejně se uvažuje $\beta = 1$. Katzova centralita pak konverguje k $$\mathbf{x} = (I - \alpha A)^{-1} \mathbf{1}.$$
PageRank je podobný Katzově centralitě, ale dělí příspěvky sousedů stupněm daného vrcholu. $$x_i = \alpha\sum_j A_{ij}\frac{x_j}{\max\{deg^-(x), 1\}} + \beta$$ Pro $\beta = 1$ konverguje k $$\mathbf{x} = (I - \alpha AD^{-1}) \mathbf{1}.$$
Surfování na webu odpovídá náhodné procházce s pravděpodoností přechodu $$P_{ij} = \begin{cases} \frac{1}{d_{j}} & \text{ pokud $A_{ij} = 1$}\\ 0 & \text{ jinak} \end{cases} \quad \text{v procházce jako} \quad \mathbf{x} = P \mathbf{x}$$
Rozšířením je líná náhodná procházka definovaná jako $$P = \frac{(I + P)}{2}$$ kde s pravděpodobností $\frac{1}{2}$ zůstaneme na místě. Tomu odpovídá $$\mathbf{x} = \alpha \mathbf{x} P + (1-\alpha)\mathbf{\frac{1}{n}}.$$
Wienerův index $$W(G) = \sum_{\{u,v\} \subseteq V(G)} d(u,v)$$
Schrödingerova rovnice je časově závislá parciálně diferenciální rovnice $2$ řádu $$\hat{H} \Psi = \mathcal{E} \Psi$$ kde
Je možné ji aproximovat jako $$H \Psi = \mathcal{E} \Psi$$ za pomoci lineárního operátoru, tj. matice $H$ definované jako $$H_{i,j} = \begin{cases} \alpha & \text{ pokud } i = j\\ \beta & \text{ pokud mají atomy $i$ a $j$ mezi sebou vazbu}\\ 0 & \text{ jinak } \end{cases}$$
Pro matici sousednosti uhlíků $A$ dostáváme $H = \alpha I + \beta A$ a energie získáme jako vlastní čísla, tj. $$\mathcal{E}_j = \alpha + \beta \lambda_j \qquad j = 1, 2, \ldots, n$$ kde $\lambda_j$ jsou vlastní čísla $A$.
Tvrzení Buď $G$ graf obsahující $m$ hran. Potom $$2\sqrt{m} \leq \mathcal{E} \leq \sqrt{2mn}.$$
Úloha 1: Mějme $k$-regulární neorientovaný graf $G$.
Úloha 2: Spočítejte PageRank centrálního vrcholu $c$ grafu za předpokladu, že je dáno $\alpha$ a pro každý vrchol $i \in V(G) \setminus c$, vzdálenost $d_i$ mezi $i$ a $c$, přičemž graf tvoří strom s kořenem $c$ (viz ilustrace níže).