Graph clustering based on mixing time of random walks
Graph clustering based on mixing time of random walks
复制标题
基于随机游走混合时间的图聚类
DOI：
10.1109/icc.2014.6883961
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
G. Neglia
中科院分区：
文献类型：
--
作者：
Konstantin Avrachenkov;Mahmoud El Chamie;G. Neglia
图的群集是将其节点分组的任务，使得同一群集中的节点连接良好，但它们与不同群集中的节点的连接较少。本文提出了一种基于随机游动性质的聚类度量来评价图的聚类质量。我们还提出了一种随机化算法，该算法根据定义的度量确定图的局部最优聚类。该算法本质上是分布式的和异步的。如果该图表示一个实际网络，其中节点具有计算能力，则每个节点可以仅依靠本地通信来确定其自己的集群。我们证明了簇的大小可以根据可用的处理能力来调整，以降低算法的复杂度。
Clustering of a graph is the task of grouping its nodes in such a way that the nodes within the same cluster are well connected, but they are less connected to nodes in different clusters. In this paper we propose a clustering metric based on the random walks' properties to evaluate the quality of a graph clustering. We also propose a randomized algorithm that identifies a locally optimal clustering of the graph according to the metric defined. The algorithm is intrinsically distributed and asynchronous. If the graph represents an actual network where nodes have computing capabilities, each node can determine its own cluster relying only on local communications. We show that the size of clusters can be adapted to the available processing capabilities to reduce the algorithm's complexity.