Measures for the overall similarity of partitions $\mathcal{P}=\{P_1,\dots,P_{\vert\mathcal{P}\vert}\}$ and $\mathcal{P}'=\{P'_1,\dots,P'_{\vert\mathcal{P}'\vert}\}$ of the same set $V$ do not provide specifics on how $\mathcal{P}$ and $\mathcal{P}'$ correspond, e.g., when the union of two parts in $\mathcal{P}$ is similar to that of three parts in $\mathcal{P}'$. #R##N#We think of a good correspondence between $\mathcal{P}$ and $\mathcal{P}'$ as a pair $(\mathcal{S},\mathcal{S}')$ with $\mathcal{S}\subseteq\mathcal{P}$, $\mathcal{S}'\subseteq \mathcal{P}'$ and a low value of $\vert(\bigcup_{S\in\mathcal{S}}S)\triangle(\bigcup_{S'\in\mathcal{S}'}S')\vert$, where $\triangle$ and $\vert\cdot\vert$ denote symmetric difference and cardinality [total weight] if the elements of $V$ are unweighted [weighted]. Such an objective function is essentially one for $\mathcal{S}\subseteq\mathcal{P}$ only and yields the weight of the cut $(\mathcal{S},\mathcal{P} \setminus \mathcal{S})$ w.r.t. $\mathcal{P}'$}. #R##N#Thus, we can derive a hierarchy of the $\vert\mathcal{P}-1\vert$ best correspondences from a minimal cut basis of $\mathcal{P}$. A minimal $P_s$-$P_t$ cut can be computed in time $O(\vert V\vert+\vert\mathcal{P}\vert^4\vert\mathcal{P}'\vert)$. #R##N#To reduce the running time in practice, we present a branch-and-bound algorithm for finding minimal $P_s$-$P_t$ cuts. When the entire cut basis needs to be computed, the algorithm is feasible up to $\vert\mathcal{P}\vert,\vert\mathcal{P}'\vert$ around 1000. The number of elements in $V$ can be neglected. #R##N#Finally, we use correspondences to gain insight into a parallel community detection algorithm that is non-deterministic due to race conditions and that has an optional refinement phase. It turns out that the race conditions frequently entail unions or break-ups of communities, while the refinement leaves most communities intact.
['Roland Glantz', 'Christian L. Staudt', 'Henning Meyerhenke']
Correspondences between partitions