Representative community divisions of networks

Methods for detecting community structure in networks typically aim to identify a single best partition of network nodes into communities, often by optimizing some objective function, but in real-world applications there may be many competitive partitions with objective scores close to the global optimum and one can obtain a more informative picture of the community structure by examining a representative set of such high-scoring partitions than by looking at just the single optimum. However, such a set can be difficult to interpret since its size can easily run to hundreds or thousands of partitions. In this paper we present a method for analyzing large partition sets by dividing them into groups of similar partitions and then identifying an archetypal partition as a representative of each group. The resulting set of archetypal partitions provides a succinct, interpretable summary of the form and variety of community structure in any network. We demonstrate the method on a range of example networks. Community detection is a common task in the analysis of network data but most current community detection algorithms provide either only a single partition or a very large number of plausible ones, neither of which gives an interpretable summary of the possible structures. Here the authors provide a solution to this problem, in the form of an algorithm based on the minimum description length principle that identifies minimal sets of archetypal, highly representative partitions of a network that succinctly summarize the plausible community structures.

Automated summary

Researchers propose a method for analyzing large partition sets in network community detection, which divides them into groups of similar partitions and identifies an archetypal partition as a representative of each group, providing a succinct and interpretable summary of community structure in any network.