Abstract
In this paper, we consider the community detection problem in signed networks, where there are two types of edges: positive edges (friends) and negative edges (enemies). One renowned theorem of signed networks, known as Harary's theorem, states that structurally balanced signed networks are clusterable. By viewing each cycle in a signed network as a parity-check constraint, we show that the community detection problem in a signed network with two clusters is equivalent to the decoding problem for a parity-check code. We also show how one can use three renowned decoding algorithms in error-correcting codes for community detection in signed networks: the bit-flipping algorithm, the belief propagation algorithm, and the Hamming distance algorithm. In particular, the Hamming distance algorithm is shown to be equivalent to an optimization problem that can be heuristically solved by using the fast unfolding algorithm for community detection in unsigned networks. It can also be extended to signed networks with more than two clusters. We compare the performance of these three algorithms by conducting various experiments with known ground truth. Our experimental results show that the Hamming distance algorithm outperforms the other two.