网络中重叠社区检测：现有技术和比较研究

lecea

网络中重叠社区检测：现有技术和比较研究

论文标题：Overlapping Community Detection in Networks: the State of the Art and Comparative Study
论文作者：Jierui Xie, Stephen Kelley, Boleslaw K. Szymanski
论文链接：
未删减版论文报告：）

本文主要的贡献：
1）介绍了重叠社区检测的背景知识；
2）回顾了多种重叠社区检测算法并对其进行了分类解释；
3）给出了两种社区检测质量度量的方法；
4）提出了社区检测基准的最新技术；
5）通过合成网络和真实的社交网络对上述的算法进行测试；
6）最后综合考虑各种算法在社区级和节点级的检测性能得出结论并提出现有算法中存在的问题。

背景

        社区（模块化结构）是现实世界社交网络的重要属性。现有的社区检测的技术有：随机游走、频谱聚类、模块最大化、微分方程和统计力学等。社区检测中的重点是确定不相交的社区。但是，由于社交网络中的一个人可能有多个社区成员资格，所以，本文提供了关于识别一个节点属于多个集群的重叠社区检测算法的最新技术回顾。
        符号表示：

算法

        本文提供了多种不同算法的比较，根据如何识别社区分为了五类，在后面进行合成网络和真实的社交网络测试的算法有十四个。现在对这十四个进行整体分类，附件详细介绍每一种。

评价标准

        不相交的社区检测评价标准已经提出过很多，只有少数措施适合于重叠的社区。最常用两种方法是：标准互信息(NMI)和Omega指数。
一、NMI

二、Omega指数

基准

        LFR基准：引入网络的异质性和社区大小分布。通过对节点的出现添加属性系数，该系数定义为其中pk是共同出现k次的节点i和j的连接概率，是节点i和节点j的相似度，aic是社区c中节点i的模糊隶属度。换句话说，边缘存在的概率不仅取决于节点i和j在一起出现的社区的数量，而且取决于它们对这些社区的隶属程度。

合成网络测试

        收集和测试比较了十四种算法在LFR网络上的性能，如表I所示。

        重叠度由两个参数确定：On(重叠节点的数量)，Om(每个重叠节点所属的社区的数量)。On设置为节点总数的10％和50％，分别表示低和高重叠密度，表示重叠节点的重叠多样性。
一、μ、n和Om的影响
        首先研究了由NMI测量的性能随着图1中不同网络大小(n)和体内强度(μ)的成员数Om从小值到大值（即2到8）的变化而变化。

图一

        由图可知，一方面，μ的值越大，检测算法产生的结果越差（图1中的红色曲线<蓝色曲线）。这对于大多数算法都是如此，唯一的例外是NMF；另一方面，将网络大小从1000增加到5000通常有略微更好的性能（图1中的方形>点），除了EAGLE、NMF和UEOC之外。对于iLCD和Link，观察到性能略有波动。 随着重叠的多样性增加（即Om变大），除了OSLOM和UEOC之外，检测性能通常以中等速率衰减。
二、社区大小的范围和重叠密度的影响
        我们评估了On和社区大小的范围对n = 5000和μ= 0.3的网络上的每个单独算法的影响，NMI的结果显示在图2中。

图二

        对于所有算法，高重叠密度（即红色曲线On=50％）情况下，检测的性能一致且显著下降。但是，在低重叠密度的情况下，小社区的大小范围和大社区的大小范围之间的性能差异（具有相同颜色的两条曲线之间的间隙）更大。而且，对于具有小社区大小s=(10,50)的网络的NMI通常高于具有大社区大小范围b=(20,100)的网络（图2中的点>正方形）的网络。由此可见，众所周知的分辨率限制在这里不起作用，因为所有测试的算法既不基于模块化也不基于扩展模块化。由CFinder、LFM、Link、MOSES、Game、iLCD、CIS和OSLOM算法可以证明，其在小和大社区大小的范围之间具有显著的性能差距，在两个测试范围内只有很小的性能差异，我们还得出结论，社区大小范围对包括SLPA、COPRA、EAGLE和GCE在内的算法的影响有限。
