Community detection in signed networks by relaxing modularity optimization with orthogonal and nonnegative constraints

Community detection in networks including singed edges is a primary challenge that has already attracted substantial attention. In this paper, we show that this task could be reformulated as a combinatorial optimization concerning the trace of the signed modularity matrix. Keeping the orthogonal and nonnegative constraints in the relaxation, we propose a multiplicative update rule, named the SMON algorithm, which results in a solution that is a close approximation to the genuine community indication matrix. In addition, the rows of the solution can be referred to as the probabilities of corresponding vertex falling into each community, which can help us to discover the overlapping community structure of the network and identify vertices that reside on the watersheds between different communities. Experimental results on real-life social networks as well as synthetic signed networks verify that our method is effective and superior to the existing approaches.