SNMFP: A two-stage approach to community detection in signed networks

Community structure in signed networks is of substantial interest in various fields. Methods for detecting such structure, however, still remain comparatively limited for the moment. In this paper, we propose a two-stage approach for finding communities in networks that include both positive and negative links. In the first phase, the symmetric nonnegative matrix factorization (SNMF) is carried out on the positive component of the given network, providing each vertex with an initial community indication vector. We then introduce a diffusion process, named signed network propagation (SNP), to refine these vectors such that they are sufficiently smooth over the entire network and meanwhile are not far away from their initial values. After the process, vertices in the same community are likely to have similar vectors while vertices belonging to distinct communities tend to have different vectors, which give us a desirable partition of the signed network. Experiments on synthetic signed networks and several real signed networks validate the effectiveness and efficiency of the proposed approach.