Abstract

• 背景：各种大量的数据集都被表示为显示底层连接、趋势和异常的图形。
• 社区检测的目标：在图中检测出密集的群组，具体形式是种子集扩展（seed set expansion），为给定的一组节点（seed vertices）找到最佳的局部社区（local community）。
• 通常算法：在静态图中用贪婪（greedy）、聚集（agglomerative）的算法来求种子集扩展。
• 新算法：针对不断变化的动态图，提出一种动态种子集扩展的算法，随着底层图形的变化，逐渐更新社区。

Introduction

• 全局社区检测（Global community detection）: 将整个图形分成几组，现有的算法：

  1. 随机游走法（random walk methods）；
  2. 谱分割（spectral partitioning）；
  3. 标签传播（label propagation）；
  4. 贪婪聚集算法（greedy gglomerative algorithms）；
  5. 分裂算法（divisive algorithms）；
  6. 团聚渗透（clique percolation ）；

• 种子集扩展（ seed set expansion）：检测与种子顶点相关的局部社区。

  • 种子顶点（seed vertex）：a set of vertices of interest.
  • 静态种子集扩展：运行一次在不变的图上。
  • 动态种子集扩展：动态的随着图形的改变而更新社区。

Contribution

• 第一个贪心种子集扩展动态算法；
• 提高了与静态算法重新计算相比的性能；
• 可以处理各种大小的批量更新，且易于并行化。

Definitions and Related Work

一个无向图图G={V,E}，其中V为顶点集，E为无向边集，表示为(u,v,w)∈E，w为边的权重。

• KCin：表示在社区C中的所有边的权重和，如式(1)：
  KCin=∑(uv,w)∈E∣u∈C⋀v∈Cw
• KCout：表示有一个顶点不属于社区C中所有边的权重和，如式(2)：
  KCin=∑(uv,w)∈E∣u∈C⋀v∉Cw
• 模块度（Modularity）：用来衡量社区C的质量Q(C)，是一种适应度函数（fitness function），如式(3)：
  Q(C)=1∣E∣(KCin−(2KCin+KCout)24∣E∣)
• 电导（Conductance ）：用来衡量社区的割（cut），或者社区间的边，如式(4)：
  ∅(C)=KCoutmin(2KCin+KCout,2KV\Cin+KV\Cout)
• 重叠社区的检测（overlapping community detection），如式(5)：
  f(C)MONC=2KCin+1(2KCin+KCout)α

静态的贪婪种子集扩展算法

算法思想：通过迭代的添加邻居节点使得选择的适应度函数最大化来扩展社区C。当不存在使得适应度函数更大的不属于社区C的节点时，算法停止，伪代码如下：

参数说明：
- seed：initial set of seed vertices;
- fit(C)：the fitness score for a community C;
- Nb(C)：the set of vertices not in C with at least one neighbor in C.

Dynamic seed set expansion algorithm

Motivation

一个简单的动态种子集扩展算法：

1. 用静态种子集扩展算法1在初始图G中求出初始社区C；
2. 图形更新的边用式(u.v,Δw)表达，其中u，v为端点，Δw为增加或者减少的边权重。当图形增加新的边时，将一个权重赋予一条不存在的边；当图形删除一条边时，将该边的权重赋为0。
3. 当图形更新后，分别计算每个Nb(C)节点在社区C和不在社区时的适合度分数，来确定是否加入该节点。例如：
   
   1. 一条更新的边(u.v,Δw)，其中Δw>0，u∈C 和 v∉C，计算fit(C)，fit(C∪v) 和fit(C\u)，根据计算结果选择最合适的点加入社区。
   2. 一条更新的边(u.v,Δw)，其中Δw<0，u∈C 和 v∈C，计算fit(C)，fit(C\v) ，fit(C\u)和fit(C\v,u)，根据计算结果选择最合适的点加入社区。

上述简单的动态种子集扩展算法存在很多不足：

• 当图形改变时，原始社区可能已经分裂，而算法没有检测到，因为没有单个节点的删减引起适应度分数的改变。如下图(a)，但此时图中的社区实际由两个社区组成，并不是最优社区。
• 种子集扩展的任务不仅仅是找到任何好的社区，而且是为特定的种子组选择好的局部社区，与全局社区检测不同。当图形改变时，上述的算法可能会将社区迁移到不以原始种子为中心的社区，如下图(b)，此时的不是种子集扩展想要的。
  

本文的动机：

• 动态种子集扩展可以随着图形的变化而更新社区的组成，且计算的速度快于静态种子集扩展在图形更新完后的重新计算。
• 针对上述算法存在的不足进行改进，不仅要保证选择的顶点集符合社区的定义，还要考虑是否是种子的良好社区，这里采用的方法是：以静态种子集扩展找到的社区为基准，如果产生类似的结果，则任务增量更新算法是成功的。

Algorithm Overview

为了保持以原始种子为中心的社区，这里跟踪添加顶点的顺序。

相关参数说明：

• mi：表示在算法1中，作为第ith个成员加入到社区C中的节点，Mi={mj∣j≤i}；
• ki,in：Mi 的 interior edge weight sum，等价于kMii,in，定义如式(1)；
• ki,out：Mi 的 border edge weight sum，等价于kMii,out，定义如式(2)；
• si：fitness score（适应度分数）；
• position i 或 p(v)=i：If mi is vertex v, then we say that v has position i 或 p(v)=i；
• Θ：Θ={mi,ki,in,ki,out,si∣0≤i≤end}，end: the last position in the sequence Θ, Mend: the current community, which we also call C。

算法工作原理：

• 阶段A：从初始图开始，执行算法1；
• 阶段B：应用图形更新流来修改社区Θ，这里要逐个添加节点以确保Si保持单调递增，这就保证了所产生的社区与源种子相关。
• 对于每次更新，我们修改成员mi去确保对应的适应度分数是单调递增的。批量更新后，算法检测降低适应度分数的节点并将它移除。然后判断是否有节点添加进来并更新Θ。

Algorithm Details

动态算法在每个图更新之后进行社区更新，并确保适应度分数序列si保持单调增加，且在G中不存在其他额外的节点使得适应度分数增加。对于每次批量更新，执行以下步骤：

1. 值 ki,in， ki,out，si和Θ更新以反映新的内部边和边界边；
2. 检测更新边的节点进行删除判断，如果删除则社区成员需要进一步修剪（prune）并更新Θ以反映修剪结果；
3. 扫描Θ确认是否适应度分数si单调递增，如果i存在dip，则i之后的位置截断，更新Θ=Θ0,i−1；
4. 重新启动静态种子集扩展即算法1，去确定是否在Nb(C)的邻居节点需要加入社区。

假设：

• 边u,v,Δw)为无向边，且更新是随意的，仅考虑p(u)<p(v)；
• 仅考虑每次只有一条边更新；
• 如果是批量更新，则上述的步骤1和2在每条边更新时都需要执行一次，步骤3和4仅执行一次。