A Heuristic Clustering Algorithm for Mining Communities in Signed Networks

Signed network is an important kind of complex network, which includesboth positive relations and negative relations. Communities of a signednetwork are defined as the groups of vertices, within which positiverelations are dense and between which negative relations are also dense.Being able to identify communities of signed networks is helpful foranalysis of such networks. Hitherto many algorithms for detectingnetwork communities have been developed. However, most of them aredesigned exclusively for the networks including only positive relationsand are not suitable for signed networks. So the problem of miningcommunities of signed networks quickly and correctly has not been solvedsatisfactorily. In this paper, we propose a heuristic algorithm toaddress this issue. Compared with major existing methods, our approachhas three distinct features. First, it is very fast with a roughlylinear time with respect to network size. Second, it exhibits a goodclustering capability and especially can work well with complex networkswithout well-defined community structures. Finally, it is insensitive toits built-in parameters and requires no prior knowledge.