Category Archives: Network Science

Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

什么样的聚集是好的聚集?

  1. 希望聚集内的相互连接尽量多
  2. 希望聚集内的节点与聚集外的节点之间连接尽量少

定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。

先用AGM生成一个网络:

CutPlot1

假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:

Cut值并不是一个非常好的指标,如果包含度为1的节点,那么仅仅由节点一个节点构成的聚类,Cut值为1。

另一个可能的指标是Conductance(越低越好):

phi(A) = frac{text{cut(A)}}{min(vol(A), 2m-vol(A))}

其中:

  1. cut(A)是聚集A的cut分值
  2. vol(A)是聚集A的所有节点的度的和
  3. m 是网络内边的总数

2  图谱理论(Spectral Graph Theory)和谱聚类

分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。

CutPlot1

定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差:

该矩阵有两个重要属性:

  1. 特征值都是非负实数
  2. 特征向量都是实数,并且相互垂直

一些通过线性代数可获得事实:

令拉普拉斯矩阵的特征值为lambda,特征向量为x

特征向量有两个重要属性:

  1. 是单位向量:sum_ix_i^2=1
  2. 与第一个特征向量垂直:sum_ix_icdot 1 = 0

特征值lambda _2是该表达式的最优解:

min_{x}frac{x^TMx}{x^Tx}=min_{x}sum_{i,j}(x_i-x_j)^2

因此上面的最小化问题的物理意义是将节点一部分放在<0出,另一部分放在>0处(sum_ixi=0)  ,并且使得连接两端的边尽量地小(min_{x}sum_{i,j}(x_i-x_j)^2

具体参见Rayleigh quotientFiedler vector,以及一个挺有帮助的slides

谱聚类步骤:

  1. 预处理:用拉普拉斯矩阵表示网络
  2. 分解:计算矩阵的特征值和特征向量,找到lambda_2对应的特征向量x(这样每一个节点就用一个值来表示了)
  3. 聚类:决定若干分割值,根据特征向量的值与分割值的关系,将各个节点归属到不同聚集

分割点的选择:

  1. 简单地选择0或者中位数
  2. 尝试最小化正则化的1维cut值

如果希望有多个聚集,方法有两类:

  1. 递归地进行2分聚类
  2. lambda_2lambda_3等后续特征值对应的特征向量进行K-means

From AGM to BigCLAM 网络内聚集的发现

Notes on MMDS on Coursera

Affiliation Graph Model

AGM是用于生成网络的一种模型,包括如下参数:

  1. 节点的集和V,代表网络中的各个个体
  2. 社区的集和C,代表网络中紧密相连的个体的集和
  3. 关系M,揭示网络中社区所包含的个体
  4. 对于每一个社区c,均有一个概率p_c用于生成连接

AGM连接生成:

  • 对于每一个社区c
    • 对于社区内的每一对节点对(u,v),根据社区的连接生成概率p_c来增加连接

AGMTwoC

 

AGMThreeC

总的来说,AGM生成的网络中,任意两个节点u,v之间有连接的概率为:

QQ截图20150224125316

AGM可以用来表示各种类型的网络-社区结构。


BigCLAM

对AGM中的关系M进行放松,另节点对社区的所属关系是有权重的。

用Community membership strength矩阵F来表示这种放松后的关系。矩阵中每一行代表网络中的一个节点,每一列代表网络中的一个社区,元素F_{vA}代表的是节点v对于社区A的所属权重。

对于一个社区A,生成一对连接的概率为P_A(u,v)=1-exp(-F_{uA}cdot F_{vA})

因此总的来说,生成一对连接的概率为:

P(u,v)=1-underset{cin C}{prod}(1-P_c(u,v))

= 1 - exp(-sum_{cin C}{F_{uc}cdot F_{vc}})

 = 1 - exp(-F_ucdot F_v^T)

根据如下矩阵生成网络:

QQ截图20150224132516

CMSMatrixToGraph

任务是:给定一个网络G(V,E),我们如何拟合一个举证F使得生成的网络与给定网络'最像':

QQ截图20150224133231

定义对数似然函数l(F)=log(P(G|F)) ,具体地:

QQ截图20150224133600

目标是找到矩阵F使得上述目标函数最大。

求解的方法为梯度上升:

对于矩阵中的每一行F_u:

  • 计算梯度:Delta l(F_u)
  • 更新该行:F_u += eta Delta l (F_u)
  • 如果更新后的行内有负项,将其改为0

其中eta为步长,梯度的计算方式为:

Delta l (F_u) = sum_{v in N(u)} F_v frac{exp(-F_uF_v^T)}{1-exp(-F_uF_v^T)}- sum_{v notin N(u)} F_v

 

BigCLAM成功发现了网络中的社区结构。

简化计算,可以缓存sum_{v}F_v

sum_{v notin N(u)} F_v = (sum_{v}F_v - F_u -sum_{vin N(u)}F_v)

 

References:

  • Overlapping Community Detection at Scale: A Nonnegative Matrix
    Factorization Approach by J. Yang, J. Leskovec. ACM International
    Conference on Web Search and Data Mining (WSDM), 2013.
  • Detecting Cohesive and 2-mode Communities in Directed and
    Undirected Networks by J. Yang, J. McAuley, J. Leskovec. ACM
    International Conference on Web Search and Data Mining (WSDM),
    2014.
  • Community Detection in Networks with Node Attributes by J. Yang,
    J. McAuley, J. Leskovec. IEEE International Conference On Data
    Mining (ICDM), 2013.