Apr, 2024

组合近似聚类删除：更简单、更快、更好

PDF
TL;DR删除最小数量的边将图划分为团体是一种 NP 困难的图聚类目标，在计算生物学和社交网络分析中具有应用。我们提供了两种先前近似算法的更严格的分析，将其近似保证从 4 改进到 3。此外，我们展示了这两种算法可以以出人意料的简单方式解除随机化，通过在辅助图中贪婪地选择具有最大度的顶点并围绕其形成一个聚类。其中一种算法依赖于解决一个线性规划问题。我们最后的贡献是设计一种新的纯组合方法来解决这个问题，在理论和实践中更加可扩展。
发现论文，激发创造
  • 参数化图聚类和边标记的更快逼近算法

    本文提供的是一种关于网络分析的图聚类框架 LambdaCC 的更快更可靠的逼近算法，其依赖于可调节参数的分辨率参数和一种新的参数化边标记问题。

    Jun, 2023

  • 最小最大相关聚类的 4 近似算法

    我们介绍了一种用于最小最大相关聚类问题的下界技术，并基于此技术提出了一种完全图的组合 4 近似算法。我们通过贪婪连接启发式算法扩展了这个算法，并在几个基准数据集上实证表明它提高了解决方案的质量和运行时间，改进了现有的技术水平。

    Oct, 2023

  • 大规模图上最大团问题的快速算法及其在重叠社团检测中的应用

    提出了一种使用新的修剪技术的确切算法，可快速在非常大、稀疏的图中找到最大团，并提出了一个快得多且提供最优或接近最优解的启发式算法，同时在网络中检测重叠社区的开发方法。

    Nov, 2014

  • 通过强三元闭包标记的相关聚类：快速近似算法和实用下界

    本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

    Nov, 2021

  • 组合分区问题算法配置的学习理论基础

    本研究提出了一种针对各种划分问题的机器学习算法，通过样本学习来获得适合特定应用场景的算法配置，同时也为算法配置的基础和学习理论的发展做出了贡献。

    Nov, 2016

  • 大规模稀疏图上最大团问题的快速算法

    本研究提出了一种基于新颖的修剪技术的精确算法，能够在大型稀疏图中快速找到最大团。实验结果表明，在大多数情况下，我们的算法比现有算法快数个数量级，并且我们还提出了一种能够在最优或接近最优解的情况下比精确算法快数个数量级的启发式变体。

    Sep, 2012

  • 潜在的随机步骤作为最大割、最小割和更多的松弛

    基于非负矩阵分解的概率模型统一了节点聚类和图简化，提供了建模任意图结构的框架。通过将硬聚类放松为软聚类，我们的算法将潜在的困难聚类问题转化为易处理的问题。

    Aug, 2023

  • 强三元闭合与簇删除的关系

    该论文研究了基于无向图的两个相关问题的参数化复杂性和经典复杂性，包括强三元闭包、集群删除等问题，并研究了关于这两个问题的复杂性和多项式内核等相关问题。

    Mar, 2018

  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。

    Jun, 2024

  • 基于拟阵的删除鲁棒子模型最大化

    本文研究在传统的拟阵约束下，单调子模函数的删除鲁棒版本的最大化问题，提出了空间复杂度依赖于拟阵的秩和删除元素数量的常数因子逼近算法，在中心化、流式环境下均获得了好的结果。

    Jan, 2022