寻找密集连接聚类的本地算法

ICMLJun, 2021

Local Algorithms for Finding Densely Connected Clusters

Peter Macgregor, He Sun

TL;DR本文研究了一种基于局部算法的图聚类方法，通过引入新的缩减技术来分析多个集合间的相互关系，并在多个实际数据集上通过恢复密集连接簇来展示算法的有效性。

Abstract

local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a s

local graph clustering vertex sets inter-connection reduction technique densely connected clusters

发现论文，激发创造

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

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

Sep, 2008

分布式图聚类与稀疏化

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

Nov, 2017

有向图的高阶谱聚类

本文研究了基于有向图的聚类，提出了基于 Hermitian 矩阵的近线性时间算法，并在合理假设下进一步证明该算法可以在亚线性时间内实现，并在 UN Comtrade 数据集上进行了广泛的实验，证明了算法的重要性。

Nov, 2020

稀疏随机图上本地算法的限制

本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小，而且通过聚类属性，我们强调了在随机图上的局部算法存在局限性。

Apr, 2013

图形中的社区检测

这篇研究论文讨论了网络科学中一个重要的问题 —— 发现社群结构的方法和应用，分析了该问题的主要元素和当前已有的各种方法，重点介绍了统计物理学家们开发的技术。

Jun, 2009

基于 PageRank 的超图聚类

本文提出了两种基于个性化 PageRank 的超图聚类算法，它们都具有输出顶点集合对导纳有理论保证的优点，并在解决方案质量和运行时间方面优于现有方法。这是第一篇在具备理论保证的情况下实现了超图聚类的实用算法。

Jun, 2020

网络社区结构快速检测算法

本文描述了一种快速检测具有社群结构的网络的新算法，并给出了各种应用实例，比之前的算法更加高效。

Sep, 2003

交互式聚类的本地算法

本文研究了基于稳定性假设的交互式聚类算法设计，算法开始于任意初始聚类，只进行每步的局部更改；我们证明在这种约束条件下，仍然可以设计出具有可证明高效和准确聚类能力的算法，并在真实数据上进行了实证。

Dec, 2013

在极大网络中找到社群结构

本篇论文提出了一种层次聚合算法，用于快速检测社区结构，可以在大规模复杂网络上运行，并且应用于分析一个大型在线零售商网站上销售物品的网络，揭示了客户购物习惯的大规模模式。

Aug, 2004

强局部超图扩散在聚类和半监督学习中的应用

本文提出了一种新的基于扩散的超图聚类算法，其解决了类图的二次超图割问题，能够非常快速且高效地计算各种势函数。该方法在实际大规模超图数据中得到了验证。

Nov, 2020