Gridlock in Networks: The Leximin Method for Hierarchical Community Detection

Abstract

Community detection (CD) is an important task in network science. Identifying the community structure and hierarchy of communities reveals latent properties of the network. This task has real-world relevance in social network analysis, taxonomy, bioinformatics, and graph mining in general. Nevertheless, there is no common definition of a community and no common, efficient method of identifying communities. As is common, we formulate CD as optimization of modularity. Modularity quantifies the separation of a network into distinct, highly interconnected groups. Maximizing modularity is NP-hard.

To solve the optimization problem, we present a polynomial-time approximation method. It greedily maximizes modularity with a heuristic for sparsest cuts in a network. This involves maximizing max-min fair throughput between all pairs of network nodes. We evaluate the approximation’s effectiveness for CD on synthetic networks with known community structure. We show competitive results in terms of the standard measure of CD accuracy, normalized mutual information (NMI). Further, our method is less sensitive to network perturbations than existing community detection algorithms. Our method also detects ties in hierarchical structure, which other techniques do not.

In graphs without a strong community structure, our method does not impose arbitrary structure. In these cases, we can show that the max-min fair flow can be split onto edge-disjoint paths of a multigraph corresponding to the original network.