Role discovery for graph clustering

Bin Hui Chou, Einoshin Suzuki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)


Graph clustering is an important task of discovering the underlying structure in a network. Well-known methods such as the normalized cut and modularity-based methods are developed in the past decades. These methods may be called non-overlapping because they assume that a vertex belongs to one community. On the other hand, overlapping methods such as CPM, which assume that a vertex may belong to more than one community, have been drawing attention as the assumption fits the reality. We believe that existing overlapping methods are overly simple for a vertex located at the border of a community. That is, they lack careful consideration on the edges that link the vertex to its neighbors belonging to different communities. Thus, we propose a new graph clustering method, named RoClust, which uses three different kinds of roles, each of which represents a different kind of vertices that connect communities. Experimental results show that our method outperforms state-of-the-art methods of graph clustering.

Original languageEnglish
Title of host publicationWeb Technologies and Applications - 13th Asia-Pacific Web Conference, APWeb 2011, Proceedings
Number of pages12
Publication statusPublished - 2011
Event13th Asia-Pacific Conference on Web Technology, APWeb 2011 - Beijing, China
Duration: Apr 18 2011Apr 20 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6612 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th Asia-Pacific Conference on Web Technology, APWeb 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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

Cite this