发帖
雷达卡
摘要翻译：
本文提出了一种以归一化割准则最小化为目标的图聚类算法，并给出了模型顺序选择过程。在最小化归一化割方面，该算法的性能与谱方法相当。然而，与谱方法不同的是，所提出的算法可扩展到具有数百万个节点和边的图。该算法由三个部分组成，依次处理：贪婪凝聚层次聚类过程、模型顺序选择和局部细化。对于n个结点和O(n)条边的图，该算法的计算复杂度为O(nlog^2n)，比谱方法的O(n^3)复杂度有较大的改进。在真实网络和合成网络上进行了实验，验证了该方法的可扩展性，模型阶数选择过程的有效性，以及该算法在最小化归一化割度量方面的性能。
---
英文标题：
《GANC: Greedy Agglomerative Normalized Cut》
---
作者：
Seyed Salim Tabatabaei and Mark Coates and Michael Rabbat
---
最新提交年份：
2011
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
This paper describes a graph clustering algorithm that aims to minimize the normalized cut criterion and has a model order selection procedure. The performance of the proposed algorithm is comparable to spectral approaches in terms of minimizing normalized cut. However, unlike spectral approaches, the proposed algorithm scales to graphs with millions of nodes and edges. The algorithm consists of three components that are processed sequentially: a greedy agglomerative hierarchical clustering procedure, model order selection, and a local refinement. For a graph of n nodes and O(n) edges, the computational complexity of the algorithm is O(n log^2 n), a major improvement over the O(n^3) complexity of spectral methods. Experiments are performed on real and synthetic networks to demonstrate the scalability of the proposed approach, the effectiveness of the model order selection procedure, and the performance of the proposed algorithm in terms of minimizing the normalized cut metric.
---
PDF链接：
https://arxiv.org/pdf/1105.0974
京公网安备 11010802022788号
