Coarsening Networks Based on Local Link Similarity for Community Detection

How can we detect the natural community structure in a social network mingled with anomalous links? The majority of existing methods almost universally ignore these anomalous links (either correct or incorrect), and treat them as ordinary links without taking their particularities into account. From a novel perspective, we focus on handling anomalous links for community detection, since the anomalous links derived from noise directly affect the accuracy of community detection and removing them makes it much easier to comprehend the network topology. Inspired by link prediction, an effective approach is proposed to coarsen networks which removes abnormal links by virtue of the local similarity index. Extensive experiments demonstrate that our strategy achieves higher accuracy than raw networks, especially when a network has high mixing of communities. For real-world networks, the improvement is up to 8.7%. In addition, fine-grained communities, usually revealing rich information in real-world networks, can be well detected.