NIPSDec, 2017

一个用于图聚类的流算法

PDF
TL;DR我们提出了一种新的算法，用于在单次遍历的边流设置中执行图聚类，并基于模块度函数提供了理论上的解释。我们对从一百万到十亿边的大规模现实生活图表进行实验，并展示了该算法比现有算法运行速度快十倍以上，并可在最大的图表上获得相似或更好的检测分数。
发现论文，激发创造
  • 数据流中的双聚类和布尔矩阵分解

    本文在数据流中对二分图聚类和布尔矩阵分解问题进行了研究，提出一种使用亚线性空间复杂度，在数据流遍历一遍后能够恢复右部聚类的算法，并且在第二次遍历中能够恢复左部聚类，同时还能够扩展该算法来解决布尔矩阵分解问题。

    Dec, 2020

  • 在边缘流上计算图描述符

    通过使用流算法近似计算三种不同的图表述，避免将整个图存储在内存中，并控制样本大小，使我们能够将算法运行时间保持在所需的范围内，并通过分析逼近误差和分类准确度证明所提出的描述符的功效。

    Sep, 2021

  • 流式异构图快速内存高效异常检测

    StreamSpot 是一种基于聚类的异常检测方法，可以在消耗有限的内存的同时，实时对包含不同节点和边的杂乱图形流进行检测，并可处理超过每秒 100K 条边的数据流。该方法具有良好的性能，并且可以处理从正常浏览器活动到各种攻击情况的各种情况。

    Feb, 2016

  • 数据流聚类：一篇综述

    该文综述了数据流聚类算法的基本概念和特点，对不同算法进行了对比分析，讨论了数据流聚类存在的问题和挑战。

    Jul, 2020

  • 亚线性时更新的动态相关聚类

    在动态节点流中，我们研究了相关聚类的经典问题。我们提出了一种算法，通过维护 $O (1)$ 的逼近精度和 $O$(polylog $n$) 的摊销更新时间，不断寻找最小化穿越簇的正边和簇内负边之和的分区。最后，我们用实际数据实验证明了我们的理论分析。

    Jun, 2024

  • 数据流中的相关聚类

    本文研究动态数据流模型下相关聚类问题，结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法，解决了自然问题。

    Dec, 2018

  • 改善的图聚类

    本文提出了一种新算法 —— 最大似然凸化版本，用于解决在随机块模型环境下的社交网络图聚类问题，相较于目前已有算法，本文算法在允许普遍规模的簇大小时的表现高出多项式因子。

    Oct, 2012

  • 分布式草图缩放图聚类

    该研究使用基于矩阵草图的方法来解决在大规模图分析中传统方法遇到的挑战，尤其是无监督学习的社区结构划分问题，实验表明该方法在分配内存中可以获得出色的聚类效果，同时提高了聚类速度。

    Jul, 2020

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

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

    Sep, 2008

  • 分布式图聚类与稀疏化

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

    Nov, 2017