2017/05/11 by Cheng‐Shang Chang, Chang, Cheng-Shang, Duan‐Shin Lee +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cooperative Communication and Network Coding #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1705.04254
openalex publication_date 2017/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 communities is equivalent to the decoding problem for a parity-check code. We also show how one can use two renowned decoding algorithms in error- correcting codes for community detection in signed networks: the bit-flipping algorithm, and the belief propagation algorithm. In addition to these two algorithms, we also propose a new community detection algorithm, called the Hamming distance algorithm, that performs community detection by finding a codeword that minimizes the Hamming distance. We compare the performance of these three algorithms by conducting various experiments with known ground truth. Our experimental results show that our Hamming distance algorithm outperforms the other two.