A Spectral Algorithm with Additive Clustering for the Recovery of Overlapping Communities in Networks

The commonly accepted definition of a community is that nodes tend to be more densely connected within a community than with the rest of the graph. Communities are often hidden in practice and recovering the community structure directly from the graph is a key step in the analysis of these datasets. Spectral algorithms are popular methods for detecting communities [26], that consist in two phases. First, a spectral embedding is built, where then nodes of the graph are projected onto some low dimensional space generated by well-chosen eigenvectors of some matrix related to the graph (e.g., the adjacency matrix or a Laplacian matrix). Then, a clustering algorithm (e.g.,k -means ork -median) is applied to then embedded vectors to obtain a partition of the nodes into communities.