Probabilistic community detection in networks

Standard community detection methods for networks provide “hard calls”: a specification of which nodes belong to which groups with no indication of the confidence of these assessments. Here, a simple formula is presented which provides the probability of a node belonging to a group. An efficient method is then presented for determining the probability of any pair of nodes being in the same group, without reference to any one, fixed group structure. These pairwise co-membership probabilities can be used directly to enable certain analyses of group structure, or can be converted into a distance metric which enables a different class of analyses. As an example, we demonstrate how this co-membership distance matrix can be used to find a community structure that is both overlapping and hierarchical using a topological technique inspired by Morse theory to partially cluster with respect to the distance metric.