0%

从图划分到社区发现问题

图划分问题

图划分问题形式化

最小划分Min-Cut

Min-Cut存在的问题

Min-Cut的扩展

图划分求解算法

局部方法:KL算法

全局方法:谱划分

拉普拉斯矩阵

谱划分方法

其中,$s$ 表示划分向量,取值为 ${+1, -1}$,$k_i$ 表示节点 $i$ 的度,$\delta$ 为一个指示函数,当 $i=j$ 时, $\delta_{ij}=1$,否则为 $0$。$v$ 和 $\lambda$ 分别是拉普拉斯矩阵 $L$ 的特征向量和特征值,$a$ 表示 $s$ 在该向量下的权重系数。

推导:

$$cut = \frac 1 2 \sum_{i=1}^KW(C_i,\bar C_i) = \frac 1 2 \sum_{i=1}^K \sum_{u \in C_i, v \in \bar C_i}A_{uv} = \frac 1 4 \sum_{ij}(1-s_is_j)A_{ij}$$

注:当 $i,j$ 同类时,$1-s_is_j$ 为 $0$,不同类时,$1-s_is_j$ 为 $2$。

$$\sum_{ij} A_{ij} = \sum_{i} k_i = \sum_{ij} s_is_jk_i\delta_{ij}$$

注:当 $i=j$ 时,$\delta_{ij}=1$,$s_is_j=1$,$s_is_jk_i\delta_{ij} = k_i$,当 $i \neq j$ 时,$s_is_jk_i\delta_{ij} = 0$。

$$\begin{align}\frac 1 4 \sum_{ij}(1-s_is_j)A_{ij} \nonumber & = \frac 1 8 \sum_{ij}(2-2s_is_j)A_{ij} \\& = \frac 1 8 \sum_{ij}(s_i^2-2s_is_j+s_j^2)A_{ij} \nonumber \\& = \frac 1 8 \sum_{ij}(s_i-s_j)^2A_{ij} \nonumber \\& = \frac 1 4 s^,Ls \nonumber \end{align}$$

$$\begin{align} cut & = \frac 1 4 \left(\sum_{i=1}^na_iv_i^T \right)L\left(\sum_{j=1}^na_jv_j \right) \nonumber \\& = \frac 1 4 \left(\sum_{i=1}^na_iv_i^T L\right)\left(\sum_{j=1}^na_jv_j \right) \nonumber \\& = \frac 1 4 \left(\sum_{i=1}^na_i(L^Tv_i)^T\right)\left(\sum_{j=1}^na_jv_j \right) \nonumber \\& = \frac 1 4 \left(\sum_{i=1}^na_i \lambda_i v_i^T\right)\left(\sum_{j=1}^na_jv_j \right) \nonumber \\& = \frac 1 4 \sum_{i,j=1}^n a_ia_j\lambda_iv_i^Tv_j \nonumber \\& = \frac 1 4 \sum_{i,j=1}^n a_ia_j\lambda_i\delta_{ij} \nonumber\end{align} $$

注:$L$ 是对称阵,所以 $L$ 的不同特征值对应的特征向量正交,即 $v_i^Tv_i=1$,$v_i^Tv_j=0$,并且有$L^T=L$。

对启示的理解:当 $s$ 和 $L$ 给定后,$a_i$ 的值是恒定的,所以最小化 $cut$ 实际上就是最小化 $\lambda_i$,也就是让 $s$ 尽可能用最小的 $\lambda_i$ 对应的 $v_i$ 去表示。

社区发现问题

社区发现与图划分

社区发现与图划分的区别

模块度优化问题

模块度的定义

其中 $e_ss$ 为社区 $C_s$ 内部的边占所有边的比例,$a_s$ 为社区 $C_s$ 连接到所有社区的边占所有边的比例,$a_s$ 为所有社区连接到社区 $C_s$ 的边占所有边的比例。

模块度的性质

模块度可以理解为:社区内部的总边数与网络中总边数的比例减去一个期望值,这个期望值就是当网络为随机网络时该比例(内部边数/总边数)的大小。

直观理解:
其中 $k_i$ 代表节点 $i$ 的度,$\delta$ 为一个指示函数,当 $i,j$ 位于一个社区时, $\delta_{ij}=1$,否则为 $0$,确保公式只对 $i,j$ 位于同一个社区时求和。其中 $2m$ 表示网络中的总边数, $2m=\sum_{i,j}A_{ij}$。对于 $\frac {k_j} {2m}$ 可以理解为节点 $j$ 占总边数的比例,所以 $\frac {k_ik_j} {2m} = k_i \frac {k_j} {2m}$ 就代表着节点 $i$ 连接到节点 $j$ 的期望边数。
公式推导:
$$ \sum_s e_{ss} = \frac {\sum_{i,j}A_{ij}\delta(c_i, c_j)} {\sum_{i,j}A_{ij}} = \frac {\sum_{i,j}A_{ij}\delta(c_i, c_j)} {2m} \tag{1}$$

$$ \sum_s a_s = \frac {\sum_ik_i\delta(c_i, s)} {2m} \tag{2}$$

$$ \sum_s b_s = \frac {\sum_jk_j\delta(c_j, s)} {2m} \tag{3}$$

由 $1,2,3$ 式可得:

$$\begin{align} Q = \sum_s(e_{ss}-a_sb_s) & = \frac {\sum_{i,j}A_{ij}\delta(c_i, c_j)} {2m} - \frac {\sum_ik_i\delta(c_i, s)} {2m} \frac {\sum_jk_j\delta(c_j, s)} {2m} \nonumber \\&= \frac 1 {2m} \sum_{ij} \left(A_{ij}-\frac {k_ik_j} {2m} \right) \delta(c_i, c_j) \nonumber \end{align}$$

进一步解释:

模块度的缺陷

  1. 社区发现问题变成了一个模块度优化问题,而此问题是一个 $NP$ 难问题,求解方法只能用模拟退火、爬山算法等寻找尽可能大的局部最优解
  2. 网络存在一个固有的尺度,小于该尺度的社区无法通过模块度优化识别出来。添加可调节的参数可以识别多尺度的网络:$Q = \frac 1 {2m} \sum_{ij} \left(A_{ij}- \gamma \frac {k_ik_j} {2m} \right) \delta(c_i, c_j)$
  3. 不支持社区重叠。把指示函数修改为一个概率函数,可以在一定程度上解决不支持社区重叠的问题:$Q = \frac 1 {2m} \sum_{ij} \left(A_{ij}- \gamma \frac {k_ik_j} {2m} \right) s(i, j)$,其中 $s(i,j)$ 表示节点 $i,j$ 位于同一个社区的可能性

随机块模型


  1. 同配结构:同一社区之间的节点相连的概率较大
  2. 异配结构:不同社区之间的节点相连的概率较大
  3. 核心外围:约靠近社区总中心,社区之间的节点相连的概率较大

参考文献:
[1] 沈华伟,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程