Localized edge ranking for fast graph clustering

Graph clustering addresses the problem of how to partition the vertices of a graph into subgraphs such that the vertices in the same subgraph are highly homogeneous and share some common characteristics. To reduce the computational cost, this paper presents a novel clustering algorithm, called LERgc, utilizing localized connectivity knowledge. We compare LERgc with widely used MCL algorithm in terms of both structural quality and functional quality. The structural evaluation shows that LERgc has better compactness than MCL and the functional evaluation based on labeled protein protein interaction network shows that LERgc can better discover clusters in a protein protein interaction network.