融合小直径子图与顶点克隆的相关性聚类编辑：一种马尔可夫链启发式方法

《Scientific Reports》：A heuristic graph editing approach to correlation clustering with overlap

　　

摘要

相关性聚类旨在将给定图/网络的顶点集划分为若干组关系密切或足够接近的顶点，使得不同组中的元素彼此不接近。该问题之前已被建模和研究为一个图编辑问题，即聚类编辑（Cluster Editing），该模型假设关系密切的数据元素必须相邻。因此，聚类编辑问题的主要目标是通过两种主要的边编辑操作——添加和删除，将簇转变为团，以此作为识别它们的方法。聚类编辑模型存在两个问题，我们希望在本文中加以解决。首先，"关系密切"并不一定意味着"直接相关"，因此接近程度应通过相对较短的距离来衡量。基于此，我们寻求将簇转变为小直径的（子）图。直径为二和三的（子）图在聚类生物网络方面特别有效。其次，在实际应用中，一个数据元素可以属于或在多个组中发挥作用。例如，蛋白质可以具有多种功能。在某些情况下，不允许数据元素属于多个簇可能导致难以通过经典的基于划分的方法获得显著的聚类结果。我们通过允许顶点克隆（也称为顶点分裂）来解决后一个问题。本文提出了一种新颖的马尔可夫链启发式方法来处理该问题，并附带实验结果，展示了所提出的模型和算法方法在基因-功能关联以及合成网络中的有效性。特别地，所提出的启发式方法在扩展的Lancichinetti-Fortunato-Radicchi（LFR）基准测试上取得了最高的F分数。