The new multilevel refinement is significantly more effective than the conventional single-level refinement or no refinement such as (Blondel et al., 2008), in reasonable runtime. Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Local search starting from singleton clusters is used to compute a preliminary clustering, and then optionally, a refinement phase, where this clustering is improved by moving vertices between clusters. As a generalization, multilevel heuristics coarsen in several stages, and refine by moving entire clusters from each of these stages, not only individual vertices.
Adjust the following parameters to optimize the algorithm (See the paper for more detail):
|Weight||An integer attribute of the edge that will be used as weight parameter|
|Resolution||The resolution parameter determines the granularity level at which communities are detected. Use a value above (below) 1.0 if you want to obtain a larger (smaller) number of communities.|
|Random Start||Number of random starts|
|Iterations||Number of iterations per random start|
|Random Seed||Seed of the random number generator|
The directionality of the input network does not matter, so both directed and undirected networks yield the same results.
If the input network has numeric edge attributes, one can be chosen as edge weight. If no edge weight (attribute) is specified, all edges default to having a weight of 1.
The output network will structurally be the same as the input network, but the nodes will be annotated with new attributes labeled "community_level_x", where x is a community level. The value of each of these attributes is the id of a community.
A single network is expected as the input, and a single network is produced as the output.
A modified version of the Java implementation of this algorithm is compiled and wrapped for integration into CIShell (see Link and References). This version is modified to accept input from method call rather than console.
To integrate this algorithm in CIShell, a custom (Java) converter is used to convert the input network file to a edge list file that is proprietary to the compiled algorithm. The compiled algorithm is then executed upon this proprietary edge list file. The output community file is merged with the input network to produce the output network with annotations.
The output of this algorithm can be visualized well with the Circular Hierarchy visualization or using Gephi.
- Randolf Rotta, Andreas Noack, 2011. "Multilevel local search algorithms for modularity clustering". Journal of Experimental Algorithmics (JEA), Volume 16, 2011.