重叠社区检测基础算法_重叠社团检测算法

1.思维导图

2.算法详解

1)CPM算法

（1）算法思想

假设社区由完全连接的子图的重叠集（团）构成，并通过搜索相邻的团来检测社区。

首先识别网络中所有大小为K的团，一旦这些被识别出来，就会构建一个新的图，将每个团看成一个节点。

如果两个代表K-团的节点共享K-1个成员，则连接两个节点。

新图中的连接组件确定了哪些派系组成了社区。由于一个节点可以同时在多个K-团中，社区可能是重叠的。

CPM适用于具有密集连接部分的网络。且K的取值一般在[3,6]时效果最好。

这里要推荐一下大佬整理的，清晰易懂。

【社区发现】重叠社区发现CPM算法 (qq.com)

（2）优缺点

优点：简单易于理解

缺点：CPM算法更像是模式匹配，不是寻找社区，因为他们旨在找到网络中特定的、本地化的结构。

2）LINK算法

（1）相关概念 

a.层次的聚类方法（Hierarchical Clustering），从字面上理解，其是层次化的聚类，最终得出来的是树形结构。专业一点来说，层次聚类通过 计算不同类别数据点间的相似度 来创建一棵有层次的嵌套聚类树。

层次聚类的好处是不需要指定具体类别数目的，其得到的是一颗树，聚类完成之后，可在任意层次横切一刀，得到指定数目的簇。

b.单链接层次聚类

根据聚类簇之间距离的计算方法的不同，层次聚类算法可以大致分为：单链接（Single-link）算法，全链接算法（complete-link）或均链接算法（average-link）。单链接算法用两个聚类簇中最近的样本距离作为两个簇之间的距离；而全链接使用计算两个聚类簇中最远的样本距离；均链接算法中两个聚类之间的距离由两个簇中所有的样本共同决定。

 

（2）算法思想

通过划分链接而不是节点来发现社区结构。如果链接到他的链接放在多个集群中，则原始图中的节点称为重叠。

链接是通过边缘相似度的层次聚类来划分的。给定节点k上的一对链接和，可以通过定义为的Jaccard索引计算相似度。

 其中 Ni 是节点 i 的邻域，包括 i。 然后使用单链接层次聚类来构建链接树状图。 在某个阈值处切割此树状图会产生链接社区。 

（3）优缺点

优点：看起来清晰

缺点：不能保证该算法比基于节点的检测有更高质量的检测，因为该算法的一些定义还比较模糊。

3）LFM算法

算法思想

LFM算法是将社区从随机种子节点扩展为自然社区，直到适应度函数局部最大，和分别是社区c的内部和外部的总度数，是控制社区大小的分辨率参数。

 

在找到一个社区后。LFM会随机选择另一个尚未分配到任何社区的节点来发展一个新社区。LFM很大程度上取决于分辨率参数

 4）FCM算法

模糊社区检测算法量化了所有节点对和社区之间的关联强度。在这些算法中，每个接待你计算一个软成员向量或归属因子。

缺点：需要确定成员向量的维数k。该值可以作为算法的参数提供，也可以从数据中计算出来。

5）COPRA算法

算法思想

COPRA算法在执行之初会为网络中每一个节点设置一个唯一的社区编号，一般这个社区编号就是节点的自身的ID；

之后，节点会根据自己的邻居节点的社区分布决定自己的社区，简单的来说就是自己的邻居节点倾向于选择哪个社区，自己就选择哪个社区。

算法在执行时会使用隶属度（Belonging Coefficient）来帮助节点决定选择哪一个社区。如果节点对于邻居节点所在社区的隶属度都低于阈值，那么节点就随机选择一个社区；

最后，算法会根据一些条件来决定是否停止算法。

停止条件一般分为两种：第一种是连续两次迭代社区标签数量相同；第二种是连续两次迭代社区内节点数目不变
原文链接：https://blog.csdn.net/u010658028/article/details/80352437

3.算法比较

1）评价标准

NMI：NMI(Normalized Mutual Information)标准化互信息，常用在聚类中，度量两个聚类结果的相近程度。是社区发现(community detection)的重要衡量指标，基本可以比较客观地评价出一个社区划分与标准划分之间相比的准确度。NMI的值域是0到1，越高代表划分得越准。

2)相关算法时间度

 3）不同参数下社区检测排名

 

 参考文献：Overlapping Community Detection in Networks: The State-of-the-Art
and Comparative Study