参数化图聚类和边标记的更快逼近算法

Jun, 2023

参数化图聚类和边标记的更快逼近算法

Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling

Vedangi Bengali, Nate Veldt

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

Abstract

graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation

graph clustering lambdacc resolution parameter approximation algorithms edge labeling problem

发现论文，激发创造

相关聚类推广

LambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。

Sep, 2018

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

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

Nov, 2021

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

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

Apr, 2024

带类别边标签的图和超图聚类

本文提出了一种基于组合目标函数的计算框架，用于聚类在分类间具有超图的复杂关系的节点，特别地，解决了超边标签的聚类，其中簇对应于经常参与相同类型的交互的节点组。

Oct, 2019

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

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

Oct, 2022

分布式图聚类与稀疏化

本文提出了一个简单的分布式算法，基于采样方案将输入的密集图转化为稀疏的子图，并在多项式对数回合内完成图的聚类，同时具有高效的实现和处理大数据集的广泛应用。

Nov, 2017

大规模图的本地聚类算法及其在近似线性时间图分割中的应用

本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。