Validation of community robustness

The large amount of work on community detection and its applications leaves unaddressed one important question: the statistical validation of the results. We present a methodology able to clearly detect the truly significance of the communities identified by some technique, permitting us to discard those that could be merely the consequence of edge positions in the network. Given a community detection method and a network of interest, our procedure examines the stability of the partition recovered against random perturbations of the original graph structure. To address this issue, we specify a perturbation strategy and a null model to build a stringent statistical test on a special measure of clustering distance, namely Variation of Information. The test determines if the obtained clustering departs significantly from the null model, hence strongly supporting the robustness against perturbation of the algorithm that identified the community structure. We show the results obtained with the proposed technique on simulated and real dataset.