Anti-community Detection

Anti-community Structures

Anti-community structure

Traditional communities are considered to have a high density of internal connections, combined with a low density of edges between different communities. However, not all naturally occurring communities in complex networks are characterized by this notion of structural equivalence.  Groups of energy states with shared quantum numbers in networks of spectral line transitions, for example, have a low density of internal connections and a high density of external connections. While anti-communities have been discussed in the literature for anecdotal applications or as a modification of traditional community detection, no rigorous investigation of algorithms has been presented. To this end, we introduce and discuss a broad range of possible approaches and evaluate them with regard to efficiency and effectiveness on a range of real-world and synthetic networks.


For further details, please refer to the original publication:

  • Sebastian Lackner, Andreas Spitz, Matthias Weidemüller, and Michael Gertz.
    Efficient Anti-community Detection in Complex Networks.
    In: Proceedings of the 30th International Conference on Scientific and Statistical Database Management (SSDBM '18), Bozen-Bolzano, Italy, July 9–11. 2018
    [pdf] [acm] [code] [slides]

Datasets / Implementation

Reference implementations for all algorithms proposed in our paper, as well as the corresponding datasets, are provided in the following GitHub repository.

  • For greedy methods, the algorithms are implemented directly in C. The code is basically self-containing, so no external dependencies are required. For your convenience, we also provide bindings for the Python language.
  • For vertex similarity methods the implementations are written in Python and make use of the sklearn library.

Please refer to the GitHub repository for more details and instructions how to use the code.

Contact

If you have any questions or feedback, we are happy to help. If you are using our implementation, we would love to hear about it! Please contact Sebastian Lackner. [email] [web]