Community Structure - Testing Methods of Finding Communities Algorithms

Testing Methods of Finding Communities Algorithms

The evaluation of algorithms, to detect which are better at detecting community structure, is still an open question. It must be based on analyses of networks of known structure. A typical example is the "four groups" test, in which a network is divided into four equally-sized groups (usually of 32 nodes each) and the probabilities of connection within and between groups varied to create more or less challenging structures for the detection algorithm. Such benchmark graphs are a special case of the planted l-partition model of Condon and Karp, or more generally of "stochastic block models," a general class of random network models containing community structure. Other more flexible benchmarks have been proposed that allow for varying group sizes and nontrivial degree distributions, such as LFR benchmark proposed by Lancichinetti et al., which is an extension of the four groups benchmark that includes heterogeneous distributions of node degree and community size, making it a more severe test of community detection methods.

Commonly used computer-generated benchmarks start with a network of well-defined communities. Then, this structure is degraded by rewiring or removing links and it gets harder and harder for the algorithms to detect the original partition. At the end, the network reaches a point where it is essentially random. This kind of benchmark may be called "open". The performance on these benchmarks is evaluated by measures such as normalized mutual information or variation of information. They compare the solution obtained by an algorithm with the original community structure, evaluating the similarity of both partitions. While this is a reasonable approach when the original structure has been slightly blurred, it becomes pointless if it has been greatly modified, since the original community structure is not present anymore. Recently, Aldecoa and Marín have proposed the closed benchmarks. They also start with a network with well-known community structure. However, the rewiring process is now guided toward a second structure which is identical to the initial one, although the node labels have been mapped from the former to the latter. In this manner, it can be tested if the solutions of the algorithms follow the evolution of the community structure or not. Moreover, the characteristic configuration of the closed benchmarks allows to check the optimality of an obtained partition, at any moment of the process, using the variation of information.