A Heuristic Clustering Algorithm for Mining Communities in Signed Networks

• 作 者: Bo Yang Da-You Liu
• 机 构: College of Computer Science and Technology,Key Laboratory of Symbolic Computation and Knowledge Engi
• 出 处: 计算机科学技术学报（英文版）
• 发表日期: 2004年期
• 关键词: complex network signed network community clustering graph theory
• 基金项目: 国家自然科学基金

Signed network is an important kind of complex network, which includes both positive relations and negative relations. Communities of a signed network are defined as the groups of vertices, within which positive relations are dense and between which negative relations are also dense. Being able to identify communities of signed networks is helpful for analysis of such networks. Hitherto many algorithms for detecting network communities have been developed. However, most of them are designed exclusively for the networks including only positive relations and are not suitable for signed networks.So the problem of mining communities of signed networks quickly and correctly has not been solved satisfactorily. In this paper, we propose a heuristic algorithm to address this issue. Compared with major existing methods, our approach has three distinct features. First, it is very fast with a roughly linear time with respect to network size. Second, it exhibits a good clustering capability and especially can work well with complex networks without well-defined community structures.Finally, it is insensitive to its built-in parameters and requires no prior knowledge.