Affiliations: Department of Informatics, ISEE, Kyushu University, Fukuoka 8190395, Japan. E-mail: {chou,suzuki}@i.kyushu-u.ac.jp
Note: [] The preliminary version of this paper was presented at the 13th APWeb Conference, April 18th–20th, 2010, Beijing, China.
Note: [] Corresponding author.
Abstract: 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.
Keywords: Graph clustering, community detection, overlapping communities, role, social network analysis
