Title: Clique-based Method for Social Network Clustering,
Abstract: In this article, we develop a clique-based method for social network
clustering. We introduce a new index to evaluate the quality of clustering
results, and propose an efficient algorithm based on recursive bipartition to
maximize an objective function of the proposed index. The optimization problem
is NP-hard, so we approximate the semi-optimal solution via an implicitly
restarted Lanczos method. One of the advantages of our algorithm is that the
proposed index of each community in the clustering result is guaranteed to be
higher than some predetermined threshold, $p$, which is completely controlled
by users. We also account for the situation that $p$ is unknown. A statistical
procedure of controlling both under-clustering and over-clustering errors
simultaneously is carried out to select localized threshold for each
subnetwork, such that the community detection accuracy is optimized.
Accordingly, we propose a localized clustering algorithm based on binary tree
structure. Finally, we exploit the stochastic blockmodels to conduct simulation
studies and demonstrate the accuracy and efficiency of our algorithms, both
numerically and graphically.