Community detection by \(L_{0}\)-penalized graph Laplacian (Q1639201)

It is known that community detection algorithms in network analysis aims at partitioning nodes into disjoint communities. Many real networks often contain outlier nodes that do not belong to any community. They just loosely connect to other nodes in the network and they often do not have a known number of communities. However most recent algorithms assume that the number of communities is known and even fewer algorithms can handle networks with outliers and unknown community numbers. The aim of the present paper is to present a method of detecting communities by maximizing a novel model-free tightness criterion which is closely related with the \(L_0\)-penalized graph Laplacian. To this direction the authors managed to develop an efficient algorithm based on the alternating direction method of multiplier in order to maximize this penalized Laplacian. Unlike many other community detection methods this method does not assume that the number of communities is known and can properly detect communities in networks with outliers. Under the degree corrected stochastic block model the authors managed to show that even for networks with outliers the maximization of the tightness criterion can extract communities with small misclassification rates in the case that the number of communities grows to infinity as the network size grows. Furthermore simulation and real data analysis show that the proposed method performs significantly better than existing methods since it can computationally efficiently recover the community structure with high resolution and accuracy.