A fast multilevel algorithm for graph clustering and community detection

by: Hristo Djidjev

(16 Jul 2007)

View FullText article

arXiv (abstract), arXiv (PDF), NASA ADS

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

bigbossman, AbnerCYH, Scis0000002, CSBBGraphTheory (group)

Find related articles with these CiteULike tags

algorithm, algorithms, cliques, clustering, communities, community, complex, detection, graph, history, multilevel

Abstract

One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms.

@misc{citeulike:1464867, abstract = {One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms.}, author = {Djidjev, Hristo }, citeulike-article-id = {1464867}, eprint = {0707.2387}, keywords = {algorithm, clustering, community, detection, graph, multilevel}, month = {Jul}, posted-at = {2007-07-18 13:38:37}, priority = {2}, title = {A fast multilevel algorithm for graph clustering and community detection}, url = {http://arxiv.org/abs/0707.2387}, year = {2007} }

RIS record

TY - ELEC ID - citeulike:1464867 L3 - citeulike-article-id:1464867 TI - A fast multilevel algorithm for graph clustering and community detection N2 - One of the most useful measures of cluster quality is the modularity of a partition, which measures the difference between the number of the edges joining vertices from the same cluster and the expected number of such edges in a random (unstructured) graph. In this paper we show that the problem of finding a partition maximizing the modularity of a given graph G can be reduced to a minimum weighted cut problem on a complete graph with the same vertices as G. We then show that the resulted minimum cut problem can be efficiently solved with existing software for graph partitioning and that our algorithm finds clusterings of a better quality and much faster than the existing clustering algorithms. KW - algorithm KW - clustering KW - community KW - detection KW - graph KW - multilevel AU - Djidjev, Hristo PY - 2007/Jul/16/ UR - http://arxiv.org/abs/0707.2387 ER -

RIS BibTeX