基本上,图聚类和社区检测方法的目标是计算聚类。它们之间有什么区别吗?
图聚类和社区检测方法有什么区别?
没有。例如引用图中的社区检测, Santo Fortunato 最近进行的一项非常好的调查,“真实网络的这一特征称为社区结构(Girvan 和 Newman,2002 年)或聚类”。真的,进一步阐述这一点没有什么意义。我有一种感觉,在早期的社交网络分析风格论文中,网络往往很简单(没有加权),但这不是我想要争论的事情,也不重要。你的问题的答案是否定的。
在Detecting Community Structures in Networks 中,M.Newman 将图聚类定义为在计算机科学背景下定义的特定问题。
让我们考虑一些计算,可以将其拆分为几个更简单的操作。这些在我们的网络中表示为节点。链接对应于操作之间的依赖关系,即一个操作的结果需要另一个操作。问题在于将操作分布在多个处理器上,以实现并行处理目的。换句话说,我们希望将每个节点(操作)分配给特定的类(处理器),即我们希望对图进行分区。
但是,存在三个限制。首先是获取预定义的社区数量,因为处理器的数量显然是提前知道的。第二个是获得平衡的负载:我们希望每个处理器大致执行相同数量的操作。就图而言,我们希望社区包含大致相同数量的节点。第三是在处理器之间获得尽可能低的通信,因为它减慢了进程。因此,就图而言,我们希望尽量减少社区之间的链接数量。
因此,从这个角度来看,社区检测可以被认为是比图聚类更普遍的问题。第三个约束在这两个问题中都被强制执行,但是社区的数量和大小在社区检测中是先验的。
这两个不同的名称是由不同的科学家社区给同一事物起的,这取决于一个人是否愿意强调社交网络的动机。也许有人将聚类和社区检测定义为不同的东西,但大多数研究其中之一的人无法告诉你为什么他们不使用另一个术语。
如果一个大网络聚集成两部分,你凭什么保证这两部分是两个社区?两个集群的低连接并不意味着每个集群具有相似类型的节点或节点具有相似类型的连接(因此是社区)。想想社交网络图。肯定有很多社区。此外,通过聚类算法,您可以将其聚类为两部分。在这种情况下,你会称每个部分为一个社区吗?? 我的回答是否定的。因为,这两个集群可能是两个地理区域的人。然后那些肯定不是社区。
聚类算法只关心最小割,不关心节点相似度或连接相似度或密集连接。此外,在聚类算法中,应该预先定义聚类的数量。
社区检测算法,他们关心密度,他们发现网络中更密集的部分,而那些算法(我到目前为止看到的)不需要预先定义社区的数量。
但是,聚类算法可以用来寻找社区,那么,由于它不能保证每个聚类都具有良好的社区结构,因此应该仔细检查每个聚类。