Title: Quantitative measurement and method for detecting anti-community structures in complex networks

Authors: Bo-Lun Chen; Ling Chen; Sheng-Rong Zou; Xiu-Lian Xu

Addresses: Department of Computer Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China ' Department of Computer Science, Yangzhou University, Yangzhou 225009, China; State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China ' College of Physics Science and Technology, Yangzhou University, Yangzhou 225009, China ' College of Physics Science and Technology, Yangzhou University, Yangzhou 225009, China

Abstract: Many networks of interest in sciences and social research can be divided naturally into anti-communities. The problem of detecting and characterising such anti-community structure has attracted recent attention. In this paper, we first define the anti-modularity as a quantitative measure over the possible partitioning of a network. We also show that the anti-modularity can be reformulated in terms of the eigenvectors of a characteristic matrix for the network, which we call the anti-modularity matrix. Based on the anti-modularity matrix, a spectral-based algorithm for anti-community detection is proposed. We also prove that the anti-modularity matrix is identical to the covariance matrix of the column vectors in the adjacent matrix ignoring a constant factor, and our algorithm essentially accomplishes a principal component analysis on the adjacent matrix. Experimental results on synthetic and real networks show that the anti-modularity is reliable as a measurement for the anti-community partitioning, and our algorithm can effectively detect the anti-communities.

Keywords: anti-community structures; anti-modularity; networks; bipartite graphs; network partitioning; anti-community detection; anti-communities; principal component analysis; PCA.

DOI: 10.1504/IJWMC.2013.057392

International Journal of Wireless and Mobile Computing, 2013 Vol.6 No.5, pp.431 - 440

Received: 27 May 2013
Accepted: 25 Jun 2013
Published online: 16 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article