三、社区检测的排名
        对不同的重叠密度和社区大小范围进行了比较。由NMI和Omega指数针对n=5000和μ=0.3测量的性能在图3和图4中表示。

图三

图四

        表II中总结的是图3中的低重叠密度情况的结果。

        表III中总结的是图4中的高重叠密度情况的结果。

        如表所示，对于(RSsNM,RSsOmega)，在前七个算法中，这两个排名，有4对匹配On=10％，5对匹配为On=50％；对于(RSbNM,RSbOmega)则更多，On=10％和On=50％都有6对匹配。这表明NMI和Omega指数在一定程度上提供类似的总体评价。
        基于这四个排名，我们进一步导出平均排名RS*NMI,Omega作为整体社区检测的性能，分别列在表II和表III的倒数第二列。在这两个最终排名中，对于低重叠密度网络，前七个算法是基于代理的算法（SLPA、Game和COPRA）和基于本地扩展的算法（GCE、OSLOM、CIS和LFM），参见图3。对于高重叠密度网络，基于代理的算法保持在前七个，连同表示模糊算法的MOSES，表示派系过滤算法的CFinder，表示链接分割的Link，参见图4。然而，对比图3和图4，低重叠密度网络显示出优异的性能，而高重叠密度网络的性能实际上相当低的事实，可以得出结论：对于具有高重叠密度和高重叠分集的网络，所有算法尚未实现令人满意的性能。
四、比较LFR中检测到的社区规模分布
        为了验证前面得到的排名，给出了社区规模（CS）的分布与已知的地面实际情况进行比较。这里只提供n=5000，μ=0.3，On=10％的分析（相应的排名是表II中的RSbNMI）。

        如图5所示，在地面真实分布情况下，SLPA、GCE和NMF的社区大小分布是单峰分布的，而且单一的峰值是CS = 20。这解释了为什么它们在排名RSbNMI方面表现良好。LFM和MOSES在CS = 5附近具有峰值，性能较低。

        如图6所示，OSLOM、Game、COPRA、CIS和CFinder算法的特征是双峰分布，在CS=1~5处具有峰值，这意味着算法找到大量的小社区。

        如图7所示，EAGLE、UEOC、iLCD的分布大多移动在预定范围20~100之外。社区大小的分布可以用来解释性能和排名，具有这种分布的算法创建了相对较小的社区，所以性能不好。
五、识别LFR中的重叠节点
        社区重叠表现为存在具有多个社区成员资格的节点，称之为重叠节点，识别重叠节点的能力对于评估社区检测算法的准确性是至关重要的。像NMI和Omega指数这样的措施只关注于提供算法精度的总体度量，但这些措施无法准确地描述节点级别发生的情况。定义：Odn为检测到的重叠节点的数量，Odm为检测到的成员的数量。注意：单独的重叠节点的数量Odn不足以准确地量化检测性能，因为它包含正的正样本(TP)和正的负样本(FP)。为了提供更精确的分析，我们认为重叠节点的识别是二元分类问题。只要Om>1或Odm>1，节点就被标记为重叠，否则标记为不重叠。使用F-分数作为检测精度的度量，F-分数定义为其中recall是正确检测的重叠节点的数量除以重叠节点的真实数量On，precision是正确检测的重叠节点的数量除以检测到的重叠节点Odn的数量。F-分数考虑检测的数量和质量之间的平衡，并且分别达到其在1和0处的最佳和最差值。
        图8和图9显示了对于不同的参数设置得到的F-分数、precision和recall。

图8

