社区发现算法总结-以新浪用户数据为例.md

根据 https://blog.****.net/itplus/article/details/9286905 整理

1 建模方法

1.1 新浪微博可用信息

• 微博内容
• 地理位置
• 毕业院校
• 标签信息
• 关注
• 粉丝

1.2 基本假设

两个微博用户之间互动越频繁，那么二者之间的社交关系越密切，而亲密的社交关系代表着潜在的兴趣关联或者较强的线下社交关系。

1.3 生成网络图

• 用户当前节点
• 想换关注的用户之间建边

这里在相互关注的用户之间建立连接关系，主要是为了简化模型，此时对应的图为无向图。当然，我们也可以采用单向关注来建边，此时将对应有向图。

2 已有算法

算法	发表年份	复杂度
CFinder	2005	-
LPA	2007	O ( m ) O(m) O(m)
LFM	2009	O ( n 2 ) O(n^2) O(n2)
EAGLE	2009	O ( n 2 s ) O(n^2s) O(n2s)
GIS	2009	O ( n 2 ) O(n^2) O(n2)
HANP	2009	O ( m ) O(m) O(m)
GCE	2010	O ( m h ) O(mh) O(mh)
COPRA	2010	O ( v m l o g v m n ) O(vmlog\frac{vm}{n}) O(vmlognvm​)
NMF	2010	O ( K n 2 ) O(Kn^2) O(Kn2)
Link	2010	O ( n k m a x 2 ) O(nk^2_{max}) O(nkmax2​)
SLPA	2011	O ( T m ) O(Tm) O(Tm)
BMLPA	2012	O ( n l o g n ) O(nlogn) O(nlogn)

质量评估
不同的社区发现算法得到的社区划分结果不同，如何评价优劣。对无向图 Newman和Girvan于2004年提出了modularity的概念。

• modularity的定义：网络中连接社区结构内部顶点的边所占的比例与另外一个随机网络中连接社区结构内部顶点的边所占比例的期望值相减得到的差值。
• 计算公式: Q = ∑ c ∈ C ( L c m − ( D c 2 m ) 2 ) Q=\sum _{c\in C}(\frac{L_c}{m}-(\frac{D_c}{2m})^2) Q=∑c∈C​(mLc​​−(2mDc​​)2)
  • m m m:图中边的总数
  • L c L_c Lc​:社区c中所有内部边的总条数
  • D c D_c Dc​:社区c中所有顶点的度之和。 D c D_c Dc​也可以写成 D c = 2 L c + O c , 其 中 O c 为 社 区 c 与 其 他 社 区 之 间 的 边 D_c=2L_c+O_c,其中O_c为社区c与其他社区之间的边 Dc​=2Lc​+Oc​,其中Oc​为社区c与其他社区之间的边

是针对无向图的，因此这里的 m 表示无向边的条数，即若节点 i 和节点 j 有边相连，则节点 (i, j) 对 m 只贡献一条边。

2.1 标签传播算法 LPA(Label Propagation Algorithm)

算法步骤

1. 为所有节点指定一个唯一的标签；
2. 逐轮刷新所有节点的标签，直到达到收敛要求为止。对于每一轮刷新，节点标签刷新的规则如下:
   对于某一个节点，考察其所有邻居节点的标签，并进行统计，将出现个数最多的那个标签赋给当前节点。当个数最多的标签不唯一时，随机选一个。

2.2 SLPA(Speaker-Listener Label Propagation Algorithm)

数值软件包(C++/Java) GANXiSw
SLPA是一种重叠型社区发现算法，其中涉及一个重要阈值参数 r r r,通过 r r r的适当选取，可以将其退化为非重叠型。算法示意图如下

SLPA引入了Listener和Speaker两个比较形象的概念。你可以这么来理解：在刷新节点标签的过程中，任意选取一个节点作为 listener，则其所有邻居节点就是它的 speaker 了，speaker 通常不止一个，一大群 speaker 在七嘴八舌时，listener 到底该听谁的呢？这时我们就需要制定一个规则。
在 LPA 中，我们以出现次数最多的标签来做决断，其实这就是一种规则。只不过在 SLPA 框架里，规则的选取比较多罢了（可以由用户指定）。
当然，与 LPA 相比，SLPA 最大的特点在于：它会记录每一个节点在刷新迭代过程中的历史标签序列（例如迭代 T 次，则每个节点将保存一个长度为 T 的序列，如上图所示），当迭代停止后，对每一个节点历史标签序列中各（互异）标签出现的频率做统计，按照某一给定的阀值过滤掉那些出现频率小的标签，剩下的即为该节点的标签（通常有多个）。
SLPA 后来被作者改名为 GANXiS，且软件包仍在不断更新中

2.3 HANP(Hop Attenuation & Node Preference)

由lan X.Y Leung等于2009年提出。核心思想

• 为各个标签引入score值来刻画其传播能力，传播能力随着传播距离的增大而减弱

• 一个节点从其邻居接收标签时，综合考虑个标签的传播能力、出现频率、度(对于带权图还可以权重)等因素。

• 接收标签规则： c n = a r g m a x l ∑ i ∈ N n l s i f i α w n i c_n=argmax_l \sum _{i\in N_n ^l} s_if_i ^{\alpha}w_{ni} cn​=argmaxl​∑i∈Nnl​​si​fiα​wni​

