This package is a tool for community detection and evaluation in signed and weighted networks. This is an implementation of our paper on community detection, which extends Constant Potts Model (CPM) objective function optimized using Louvain algorithm, and uses the extended Map Equation for signed networks to find the scale parameter of CPM. Quality of arbitrary communities can be evaluated using the Map Equation as a more robust variant of Modularity; see this experimental and theoretical results.
Download the jar file from here (v1.0.0, 188kb).
Start using the program by running java -jar <filename> -h.
This project is developed as a maven project.
Input graph format is required to be:
id1 id2 weight
...
where each line represents a link from id1 to id2;
graph is considered undirected by default.
To detect the communities of graph.txt, run the command below:
mdl --verbose -g graph.txt -o partition.txt
To detect communities at a specific resolution (scale) 0.001, run:
mdl --verbose -r 0.001 -g graph.txt -o partition.txt
To detect communities at a specific interval-accuracy of resolution, run:
mdl --verbose -i 0.01 0.05 -a 0.01 -g graph.txt -o partition.txt
Generally, by sliding the resolution from 0 to 1, detected communities become smaller and denser.
Setting r = 0 is equivalent to Correlation Clustering that aims to minimize the number of negative (positive) edges inside (between) clusters regardless of the edge density.
If you want to evaluate the quality of partition partition.txt
and write the evaluation result to mdl.txt, run:
mdl -g graph.txt -p partition.txt -o mdl.txt
If a graph is directed add --directed parameter. Evaluation is based on extended Map Equation and supports directed links.
If you want to evaluate a group of partitions partition-*.txt, run:
mdl -g graph.txt -p partition-*.txt -o mdl.txt
Other options can be viewed by:
mdl -h
For pre-processing a graph, such as extracting its positive or negative subgraphs, run:
preprocess -h
This algorithm requires O(E) memory space and O(ElogE) execution time for the detection
of communities in a signed network having O(E) links.
This implementation differs from our main Matlab-MEX implementation that used an extended version of Louvain algorithm proposed by M. Rosvall and C. T. Bergstrom. In future, we will try to implement one of the Louvain's recent variants to improve the performance of algorithm.
If you find this project useful, please cite the paper as follows:
Esmailian, P. and Jalili, M., 2015. Community detection in signed networks: the role of negative ties in different scales. Scientific reports, 5, p.14339.