Anti-Community Detection ########################
As a first step, please make sure that all required dependencies are installed. The following commands can be used to install missing packages on Ubuntu or Debian operating systems:
$ sudo apt-get install build-essential $ sudo apt-get install libgsl-dev
Afterwards, just extract the source code to a directory of your choice and run:
$ make
If everything goes well, the program terminates with exitcode 0. If not, the error message should hopefully contain a hint what is going wrong. All compiled programs will be located within the src/ and third-party/ directory.
After the compilation finished, it makes sense to run the included self-tests to check that everything works fine. The tests are all located in the src/ folder, so we first have to switch to the right directory:
$ cd src
To run the self-tests of the library itself, execute:
$ make test
To run tests for the Python bindings, execute:
$ ./pygraph.py
Most programs contained in this package require graph data with the following input format:
--- snip --- NumberOfNodes StartNode EndNode [Weight] \ StartNode EndNode [Weight] } Edges StartNode EndNode [Weight] / [...] --- snip ---
The first line defines the number of nodes, all following lines describe the edges (first node index, second node index, optional weight). Lines starting with "#" are comments and have to be ignored. An example for a trivial graph can be seen in src/data/example-trivial.graph.
The current version of the package contains the following programs. Each program also has a separate help, which can be shown by running "PROGRAM --help", e.g., "src/laprop --help".
$ src/gml Convert graph to GML file format.
$ src/laprop Apply label propagation algorithm to the graph specified by the given file.
$ src/maxmodularity Agglomerative hierarchical clustering algorithm for community detection / modularity maximization.
$ src/minmodularity Agglomerative hierarchical clustering algorithm for anti- community detection / modularity minimization.
$ src/antimodularity Agglomerative hierarchical clustering algorithm for anti- community detection / anti-modularity maximization.
$ src/components Return connected components of an undirected graph.
$ src/metrics Compute modularity and anti-modularity for the graph specified by the given file. When a ground-truth label file is given, also compute cluster quality metrics.
$ src/subgraph Extract subgraph specified by the given files.
The datasets directory contains a collection of various small graphs. The graphs already have been converted to the correct format. Each directory contains a file called "result.graph".
After changing the implementation of an algorithm, it is sufficient to execute:
$ cd datasets $ make clean $ make
to run all evaluations again. This might take a few minutes. In each directory, a "metrics.txt" file will be created, which contains common measures (such as the number of communities, Modularity, Antimodularity, etc.) and can be used to compare different algorithms.
As an example, the following commandline applies a Modularity minimization algorithm to the Adjectives and Nouns dataset.
$ src/minmodularity datasets/adjectives-noun/result.graph
By default, the output (a vector of vertex labels) is written directly to the terminal. Nevertheless, if preferred, it can also be redirected to a file:
$ src/minmodularity datasets/adjectives-noun/result.graph > output.txt
Note that some programs might have additional parameters, which are passed through to the (anti-)community detection method. Please check "PROGRAM --help" to get a list of available options.
To compute the modularity and anti-modularity measure, as well as some other statistical values for a community detection result, just run:
$ ./src/metrics --clusters=datasets/adjectives-noun/minmodularity.txt \ $ --groundtruth=datasets/adjectives-noun/ground-truth.txt \ $ datasets/adjectives-noun/result.graph
The output will contain one measure per line. To write the result to a file, the operator ">" can be used, as in the example above.
To create plots suitable for publication, we recommend the tool Gephi available from https://gephi.org/. As a prepartion, use the "gml" program to create a file containing all attributes required for plotting, for example:
$ ./src/gml --base=datasets/adjectives-noun/ground-truth.txt \ $ --algo=datasets/adjectives-noun/minmodularity.txt \ $ datasets/adjectives-noun/result.graph > import.gml
Note that you can add an arbitrary number of attributes by adding additional --NAME=FILENAME arguments to the commandline. When you have selected all attributes you need, import the output file (here "import.gml") into Gephi.
To color vertices based on an attribute, select the menu "Partition" in the side bar "Appearance" on the left. Choose one of the attributes (e.g., "algo"), and then click on "Apply" to confirm your changes.
Arranging the vertices based on attributes requires a bit more effort: Create a new filter "Library -> Attributes -> Partition -> base" using the side bar "Filters" on the right. Then select one partition at a time, click on the "Filter" button in the bottom right corner, and apply a Layout method of your choice (e.g., "Fruchterman Reingold"). When this is done, use the "Drag" cursor to move the cluster to a location of your choice, and proceed with the next partition. Note that you can change the selection radius by clicking on "Configure" in the top part of the "Graph" view. (If there is an easier way to achieve a similar result, please let me know!)
S. Lackner, A. Spitz, M. Weidemüller, and M. Gertz. 2018. Efficient Anti-community Detection in Complex Networks. Proceedings of the 30th International Conference on Scientific and Statistical Database Management (SSDBM '18), July 9-11, 2018, Bozen-Bolzano, Italy. ACM, NY, USA. https://doi.org/10.1145/3221269.3221289
L. Chen, Q. Yu, and B. Chen. 2014. Anti-modularity and anti-community detecting in complex networks. Inf. Sci. 275 (2014), 293–313. https://doi.org/10.1016/j.ins.2014.02.040
M. E. J. Newman. 2004. Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 6 (2004), 5. https://doi.org/10.1103/PhysRevE.69.066133
M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 2 (2004), 15. https://doi.org/10.1103/PhysRevE.69.026113
M. E. J. Newman and G. Reinert. 2016. Estimating the number of communities in a network. Phys. Rev. Lett. 117 (2016), 5. Issue 7. https://doi.org/10.1103/PhysRevLett.117.078301