  To understand how a complex system is organized and functions, researchers
often identify communities in the system's network of interactions. Because it
is practically impossible to explore all solutions to guarantee the best one,
many community-detection algorithms rely on multiple stochastic searches. But
for a given combination of network and stochastic algorithm, how many searches
are sufficient to find a solution that is good enough? The standard approach is
to pick a reasonably large number of searches and select the network partition
with the highest quality or derive a consensus solution based on all network
partitions. However, if different partitions have similar qualities such that
the solution landscape is degenerate, the single best partition may miss
relevant information, and a consensus solution may blur complementary
communities. Here we address this degeneracy problem with coarse-grained
descriptions of the solution landscape. We cluster network partitions based on
their similarity and suggest an approach to determine the minimum number of
searches required to describe the solution landscape adequately. To make good
use of all partitions, we also propose different ways to explore the solution
landscape, including a significance clustering procedure. We test these
approaches on synthetic networks and a real-world network using two contrasting
community-detection algorithms: The algorithm that can identify more general
structures requires more searches and networks with clearer community
structures require fewer searches. We also find that exploring the
coarse-grained solution landscape can reveal complementary solutions and enable
more reliable community detection.
