Consensus Clustering

Clustering techniques don’t always produce a single answer. Consensus clustering takes each of these answers and combines them into a better graph.

Algorithm is:

1. Apply clustering algorithm $A$ on graph $G$ $n_p$ times, yielding $n_p$ partitions.
2. Compute the consensus matrix $D$: $D_{ij}$ is the number of partitions in which vertices $i$ and $j$ of $G$ are assigned to the same community, divided by $n_p$.
3. All entries of $D$ below a chosen threshold $\tau$ are set to zero.
4. Apply $A$ on $D$ $n_p$ times, yielding $n_p$ partitions.
5. If the partitions are all equal, stop. Otherwise, go back to 2.

Because the result is a weighted network, the algorithm $A$ has to be able to work w/ weighted graphs.