A unified framework for spectral clustering in sparse graphs

One of the most natural tasks in graph theory is community detection, i.e., the identification of similarity groups on a given network. Practically, for an unweighted and undirected graph G(V, E) with V n nodes and E edges, community detection consists in finding a non-overlapping partition of the nodes that identifies underlying communities in a completely unsupervised manner. There is no unique definition of a community, but a general criterion is to impose that nodes in the same community have more interconnections than nodes in different communities, as a consequence of the stronger affinity among members of the same community [17]. There exist many ways of formalizing this intuition, some of them under the form of a cost function to minimize, such as the MinCut, RatioCut, and NormalizedCut costs [53]. The resulting optimizations are however NPhard problems and, as a consequence, many algorithms consist in retrieving relaxed continuous solutions of the problem.