Worst-case test network optimization for community detection method

Network community detection finds communities/clusters of densely connected nodes with few edges outside the cluster. It is applied in a variety of domains, from e-commerce in social networks or web graphs, up to analysis of biochemical networks or control and automation tasks. Hi-consequence risk applications range from black-start recovery of power systems, truss structure manufacturing, neural motor control, water distribution, to image segmentation for finding cracks in bridges. For such important technical applications, it is necessary to know the limits of the used methods, how much they can deviate from optimum. The robustness of the community detection methods was already compared using a number of test networks, both real world and artificial. However, these test networks were implicitly average cases. Here, we evolve networks, which produce a maximum error of modularity measure for selected methods of community detection. This worst-case test networks were evolved for Edge betweenness, Fast greedy, Infomap, Louvain, and Walktrap modularity detection. Such a comparison provides a tougher test of robustness than previous approaches. A bit surprisingly, after the Blondel's Louvain method, the next best result was provided by fast greedy, while otherwise favored Infomap fared rather poorly.