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

摘要

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.