• score衰减规则： s n = ( m a x i ∈ N n c n s i ) − σ , 其 中 σ 为 衰 减 因 子 s_n = (max_{i\in N_n ^{c_n}}s_i)-\sigma,其中\sigma 为衰减因子 sn​=(maxi∈Nncn​​​si​)−σ,其中σ为衰减因子。当score值小于等于0时，标签停止传播。

2.4 BMLPA(Balanced Multi-Label Propagation Algrithm)

由武志昊等于2012年提出，其基本思想为：对每个节点能归属的community个数不做限制，只要求同一个节点的标签有平衡的归属系数(balanced belonging coefficient)
算法示意图如下

这里对上面的图做个简单介绍：带问号的节点是待确定标签的节点，黑色实心点为其邻居节点，它们的标签是已知的，注意标签均是由二元数对的序列构成的，序列中每一个元素的第一个分量表示其标签，第二个分量表示该节点属于该标签对应社区的可能性（或者说概率，叫做 belonging coefficent），因此对于每个节点，其概率之和等于 1。

我们按照以下步骤来确定带问号节点的标签：

1. 获取邻居节点中所有的互异（distinct） 标签列表，并累加相应的 belonging coefficent 值。
2. 对 belonging coefficent 值列表做归一化，即将列表中每个标签的 belonging coefficent 值除以 C1 （C1 为列表中 belonging coefficent 值的最大值）。
3. 过滤。若列表中归一化后的 belonging coefficent 值（已经介于 0,1 之间）小于某一阀值 p （事先指定的参数），则将对应的二元组从列表中删除。
4. 再一次做归一化。由于过滤后，剩余列表中的各 belonging coefficent 值之和不一定等于 1，因此，需要将每个 belonging coefficent 值除以 C2 （C2 表示各 belonging coefficent 值之和）。
   经过上述四步，列表中的标签即确定为带问号节点的标签。

2.5 Fast Unfolding

由Vincent D. Blondel于2008年提出，他是一种基于modularity optimization的启发式算法。

这里，我们对 Fast Unfolding 算法做一个简要介绍，它分为以下两个阶段：

1. 首先将每个节点指定到唯一的一个社区，然后按顺序将节点在这些社区间进行移动。怎么移动呢？以上图中的节点 i 为例，它有三个邻居节点 j1, j2, j3，我们分别尝试将节点 i 移动到 j1, j2, j3 所在的社区，并计算相应的 modularity 变化值，哪个变化值最大就将节点 i 移动到相应的社区中去（当然，这里我们要求最大的 modularity 变化值要为正，如果变化值均为负，则节点 i 保持不动）。按照这个方法反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止。
2. 将第一个阶段得到的社区视为新的“节点”（一个社区对应一个），重新构造子图，两个新“节点”之间边的权值为相应两个社区之间各边的权值的总和。

我们将上述两个阶段合起来称为一个 pass，显然，这个 pass 可以继续下去。
从上述描述我们可以看出，这种算法包含了一种 hierarchy 结构，正如对一个学校的所有初中生进行聚合一样，首先我们可以将他们按照班级来聚合，进一步还可以在此基础上按照年级来聚合，两次聚合都可以看做是一个社区发现结果，就看你想要聚合到什么层次与程度。

2.6 DCLP(Distance-Control Label Propagation)

算法由HANP算法简化而来，仅考虑其中的衰减因素，且用距离dis_allowed来代替 σ \sigma σ。

DCLP 算法是 LPA 的一个变种，它引入了一个参数来限制每一个标签的传播范围，这样可有效控制 Monster（非常大的 community，远大于其他 community）的产生。

2.7 AM(Adaptive-Multi)-DCLP

基于DCLP，可得到相应的自适应多级划分算法(AM-DCLP)。

• 基本思想：对原图调用DCLP算法后，若某些社区规模较大，则将它们的子图抽出来继续调用DCLP算法
• 两个控制参数：
  • maxC_allowed:社区规模的最大值
  • break_down_allowed:允许调用DCLP算法的级数

多级划分是一种朴素的思想，上述算法中的DCLP也可以换成其他的社区发现算法，不同级之间甚至不同community之间都可以根据具体特点分别调用不用的社区发现算法，以期实现更好的自适应。

2.8 DSCLP(DCLP with Shrinking Strategory)

基于DCLP算法。

• 基本思想：每次迭代DCLP之后，对形成的所有社区进行检测，若社区的规模足够大，则让其不再参与下一轮迭代。
• 参数 picked_bound:允许提前结束迭代的社区规模的下界
• 算法优点：(1)能及时终止大的社区进一步变大，防止过大的monster产生(2)小社区可以一直迭代，从而得到充分发展

3 算法中涉及到的重要问题

• 节点遍历顺序：自然顺序/随机顺序
• tie-break规则：随机/度优先
• 同步/异步模式：异步收敛更快，同步稳定且适合并行
• 迭代终止规则：迭代次数/modularity单调性/社区规模
• monster community：如何控制规模
• 串行/并行实现：重构串行结果，并行效率

参考

**** 社区发现算法