Enumerating Communities for a Deeper Understanding of Community Finding

To advance the current state of the practice of community finding within networks, this paper presents algorithms for exploring the range of possible assignments of nodes to communities. One algorithm is an efficient method for enumerating the assignments. The second algorithm is an unranking of assignments, i.e. it is an algorithm for generating the assignment corresponding to a given rank in the numbering of assignments. Both of these algorithms are parallelizable. The unranking algorithm can also be used to generate sample assignments (e.g. for Monte Carlo) by using random rank numbers. The following discoveries we have made using these algorithms have important ramifications for the practice of community finding: 1) the distribution of metrics over the range of assignments appears to be normal, 2) the curve for finding the best number of communities is almost always U shaped, and 3) it is likely that the best solutions for a network will have varied characteristics