图聚类算法详解：从随机游走到局部聚类

"本资源是一份关于图聚类算法的讲义，涵盖了各种图聚类方法，包括随机游走、MCL（Markov Cluster Algorithm）和LERgc（Localized Edge Ranking for Fast Graph Clustering）。" 图聚类算法是数据挖掘和机器学习领域的重要工具，它通过分析网络图结构来发现其中的模式和群组。聚类的基本思想是将相似的节点聚集在一起，而将不相似的节点分开。在图聚类中，网络图可以是社交网络、蛋白质相互作用网络等，它们的节点代表实体，边则表示这些实体之间的关系。 随机游走是一种在图中模拟随机运动的方法，常用于计算节点间的相似度。在无权图中，随机游走意味着从一个顶点到其相邻顶点的概率是相等的；而在有权图中，游走概率可以根据边的权重进行调整。随机游走对图的度分布非常敏感，这使得它能捕获节点之间的连接强度差异。 马尔科夫模型是随机游走的基础，它描述了一个系统在状态之间转换的概率性规则。在这个模型中，未来的状态仅依赖于当前状态，而与之前的历史状态无关。在图聚类中，马尔科夫模型用于定义节点之间的转移概率，通过多次迭代，可以揭示节点之间的连通性并形成聚类。 MCL是一种全局性的图聚类算法，它基于马尔科夫过程。该算法通过矩阵的膨胀和扩展操作，即矩阵自乘，来模拟流在网络中的传播，从而识别出紧密相连的节点群。这种方法无需先验的簇大小信息，能够自适应地发现网络中的聚类结构。 LERgc（Localized Edge Ranking for Fast Graph Clustering）是另一种图聚类方法，它关注局部信息，从特定顶点或顶点集合出发，寻找与其相关的类别。LERgc利用局部边打分策略，根据顶点的度和与目标顶点的交集来计算游走概率，从而确定边的重要性，进而识别出聚类。 总结来说，图聚类算法涉及多种技术，如随机游走、马尔科夫模型、MCL和LERgc，它们各自有其适用场景和优势，能够帮助我们理解和解析复杂网络中的结构和模式。这些算法对于理解社交网络中的社区结构、生物网络中的功能模块，以及其他复杂系统都有着重要的应用价值。