在图聚类中，我们希望对给定图的节点进行聚类，使得同一聚类中的节点高度连接（通过边），而不同聚类中的节点连接不良或根本没有连接。

在图上执行聚类的简单（分层和分裂）算法基于首先找到图的最小生成树（使用例如Kruskal 算法），$T$. 然后它继续迭代。在每次迭代中，我们从$T$权重最高的边。鉴于$T$是一棵树，去掉一条边$T$将创建一个森林（带有连接的组件）。因此，在去除权重最高的边缘之后$T$，我们将有两个连通分量。这两个连接的组件将代表两个集群。因此，经过一次迭代，我们将拥有两个集群。在下一次迭代中，我们删除权重第二高的边，这将创建其他连接的组件，依此类推，直到可能所有节点都在自己的集群中（也就是说，所有边都已从$T$）。

这个算法有几个限制。例如，它只考虑与共享的初始图的边$T$（即只考虑最小生成树的边）。它还需要对图的边缘进行加权。它不需要预先知道簇的数量（像任何其他层次聚类算法一样），但我们仍然需要选择最佳的簇数（在算法终止之后）。我们可以通过多种方式做到这一点。一种方法是设置阈值$t$用于决定我们何时应该停止从$T$：更具体地说，我们将继续从$T$直到下一个最高权重高于此阈值$t$.

这种类型的聚类有很多应用。例如，我们可能想要发现社交网络中的某些人群。

Graph clustering论文（Satu Elisa Schaeffer，2007 年）提供了该领域的可读且非常详细的概述。

有一些基于 k-means 的算法也可以在图上工作。参见例如基于图的 k 均值聚类：集合中值与广义中值图的比较（由 Ferrer 等人撰写）。