Community detection in graphs

A thorough exposition of community structure, or clustering, is attempted, from the definition of the main elements of the problem, to the presentation of most methods developed, with a special focus on techniques designed by statistical physicists.

Abstract

The modern science of networks has brought significant advances to our\nunderstanding of complex systems. One of the most relevant features of graphs\nrepresenting real systems is community structure, or clustering, i. e. the\norganization of vertices in clusters, with many edges joining vertices of the\nsame cluster and comparatively few edges joining vertices of different\nclusters. Such clusters, or communities, can be considered as fairly\nindependent compartments of a graph, playing a similar role like, e. g., the\ntissues or the organs in the human body. Detecting communities is of great\nimportance in sociology, biology and computer science, disciplines where\nsystems are often represented as graphs. This problem is very hard and not yet\nsatisfactorily solved, despite the huge effort of a large interdisciplinary\ncommunity of scientists working on it over the past few years. We will attempt\na thorough exposition of the topic, from the definition of the main elements of\nthe problem, to the presentation of most methods developed, with a special\nfocus on techniques designed by statistical physicists, from the discussion of\ncrucial issues like the significance of clustering and how methods should be\ntested and compared against each other, to the description of applications to\nreal networks.\n