Sep, 2018

相关聚类推广

PDF
TL;DRLambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。
发现论文，激发创造
  • 参数化图聚类和边标记的更快逼近算法

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

    Jun, 2023

  • 完全图和完全 k 部分图上相关聚类的近似最优线性规划舍入算法

    该论文提出了一种新的线性规划松弛四舍五入方案，解决了相关聚类问题的近似算法问题和完整性间隙问题，从而在完全图中实现了 2.06-ε 的近似度，而在完全 $k$- 部分图中实现了 3 的近似度。

    Dec, 2014

  • 社交网络分析中的模式聚类和重叠聚类

    本文引入了一种新的聚类范式 —— 模式聚类，该文章探讨了模式聚类在社交网络社区分析中的应用，以及通过模式覆盖算法实现的重叠聚类与潜在特征推断等问题。

    Dec, 2016

  • 大规模图上的并行相关聚类

    本文提出了 C4 和 ClusterWild！两个用于并行相关聚类的算法，并在实验中证明了它们在精度和运行时间方面的优势。

    Jul, 2015

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

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

    Nov, 2021

  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

    本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

    Jul, 2023

  • 常数轮并行下的相关聚类

    本文提出了一种基于大规模并行计算 (MPC) 的算法，用于解决相关聚类问题。该算法的主要目标是利用签名图对图进行分区以最小化争议数量。在实验中，该算法同时试图减少节点内存的使用率。我们的算法是第一个在亚线性存储器中运行且使用有限的 MPC 轮数可以证明近似计算聚类问题方法的一种。

    Jun, 2021

  • 通过（超）图划分进行本地模体聚类

    本文针对基于分布的局部聚类问题，提出了结合超图和图模型的新方法，通过组合优化算法求解，并在三角形图案实验中表现出了较高的性能表现。

    May, 2022

  • GLCC: 用于图级聚类的通用框架

    本文提出了一种面向多个图形的一般图级聚类框架，名为 GLCC，它使用对比学习技术，包括实例级和聚类级联合优化表示学习，以及使用邻域感知伪标签来奖励优化表示学习的过程。实验证实，GLCC 比其他竞争基线方法表现更好。

    Oct, 2022

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

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

    Oct, 2023