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.

 

Leave a Reply

Your email address will not be published. Required fields are marked *