Community detection in graphs

The modern science of networks has brought significant advances to ourunderstanding of complex systems. One of the most relevant features of graphsrepresenting real systems is community structure, or clustering, i. e. theorganization of vertices in clusters, with many edges joining vertices of thesame cluster and comparatively few edges joining vertices of differentclusters. Such clusters, or communities, can be considered as fairlyindependent compartments of a graph, playing a similar role like, e. g., thetissues or the organs in the human body. Detecting communities is of greatimportance in sociology, biology and computer science, disciplines wheresystems are often represented as graphs. This problem is very hard and not yetsatisfactorily solved, despite the huge effort of a large interdisciplinarycommunity of scientists working on it over the past few years. We will attempta thorough exposition of the topic, from the definition of the main elements ofthe problem, to the presentation of most methods developed, with a specialfocus on techniques designed by statistical physicists, from the discussion ofcrucial issues like the significance of clustering and how methods should betested and compared against each other, to the description of applications toreal networks.