时间： 分类：   字数： 2473 字 阅读： 5分钟 阅读次数：

图的基本定义啥的就不写了，满大街都是。从 Laplace 矩阵开始的。

谱图理论基础

Laplace 矩阵

来源

考虑微积分中的 Laplace 算子。对多元函数 $f(x_1,\cdots,x_n)$，Laplace 算子 $\Delta$ 定义为 $$ \Delta f=\sum_{i=1}^n \dfrac{\partial^2 f}{\partial x_i^2}. $$ 我们用右侧差分代替各个函数的导数，即 $$ f’(x)\approx \dfrac{f(x+\Delta x)-f(x)}{\Delta x}. $$ 为简便起见，考虑二元函数 $f(x,y)$，并且统一步长为 $1$。此时二维平面变成了一张图，节点是所有格点，每个点连接了上下左右四个格点。对节点 $(x,y)$，它的四个邻居是 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$.

容易算出差分形式的 Laplace 算子为

$$ \Delta f(x,y)\approx f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y). $$

把它推广到图 $G(V,E)$，$f:V\to\mathbb{R}$，有

$$ \begin{pmatrix} \Delta f(x_1)\\ \vdots\\ \Delta f(x_n) \end{pmatrix}=-(D-W) \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_n) \end{pmatrix}. $$

Laplace 矩阵定义为 $D-W$ 而不是 $W-D$，是因为这样是半正定矩阵，而不是半负定矩阵。

性质

  • $\forall x\in\mathbb{R}^n,x^TLx=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)^2$,
  • $L$ 对称半正定，
  • 最小特征值为 $0$，其中一个特征向量为所有分量为 $1$ 的向量，
  • 特征值 $0$ 的重数为连通子图的个数，
  • 所有非 $0$ 特征值的特征向量必然与 $1$ 正交（更一般地，实对称矩阵不同特征值的特征向量正交）。

中心性（Centrality）

几种简单的中心性的度量：

  • Degree centrality: $k_u$ ($k_u^{\rm in},k_u^{\rm out}$),
  • Closeness centrality: $c_{CL}(u)=\left(\sum_v d_{uv}\right)^{-1}$,
  • Betweenness centrality: 点对 $v,w$ 的个数 which 有通过 $u$ 的最短路径（有多条则按比例算），

此外还有下面几种不那么 trivial 的。

Katz centrality (Eigenvalue centrality)

Perron-Frobenius 定理

我们要先介绍 Perron-Frobenius 定理，它描述了非负矩阵的谱的一些有趣性质。完整内容和证明请参考 https://dna049.com/perronFrobeniusTheory 。

定义（置换相似） 两个矩阵称为置换相似的，若存在置换矩阵 $P$ 满足 $P^TXP=Y$.

对于图的邻接矩阵，置换操作等价于更改节点的编号顺序。

定义（可约矩阵） 设 $A\in M_n$，称 $A$ 可约，若 $A$ 置换相似于一个形如 $\begin{pmatrix}B&0\\C&D\end{pmatrix}$ 的矩阵，其中 $B,D$ 是方阵。否则称 $A$ 不可约。

图的邻接矩阵可约，等价于图不连通。

定义（谱半径） 矩阵 $A$ 的谱半径 $\rho(A)$ 定义为矩阵 $A$ 的所有特征值的绝对值的最大值。

定理（Perron-Frobenius） 设 $A$ 是非负不可约矩阵，则

  1. $\rho(A)>0$ 且 $\rho(A)$ 是矩阵 $A$ 的一个单重特征值
  2. $A$ 有一个对应于 $\rho(A)$ 的正特征向量
  3. $A$ 的每个非负特征向量都对应于特征值 $\rho(A)$

Katz 的心路历程

$A$ 为邻接矩阵。对于 degree centrality，我们把各节点的中心度写成列向量，有 $$ c_0=A \begin{pmatrix} 1\\ \vdots\\ 1 \end{pmatrix}. $$ 这只考虑了自己的影响力，没有考虑邻居的影响力。我们希望把它改成邻居的 degree centrality 之和，即 $$ c_1=\sum_{v:(u,v)\in E} c_0(v)= Ac_0. $$ 进一步套娃，有 $c_{r+1}=Ac_r$. 但这样下去会发散，我们需要加上个衰减因子。根据 Perron-Frobenius 定理，记最大特征值为 $\lambda$，我们让 $c_{r+1}=\lambda^{-1}Ac_r$. 又记 $\lambda$ 的正特征向量为 $x$，有 $$ \lim_{r\to\infty} c_r=\left(\sum_i x_i\right)x. $$ 证明留作习题。而我们其实只关心节点之间的中心度的相对大小，所以 $x$ 可以随便乘个系数。我们令 $|x|=1, x_i>0$，然后定义 eigenvalue centrality (Katz centrality):

$$ c_E(u)=x_u. $$

PageRank centrality

这是 Google 的网页排序指标。我们假设一个网络中，网页（顶点）$u$ 有 $x_u$ 的人在访问。下一时刻，有一部分人会从其他页面跳转而来。跳转的概率是 $\alpha$，等概率跳转到该页面连接的其他页面。则跳转到 $u$ 的人数是： $$ \alpha\sum_{v:(v,u)\in E}\dfrac{x_v}{k_v^{\rm out}}. $$ 此外，还会有一些新人到来，这部分是个常数 $\beta$. 于是有 $$ x_v=\alpha\sum_{u:(u,v)\in E}\dfrac{x_u}{k_u^{\rm out}}+\beta. $$ 用 $D$ 表示出度矩阵，$\mathbf{1}$ 为 $n\times 1$ 的全 $1$ 向量，有 $$ x=\beta(I-\alpha D^{-1}A)^{-1}\mathbf{1}. $$ 请自行证明那个矩阵可逆。

