A Dynamic Algorithm for Local Community Detection in Graphs--阅读笔记
-
Abstract *
-
Introduction *
-
Contribution*
-
Definitions and Related Work*
Fixed-state greedy seed set expansion mechanism. -
动态种子集合扩展机制
- 算法动机
- 算法总体架构概述
- 算法细节描述
Abstract
- 背景：众多的数据集均被以展示潜在模式、趋势以及异常行为的方式呈现出来。
- 目标：通过在图中识别出高度关联的群体——即所谓的种子集扩展（seed set expansion），从而确定一组初始节点（seed vertices）对应的最优局部社区（local community）。
- 传统方法：针对静态网络而言，在其框架下应用贪婪（greedy）与凝聚（agglomerative）方法来计算种子集扩展。
- 创新方法：本研究针对动态网络提出了一种新的动态种子集扩展算法，在观察到底层图形发生演变的过程中持续更新相应的社区结构。
Introduction
-
全局社区检测（Global community detection） : 将整个图形分成几组，现有的算法：
- 随机游走法（random walk methods）；
- 谱分割（spectral partitioning）；
- 标签传播（label propagation）；
- 贪婪聚集算法（greedy gglomerative algorithms）；
- 分裂算法（divisive algorithms）；
- 团聚渗透（clique percolation ）；
-
种子集扩展（ seed set expansion） ：检测与种子顶点相关的局部社区。
-
种子顶点（seed vertex）：可被视为一组感兴趣的顶点集合。
-
静态种子集扩展：每一次均基于固定不变的基础图展开。
-
动态种子集扩展：通过根据图形的变化自动更新相应的社区结构来实现动态性的种子集扩展。
Contribution
- 该贪心种子集扩展算法；
- 显著提升了相较于静态算法重新计算时的表现；
- 应对不同规模的数据批次更新，并具有良好的可并行性。
Definitions and Related Work
该无向网络由节点集合V和边集合E构成；每条边(u, v, w)属于E；其中w代表边(u, v)的权重。
-
K_{in}^C：表示在社区C中的所有边的权重和，如式(1)：
-
K_{out}^C：表示属于社区C的所有边权重之和的一个顶点不参与计算的部分权重总和，请参考式(2)所示：
- 模块度（Modularity）：一种用于评估社区质量的关键指标Q(C), 其本质上是一种适应性函数(fitness function)，具体内容可参见式(3)：
- 电导（Conductance ）：这一指标主要用来衡量网络分区效果或各分区之间连接密度的变化情况, 如所展示于式(4)中：
- 重叠社区检测（overlapping community detection） 是一种专门针对部分重叠网络结构进行分析的有效方法, 其应用实例可见于式(5)：
-
静态贪婪算法及其种子集扩展策略
算法的核心思想在于通过迭代地引入邻居节点以最大化社区C的适应度函数。在这一过程中，在每一步迭代中都会选择一个具有最高适应度值的新邻居节点进行连接操作。当所有未被加入到社区C中的节点均无法进一步提升其适应度函数时（即不再存在比现有成员具有更高适应度值的外部节点），该算法终止运行。伪代码如下：
参数说明：
- seed：starting set of seed vertices;
- fit(C)：The fitness metric for a community C;
- Nb(C)：The Nb(C) represents the set of vertices excluding those within the community who have at least one connection to members within Nb(C).
Dynamic seed set expansion algorithm
Motivation
一个简单的动态种子集扩展算法：
基于静态种子集的扩展算法1用于确定初始图G中的初始社区C；将图形更新表示为(u,v,\Delta w)的形式,其中u, v为端点,\Delta w代表增减的边权值;当添加新边时,在不存在的新边上分配权重;而当删除一条边时,将其权重设为零;更新后计算网络中每个节点在社区内外适应度得分以判断其归属情况.
- 一条更新的边中包含\Delta w为正值的情况：此时若u属于集合C而v不属于集合C时，则需要分别计算社区融合后的适应度值f_{it}(C \cup v)以及单点适应度值f_{it}(C \setminus u)随后根据两者的结果决定哪一个节点最有资格被纳入到社区中。
- 一条更新的边中包含\Delta w为负值的情况：此时若u和v都属于集合C时，则需要分别计算单点适应度值f_{it}(C \setminus v)以及两节点共同存在的适应度值f_{it}(C \setminus v, u)随后根据两者的结果决定哪一个节点最有资格被纳入到社区中。
上述简单的动态种子集扩展算法存在很多不足 ：
- 当网络结构发生变化时, 原始社群可能已经分离, 而算法未能检测到这一情况, 因为单个节点的移除未导致适应度分数的变化. 如图(a)所示, 但在当前图中, 社区实际上由两个子社群组成, 并非最佳社群布局.
- 种子集扩展的目标不仅是寻找任意一个优良社群, 而是为了特定的种子群挑选出合适的局部社群, 这与整体网络划分不同. 如图(b)所示, 该算法可能会将划分结果转移到不基于原始种子群的新区域.
- 此时的结果与种子集扩展所期望的结果不符.
本文的动机：
- 动态式种子集合扩展能够根据图形的变化实时更新社区构成，并且其计算效率显著高于完成一次完整图形重算所需的计算时间。
- 为了优化现有算法并解决其不足之处：
- 首先要求所选顶点集合满足社区划分的标准；
- 同时还需评估其作为核心节点的作用；
基于静态式种子集合扩展所得结果的基础上，
如果新的方法得到类似效果，
则可认为增量式更新算法获得了成功实现。
Algorithm Overview
为了保持以原始种子为中心的社区，这里跟踪添加顶点的顺序。
相关参数定义： * m_i：在算法1中作为第i^{th}个成员加入社区的节点被定义为集合M_i = \{m_j \mid j \leq i \}；
- k_{i,in}：该集合M_i内部边的权重总和等价于k_{i,in}^{M_i}；其具体定义如式(1)所示；
- k_{i,out}：该集合对应的边界边权重总和等价于k_{i,out}^{M_i}；其具体定义如式(2)所示；
- s_i：节点i的适应度分数值；
- 位置p(v) = i：若给定一个顶点v则称其位置为i 或者p(v) = i；
- \Theta：由所有元素m_i, k_{i,in}, k_{i,out}, s_i组成的集合\Theta = \{m_i, k_{i,in}, k_{i,out}, s_i \mid 0 \leq i \leq end\}；其中end表示该序列的最后一位置；此时对应的社区即为当前社区群组，并被称为。
算法工作原理： * 阶段A：从初始图开始，执行算法1；
- 阶段B：采用图形更新流来优化社区结构，在这一过程中需要依次增加节点以维持S_i始终保持递增趋势，并以此形成与源种子相关的社区网络。
- 在每次迭代中进行调整以使适应度分数呈递增状态。完成一批更新后,算法将识别并排除那些适应度分数下降的节点,并决定是否引入新成员以维持社区结构。
Algorithm Details
动态算法会在每次图更新后执行社区更新过程，并同时保证适应度分数序列始终保持单调递增状态。此外，在当前群体G中不存在任何额外节点会导致适应度分数上升的情况。对于每次批量处理任务时，请按照以下步骤操作：首先验证当前群体中的社区划分是否符合条件；如果满足条件，则生成新的种群；如果不符合，则对所有节点执行局部搜索操作；最后根据适应度分数重新排序资源分配并完成种群更新。
使用数值动态调整以反映网络中的内部连接与边界连接的变化。
识别所有涉及边界边的节点后进行删除判断；若发现需要删除，则社区成员需随后进行修剪处理（prune）。
遍历检查适应度分数序列是否存在持续上升趋势；若出现下降点（dip），则随后将位置截断，并将θ值设置为θ₀,i−1。
重新启动静态种子集的动态扩展过程（即算法1），以确定当前邻居节点是否应被纳入社区中。
假设： 无向边连接顶点u和v，并具有权重增量Δw；并且其权重更新过程是任意的；仅仅关注节点u的状态变化情况；
每次只修改一条边的信息；当进行批量更新操作时，在每条被修改的边上都需要重新计算步骤1至2的操作；而步骤3与4则在整个图中统一执行一次。
