RoClust: Role discovery for graph clustering

Bin Hui Chou, Einoshin Suzuki

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalWeb Intelligence and Agent Systems
Issue number1
Publication statusPublished - 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'RoClust: Role discovery for graph clustering'. Together they form a unique fingerprint.

Cite this