图聚类算法解析：从随机游走到MCL与LERgc

本文主要介绍了图聚类算法的相关概念，包括图聚类的基本思想、随机游走、马尔科夫模型以及两种特定的图聚类算法：MCL（Markov Cluster Algorithm）和LERgc（Localized Edge Ranking for Fast Graph Clustering）。 1. 图聚类 图聚类是数据挖掘中的一个重要领域，它旨在将具有相似性质的节点聚集在一起，形成不同的类别。图聚类广泛应用于社交网络分析、蛋白质相互作用网络研究等场景。聚类方法主要有基于划分、基于层次、基于密度、基于网格和基于模型等策略。在图聚类中，节点相似度通常不再依赖于传统的几何距离，而是利用图的特性，如点介数、边介数、度数和最短路径等来计算。 2. 随机游走 随机游走是一种在图中模拟随机过程的方法，其中每个顶点被赋予一定的转移概率到其相邻顶点。在无权图中，每个顶点到邻居的概率通常是均等的，而在有权图中，概率会根据边的权重进行分配。随机游走对图的结构敏感，有助于识别节点间的紧密连接。 3. 马尔科夫模型 马尔科夫模型是一种描述系统状态转换的统计模型，其中未来状态只依赖于当前状态，而与之前的状态无关。在图聚类中，马尔科夫模型用于模拟随机游走，通过转移概率矩阵进行状态转换，可以用于矩阵的膨胀和扩展操作。 4. MCL（Markov Cluster Algorithm） MCL算法是一种全局性的图聚类方法，通过矩阵的膨胀和收缩操作实现聚类。膨胀操作通过矩阵自乘增强节点之间的连接，而收缩操作则有助于凝聚成聚类。这一过程可以通过膨胀因子来调整聚类的精细程度。 5. LERgc（Localized Edge Ranking for Fast Graph Clustering） LERgc是一种局部图聚类算法，它从特定的顶点或顶点集合出发，寻找与其相关的类别。与全局方法不同，LERgc更关注节点之间的局部关系，通过局部边打分策略，根据顶点的概率和与目标节点的交集来识别相关联的边。 图聚类算法通过分析节点之间的关系，利用随机游走和马尔科夫模型等工具，能够在复杂网络中有效地发现结构相似的群体，对于理解和解析网络结构具有重要意义。MCL和LERgc是两种有效的图聚类方法，分别适用于全局和局部视角的聚类需求。