图9

        一般来说，在低和高重叠密度，算法在小社区上获得更好的F-分数。但是，对于各种算法，原因是不同的。例如，EAGLE在小社区的F-分数的增加是由于recall的增加（见图8中(c)和(f)所示），而iLCD的增加主要是由于precision的增加（见图8中(b)和(e)所示）。此外，F-分数通常随着重叠分集Om的增加而适度地衰减。显然，Om对OSLOM具有很大的影响，对于大的Om具有快速下降。SLPA是唯一一个在低重叠密度情况下与Om具有正相关关系。
        实验还揭示了一些算法的precision和recall的不平衡，部分是由于过检测（检测到比所存在更多的重叠节点）或欠检测（仅识别非常少的重叠节点）。极端的例子是EAGLE和Link，尽管EAGLE实现了非常高的检测精度（见图8中的(b)和(e)所示），但是它遭受欠检测，仅识别非常少的重叠节点（从图10中可以看出），得到低的recall得分，结果导致低的F-分数（见图8中的(a)和(b)所示）；对于Link，即使它具有非常高的recall（见图8中的(c)和(f)所示），但是它的F-分数较低，这是因为Link遭受过度检测，声明了比预期更多的重叠节点（从图10中可以看出）。

图10

        关于不同社区大小范围的F-分数的排名表示在表IV和V中，RSsF和RSbF对应不同的重叠密度情况，RS*F是两个社区大小范围的平均排名。

        为了便于比较，将RS*F复制到表II和III中。清楚地显示，在表II中，社区质量等级RS*NM,Omega和节点质量等级RS*F可能有完全不同的性能表现。对于低重叠密度情况（如表II），在检测社区中具有低排名的算法在识别重叠节点时，实际上可以具有很好的性能（例如CFinder，iLCD和MOSES），而高排名的算法，可能分别由于欠检测和过检测而表现不好（例如GCE和CIS），还有些则均具有非常稳定和良好的性能（SLPA）。这些观察表明，如果这些算法应用在重叠社区检测，旨在识别具有多个社区成员资格的节点，需要仔细地处理具有高NMI或Omega指数的算法，防止出现欠检测和过度检测情况。对于高重叠密度情况可以得出类似的结论。
六、最终排名
        两种类型的排名提供了补充信息，排除过度检测和欠检测情况，综合考虑RS*F和RS*NMI,Omega的前七位得出结论：
（a）对于低重叠密度网络，SLPA、OSLOM、Game和COPRA提供比其他测试算法更好的性能；
（b）对于高重叠密度网络，SLPA和Game提供更好的性能。

现有算法中存在的问题及未来研究的方向

        测试结果表明在这样的网络中的检测仍然存在没有完全解决的问题。
一、算法可能对一些特定的结构敏感
        例如，只有SLPA，LFM，CIS和Game在具有高度稀疏结构的网络（例如P2P）中具有令人满意的性能，所以需要研究出对于任意的网络结构都能够具有稳定高效的算法。
二、一些算法倾向于过度检测重叠
        如LFR网络的情况。CIS和Link在测试中性能低，因为他们发现相对于其他算法所标识的节点，有太多的重叠节点或成员资格。故可以在避免过度检测方面继续研究。
三、大多数算法未考虑权重
        大部分算法针对的是未加权网络。但是，在许多应用中，权重具有重要的信息。明确考虑权重并允许重叠的算法（例如CPMw和SLPAw）预计比其他算法具有优势。
四、两个基本问题
        何时应用重叠方法和重叠有多重要。关于重叠的必要性的讨论在很大程度上尚未探讨。
五、一种验证重叠的方法
        对于A和B两个集合，A∩B与集合A-B和B-A之间的相似性高于A-B和B-A之间的相似性。

结论

        回顾了大量的社区检测算法以及质量度量方法和几个现有的基准。执行了多次测试，包括不同的网络结构和不同程度的重叠。质量评估在社区级别和节点级别上分别执行，结果表明，在具有高重叠密度和高重叠多样性的网络中的检测仍然具有改进的空间。