HITS (hubs and authorities)

HITS (Hyperlink-Induced Topic Search) 与 PageRank 算法一样，也是一种用于对网页进行排序的算法。

网页有两个功能：hub 和 authority。Hub 是网站导航方面的功能，比如臭名昭著的 hao123，authority 是真正的内容，比如我这篇文章（？）。我们给每个节点 $u$ 两个中心性：hub centrality $h_u$ 和 authority $a_u$. 我们希望：

  • 被高 $h$ 的节点指向，说明内容质量 $a$ 高
  • 指向高 $a$ 的节点，说明索引质量 $h$ 高

有了！ $$ \begin{align} h_u&=\alpha\sum_{v:(u,v)\in E}a_v,\\ a_v&=\beta \sum_{u:(u,v)\in E}h_u. \end{align} $$

写成矩阵就是 $$ \begin{align} h &= \alpha Aa,\\ a &= \beta A^Th. \end{align} $$

然后 $$ \begin{align} AA^Th&=\dfrac{1}{\alpha\beta} h,\\ A^TAa&=\dfrac{1}{\alpha\beta}a. \end{align} $$

$h$ 是 $AA^T$ 的特征向量，根据 Perron-Frobenius 定理，要想 $h$ 是正的，他只能是最大特征值的特征向量，这个最大特征值就是 $\dfrac{1}{\alpha\beta}$。$a$ 同理。给出合适的归一化条件，就可以求出 $h$ 和 $a$。

Network Cohesion

团（clique）是全连接子图。

核心（core）：$k$-core 表示子图内每个顶点的度都不小于 $k$（只统计内部边）

我们发现有一个有趣的性质：如果 $(u,v)$ 和 $(u,w)$ 都是边，往往 $(v,w)$ 也是边（共同好友），这一性质叫过渡性（transitivity）。我们想要引入聚类系数（clustering coefficient）来刻画过渡性。

我们称 $uvw$ 是长度为 2 的闭合路径，如果 $(u,v),(u,w),(v,w)$ 都是边。定义聚类系数 $$ C=\dfrac{\sharp{\text 长度为 2 的闭合路径}}{\sharp{\text 长度为 2 的路径}}. $$

物以类聚（homophily）

鲁迅曾经说过，物以类聚，人以群分。在图中，属性相似的节点可能更倾向于互相连接，这一特点就叫 homophily。

属性向量

我们要构造 $y$ 和 $z$. 首先每个节点 $u$ 都有一个属性 $x_u$。设一共有 $m$ 条边，我们把 $(u,v)$ 和 $(v,u)$ 看成同时存在的两条边，这时就有 $2m$ 条边。我们给边编号 $j=1,\cdots,2m$，边 $e_j=(u,v)$，则 $y_j=x_u,z_j=x_v$.

例如 $E={(1,2),(1,3)}$, 则 $y=(x_1,x_2,x_1,x_3),z=(x_2,x_1,x_3,x_1)$. 他们都是 $2m$ 维向量。显然 $y$ 和 $z$ 的变化趋势是否相同可以反映 homophily。下面介绍两种衡量方式：assortativity coefficient 和 modularity。

Assortativity coefficient

定义 assortativity coefficient 为 $y,z$ 的相关系数： $$ r=\dfrac{{\rm Cov}(y,z)}{\sqrt{{\rm Var}(y){\rm Var}(z)}}, $$ 容易验证，可以展开为如下形式： $$ r=\dfrac{2\sum_{(u,v)\in E}x_ux_v-2m\bar x_E^2}{\sum_{u\in V} k_u x_u^2-2m\bar x_E^2}. $$ 其中 $m$ 为边数，$k_u$ 为 degree, $\bar x_E=\dfrac{1}{2m}\sum_{u\in V} k_u x_u$.

我们有 $-1\leq r\leq 1$. $r$ 越大越说明鲁迅说的对。$r$ 要是 $-1$ 则恰恰相反。

Modularity

Assortativity coefficient 适合连续属性，而它更适合离散的分类属性。假设某个 factor 有 $I$ 个取值，例如三个不同的班级，$x_u$ 采用 one-hot 编码，即 $u$ 如果属于第 $i$ 类，则 $x_u^{(i)}=1$, 否则 $x_u^{(i)}=0$. 类似地有 $y^{(i)},z^{(i)}$ 都是 $2m$ 维向量。定义 modularity: $$ Q=\sum_{i\in I} {\rm Cov}(y^{(i)},z^{(i)}). $$ 将其用 $x$ 表示可以得到 $$ \begin{align} Q&=\sum_{i\in I}Q^{(i)},\\ Q^i&=\dfrac{1}{m}\sum_{(u,v)\in E}x_u^{(i)}x_v^{(i)}-\left(\bar x^{(i)}_E\right)^2. \end{align} $$ $Q$ 越大越好，但 $Q\leq 1$（自行证明）。

Agglomerative Clustering

聚类是机器学习中的一个重要话题。这里我们简要介绍以下 agglomerative clustering。它是层次聚类中自底向上的算法（还有一种自顶向下的 divisive clustering）。Agglomerative clustering 可以采用许多不同的方式来度量两个聚类的相似度，这里介绍的是使用 modularity $Q$ 作为相似程度的实现。

  • 首先假设每个节点都是单独的一类；
  • 考虑合并其中两个节点，有 $n(n-1)/2$ 种合并方式，穷举选择使 $Q$ 最大的一种；
  • 现在只剩 $n-1$ 个类别了，重复上述步骤，选择一种使得 $Q$ 最大的方式合并其中两个类别；
  • 重复直到只剩一类；
  • 合并的过程可以画出一个树形图，它叫 dendrogram。

然后就可以目测 dendrogram 来决定分几类了。

0%