RoClust: Role discovery for graph clustering
RoClust: Role discovery for graph clustering
复制标题
DOI：
10.3233/wia-130259
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Bin-Hui Chou;Einoshin Suzuki
中科院分区：
文献类型：
--
作者：
Bin-Hui Chou;Einoshin Suzuki
图聚类或社区检测是通过将图中的顶点聚类为社区来发现网络底层结构的一项重要任务。在过去的几十年中，人们提出了非重叠方法（例如标准化切割和基于模块化的方法）来发现不相交的社区，这些方法假设每个顶点属于单个社区。另一方面，CPM 等重叠方法假设每个顶点可以属于多个社区，由于该假设符合现实，因此受到越来越多的关注。在本文中，我们表明现有的非重叠和重叠方法缺乏考虑将顶点与其属于不同社区的邻居连接起来的边，这通常会导致位于社区边界附近的顶点的反直觉结果。因此，我们提出了一种新的图聚类方法，名为RoClust，它使用桥、网关和集线器三种角色来发现社区。这三个角色中的每一个都代表一种连接社区的顶点。实验结果表明，RoClust 优于最先进的图聚类方法，包括非重叠和重叠方法。
Graph clustering, or community detection, is an important task of discovering the underlying structure in a network by clustering vertices in a graph into communities. In the past decades, non-overlapping methods such as normalized cuts and modularity-based methods, which assume that each vertex belongs to a single community, are proposed to discover disjoint communities. On the other hand, overlapping methods such as CPM, which assume that each vertex can belong to multiple communities, have been drawing increasing attention as the assumption fits the reality. In this paper, we show that existing non-overlapping and overlapping methods lack consideration to edges that link a vertex to its neighbors belonging to different communities, which often leads to counter-intuitive results of vertices located near borders of communities. Therefore, we propose a new graph clustering methods named RoClust, which uses three roles, bridges, gateways and hubs to discover communities. Each of the three roles represents a kind of vertices that connect communities. Experimental results show that RoClust outperforms state-of-the-art methods of graph clustering including non-overlapping and overlapping methods.