图聚类算法比较：社会网络中的最短距离与随机漫步应用

本文主要探讨了图聚类算法在社会关系网络中的应用，特别是针对社会网络图中独特的特性，如节点没有明确的坐标值，使得传统的欧氏距离和曼哈顿距离不再适用。作者重点聚焦于基于划分的图聚类方法，其中一种常见的算法是k-medoids聚类，这是一种非参数化的方法，通过将数据点映射到聚类中心（medoids）来实现。 在k-medoids算法的具体应用中，文章对比了两种距离计算策略：最短距离算法和随机漫步距离算法。最短距离算法顾名思义，衡量两点间直线或路径上的最小距离，这对于寻找紧密连接的子群体非常有效。而随机漫步距离则模拟了在网络中随机行走直到达到另一个节点的概率，这可能更强调节点之间的交互频率而非物理距离。 作者以DBLP数据集构建的社会关系网络为例，进行了实验来验证这两种距离计算方法对图聚类结果的影响。实验结果显示，最短距离算法在社会关系网络的图聚类任务中表现更佳，因为它能够更好地捕捉到节点间的直接联系和社区结构，从而实现更准确的分类。 此外，文中还提到了关键词，包括图聚类（Graph Clustering）、社会关系网络（Social Network）、k-medoids、最短距离算法（Shortest Distance Algorithm）以及随机漫步距离算法（Random Walk Distance Algorithm）。这些关键词揭示了论文的核心研究内容和焦点，即如何适应社会网络数据的特性，选择有效的聚类算法。 这篇文章深入研究了图聚类算法在社会关系网络中的实际应用，特别是在处理无坐标值节点的情况下，如何选择合适的距离度量，以及如何通过k-medoids算法优化聚类效果。这对于理解复杂网络的数据分析和挖掘具有重要的理论和实践价值。