Anti-modularity and anti-community detecting in complex networks

• We present the anti-modularity as a quality measure of the anti-community detecting.
• A label propagation algorithm LPAD for anti-community detection is proposed.
• The proposed algorithm LPAD does not require the predefined number of anti-communities.
• The proposed algorithm LPAD has low time complexity of O(n2).
• LPAD can maximize the number of edges between clusters and minimize the number of clusters.

Many networks of interest in sciences and social research can be divided naturally into anti-communities. The problem of detecting and characterizing such anti-community structure has attracted recent attention. In this paper, we first define the anti-modularity as a quantitative measure of anti-community partitioning on a network. We also theoretically and empirically show the reliability of anti-modularity as a measurement of the quality of an anti-community partitioning. A label propagation algorithm LPAD for anti-community detection is proposed. Experimental results on synthetic and real world networks show that our algorithm LPAD can obtain higher quality anti-community partitioning than other methods.