论文标题
多样性和多样性：在完整签名的图上分析相关聚类问题的最佳解决方案空间
Multiplicity and Diversity: Analyzing the Optimal Solution Space of the Correlation Clustering Problem on Complete Signed Graphs
论文作者
论文摘要
为了研究现实世界系统，许多应用作品通过签名的图表对其进行建模，即边缘被标记为正或负面的图形。当可以将其划分为多个模块时，这种图被认为是结构平衡的，因此模块的（分别为swee）位于模块内部（分别为ress。）。如果不是这种情况，作者会寻找与这种平衡最接近的分区，一个称为相关聚类（CC）的问题。由于CC问题的复杂性，标准方法是找到一个最佳分区并坚持下去，即使可能存在其他最佳或高分解决方案。在这项工作中，我们在合成完整图的集合中研究了CC问题最佳解决方案的空间。我们从经验上表明，在某些条件下，可以有许多签名图的最佳分区。其中一些非常不同，因此在系统上提供了不同的观点，如在一个小型现实图表上所示。这是一个重要的结果，因为这意味着人们可能必须找到CC问题的几种最佳解决方案，以便正确研究所考虑的系统。
In order to study real-world systems, many applied works model them through signed graphs, i.e. graphs whose edges are labeled as either positive or negative. Such a graph is considered as structurally balanced when it can be partitioned into a number of modules, such that positive (resp. negative) edges are located inside (resp. in-between) the modules. When it is not the case, authors look for the closest partition to such balance, a problem called Correlation Clustering (CC). Due to the complexity of the CC problem, the standard approach is to find a single optimal partition and stick to it, even if other optimal or high scoring solutions possibly exist. In this work, we study the space of optimal solutions of the CC problem, on a collection of synthetic complete graphs. We show empirically that under certain conditions, there can be many optimal partitions of a signed graph. Some of these are very different and thus provide distinct perspectives on the system, as illustrated on a small real-world graph. This is an important result, as it implies that one may have to find several, if not all, optimal solutions of the CC problem, in order to properly study the considered system.
