BENCHMARK GRAPHS TO TEST COMMUNITY DETECTION ALGORITHMS
Methods to detect communities in graphs need to be thoroughly tested. To do that, one needs benchmark graphs with a built-in community structure, that the methods should identify. Standard benchmarks, like that by Girvan and Newman, do not account for important features of real networks, like the fat-tailed distributions of node degree and community size. Therefore, we have proposed new classes of benchmark graphs, in which the distributions of node degree and community size are both power laws, with tunable exponents. In the paper Benchmark graphs for testing community detection algorithms, we have proposed a benchmark for the simplest case of undirected and unweighted graphs.
Package 1 includes the code to generate undirected and unweighted graphs with overlapping communities. The extent of the overlap can be tuned by input, and it can be set to zero if one is interested in non-overlapping clusters.
Package 2 includes the code to generate undirected weighted graphs with possibly overlapping communities.
Package 3 includes the code to generate directed unweighted graphs with possibly overlapping communities.
Package 4 includes the code to generate directed weighted graphs with possibly overlapping communities.
Package 5 includes the code to generate the hierarchical benchmarks, with communities inside other communities.
The code is written in C++. In each package there is a Readme file where you can find instructions on how to use the code and simple examples.
GENERALIZED NORMALIZED MUTUAL INFORMATION
In our paperDetecting the overlapping and hierarchical community structure in complex networks(New J. Phys. 11, 033015, 2009) we have introduced a measure of similarity between partitions that can be applied also to compare covers, i.e. divisions of a network into overlapping communities. The measure is based on the normalized mutual information used in information theory and regularly adopted by scholars to compare partitions of a network in communities. The standard normalized mutual information cannot be trivially extended to the case of overlapping communities. The code to compute our new measure for a pair of partitions/covers can be found here. The new measure does not coincide with the standard normalized mutual information when communities do not overlap, but it is quite close. For more information on the measure check this link.