detection - 社区检测算法的评估指标

Question

我想在 R 中评估和比较我的社区检测算法的结果。我的算法不允许重叠，并且有一些节点没有被处理。例如，对于 Zachary 空手道俱乐部，我有 1 个节点未处理。我找到了很多指标(NMI、ARI、Modulaity(Q)、纯度、排名指数...)，但我不知道哪些是最好的。目前，我使用模块化、纯度和排名指数。

那些选择的评估指标是否足够？

例如，Rank Index 是 RI(P,R)= (a+d)/(a+b+c+d) 其中 a、b、c 和 d 是节点对的数量分别根据P和R在同一社区，根据P在同一社区但根据R在不同社区，在P给定的不同社区但在R给定的同一社区，以及在不同社区根据P 和 R，并且 P = {p1, p2, . . . , pk} 是应用于图 G =< V,E > 和 R = {r1, r2, . . . , rn} 是真正的社区结构。

那么如果我处理一个大图，我该如何计算这些值呢？我在哪里可以找到 R(真正的社区结构)？

Answer 1

您混淆了两种类型的度量:内部和外部标准，如针对聚类问题定义的(请参阅 this page)。

• 内部标准:盲目评估检测到的社区结构的质量。这意味着您没有任何可以与估计结构进行比较的引用结构。例如:模块化、电导……
• 外部标准:将估计的社区结构与引用社区结构(也称为基本事实、黄金标准等)进行比较。例如:NMI、(A)RI、纯度……

没有“最佳”衡量标准:它们各不相同，并且依赖于如何量化社区检测算法性能的不同概念。一个更相关的问题是:哪些措施适合您的情况？

确实，你列出的措施都需要对节点集进行分区。你提到你的算法忽略了某些节点，所以这可能是个问题。一个基本的解决方法是考虑每个被忽略的节点构成它自己的社区。或者，为重叠社区结构定义的某些措施能够处理这种情况。

另一个重点是您用于测试算法的数据。你有这些数据的实际社区结构吗？如果不是，那么您根本无法使用外部标准。

请注意，大多数外部标准认为社区结构只是节点集的一个分区(在数学意义上)。因此，他们依赖于引用和估计分区的比较。这是因为它们都起源于聚类分析领域。问题是他们完全没有考虑网络链接。然而，社区结构不仅仅是节点集的分区:链接在该分区上的分布方式非常重要。出于这个原因，您可能希望以更定性的方式评估您的社区结构，例如通过比较检测到的社区的拓扑属性(参见 Orman'12)。您也可以更改现有措施，使它们考虑链接(参见 Labatut'13)。并不是说我特别想引用自己，但这些论文似乎很相关。

关于这些措施的具体处理，您可能需要查看用于执行社区检测的工具的文档:其中一些与性能措施捆绑在一起。例如，如果您使用 igraph，则有一个 function just for that .