Fast Overlapping Communities Search

sndnyang

2016-5

基本定义

给定图G(V, E)

目标: 找到一簇子图， 每个子图都是一个社区（community) 即 \(S = \{S_i | S_i \subset V \}\)

社区（community)： 子图中任意点在该子图中的连通性 高于 非社区的子图

定义

  • 包含点 \(v_j\) 的社区的集合为： \[ S(v_j) = \{S_i | v_j \in S_i \land S_i \in S \} \]
  • disjoint cluster: \(|S(v_j)| \le 1\)
  • overlapped cluster: \(|S(v_j)| > 1\)
  • \(N(v_j)\) 为 \(v_j\) 的邻接点
  • \(N_i(v_j)\) 为 \(v_j\) 在社区 \(S_i\) 的邻接点， 即 \[ N_i(v_j) =\{v_k | (v_j, v_k) \in E \land v_k \in S_i \} \]

新定义

社区连通性 community connectedness, 即点 \(v_j\)在社区\(S_i\)邻点超阈值个数 除以 该社区点数, 代表 点对应社区的归属性。

\[ \zeta^i_j = \frac{|N_i(v_j)|-K+1}{|S_i| - K} if |N_i(v_j)| > K, else, 0 \]

邻接连通性 neighborhood connectedness， 即 点 \(v_j\)在社区\(S_i\)邻点数 除以 \(v_j\)的总邻点数， 代表 点加入新社区的可能性

\[ \xi^i_j = \frac{|N_i(v_j)|}{|N(v_j)|} \]

外围结点 peripheral node: \(v_i\)的在社区内的邻接点

\[ Added_i = \{v_k|v_k \in N(v_i) \land v_k \in S_i \}, \forall S_i \in S^l \]

步骤

示意图

1 2

3 4

初始化

相重删除

几乎相重(near-duplicate)社区定义

对两个社区\((C, C^{'})\), 定义社区相似度：

\[\psi(C, C^{'}) = \frac{|C \cap C^{'}|}{min(|C|, |C^{'}|)}\]

图示: duplicate

意义

  1. 去重后， 计算量减少
  2. 防止两种连通性分数的分布出现不需要的偏斜(undesirably skewed)

说明

对点\(v_i\)为索引的社区\(S_i\)，仅需要与该社区内其他点为索引的社区进行比较， 可有效节省时间。

计算点与社区间连通性

步骤

  1. 对所有社区里的所有点 \(V_j\), 计算相应的
    1. 社区连通性 \(\zeta^i_j\)
    2. 邻接连通性 \(\xi^i_j\)
  2. 将(0, 1] 区间划分为 \(max(20, N(v_j))\) 块， 每块初始化为0.
  3. 根据连通性分数， 统计各区间 分值的个数。（两种连通性分开统计）
  4. 标记 最右的非0元， 并开始向左遍历， 直到：
    1. 遍历完毕 或
    2. 遇到某区间，<=标记值(最右非零元)， 且<=左边区间值， 这个值选为 阈值 stay cut-off of

示意图

select
select

最右的非零元为 第14位, 向左扫描， 第11位的值小于第14位且小于第10位， 因此选择第11位

代码

for(j = buck-1 ; j > 0; j--){
    if(network[i].bcount[j]){
        mbuck = j;
        break;
    }
}

min = network[i].bcount[mbuck];
for(j = mbuck-1 ; j > 0; j--){
    if(network[i].bcount[j] < min)
        min = network[i].bcount[j];
    if(network[i].bcount[j] == min && network[i].bcount[j] <= network[i].bcount[j -1]){
        network[i].bucket = j + 1;
        break;
    }
}
if(j == 0)
    network[i].bucket = 0;

排除阶段

leave phase

对各个社区\(S_i\) 进行如下操作：

  1. 遍历外围结点 \(v_k \in Added_i\), 若社区连通性分数 \(\zeta^i_k\) 比留存阈值低, 则排除出 \(S_i\)。
  2. 若更新后的\(S_i\)社区内 点的个数 <= K， 则\(S_i\)不满足社区的条件， 取消\(S_i\)社区。

注： > Removal of only peripheral nodes ensures that nodes that form the core of a community are never eliminated

扩展阶段

expand phase

对每个社区\(S_i\)， 从外围点\(Added_i\)向它的邻点\(v_j\)进行扩展。

扩展需要满足以下条件：

  1. 该点未入 \(S_i\)社区
  2. 该点选入 \(S_i\)社区的可能性高（即 邻接连通性 \(\xi^i_j\) 高于选中阈值 join cut-off ）

join cut-off 选中阈值的计算方式与 stay 相同

代码描述

参考链接

focs-code

focs-c++

分析

论文总结

优点

  1. 速度非常快
  2. 思想直观简洁

时间复杂度：

\[O(m+nl^2 + nl^3 + nl^3) = O(m + nl^3) \approx O(m+n)\]

  1. l be the average number of communities per node, 点平均所属社区个数（或邻点个数）
  2. m 边数
  3. n 点数

实验时间

runtime
runtime

实验准确度

nmi
nmi

NMI

\[ NMI(C_A, C_B) = \frac { -2 \sum^{C_A}_{i=1}\sum^{C_B}_{j=1} C_{ij} log( \frac{C_{ij}N}{C_{i.} C_{.j}} ) } { \sum^{C_A}_{i=1}{C_{i.}log(\frac{C_{i.}}{N})} + \sum^{C_B}_{j=1}{c_{.j} log(\frac{c_{.j}}{N})} } \]

  1. Given two partitions A and B of a network
  2. C be the confusion matrix, \(C_{ij}\) the number of nodes in common by community i in A and community j in B
  3. $C_A(C_B) number of clusters in partition A(B)
  4. \(C_{i.}(C_{.j})\) the sum of elements of C in row i(column j)
  5. N number of nodes of the network

问题

阈值选择方法

有点奇怪

The proposed cut-off selection method has been chosen after observing the score distributions.
It helps in selecting communities with near-best connectivities

  1. 如何解释
  2. 极端情况，最右边的非零元就是最小值bucket-case

社区个数有限

maximum number of communities that can be detected by this method is equaltothenumberofnodesinanetwork

因为 初始化后， 只有删除社区， 没有添加新社区

Orkut 社区个数是点数的两倍有余

如果能合理地添加新社区， 也许可以作为很好的 动态图的方法

顺序会影响

在去重与排除两个阶段， 遍历的次序会有小的影响

改进方案

谢谢