partition_overlap_center

graph_tool.inference.partition_overlap_center(bs, init=None, relabel_bs=False)

Find a partition with a maximal overlap to all items of the list of partitions given.

Parameters:

bslist of iterables of int values or list of PropertyMap

List of partitions.

inititerable of int values (optional, default: None)

If given, it will determine the initial partition.

relabel_bsbool (optional, default: False)

If True the given list of partitions will be updated with relabelled values.

Returns:

cnumpy.ndarray

Partition containing the overlap consensus.

rfloat

Uncertainty in range \([0,1]\).

Notes

This algorithm obtains a partition \(\hat{\boldsymbol b}\) that has a maximal sum of overlaps with all partitions given in bs. It is obtained by performing the double maximization:

\[\begin{split}\begin{aligned} \hat b_i &= \underset{r}{\operatorname{argmax}}\;\sum_m \delta_{\mu_m(b^m_i), r}\\ \boldsymbol\mu_m &= \underset{\boldsymbol\mu}{\operatorname{argmax}} \sum_rm_{r,\mu(r)}^{(m)}, \end{aligned}\end{split}\]

where \(\boldsymbol\mu\) is a bijective mapping between group labels, and \(m_{rs}^{(m)}\) is the contingency table between \(\hat{\boldsymbol b}\) and \(\boldsymbol b ^{(m)}\). This algorithm simply iterates the above equations, until no further improvement is possible.

The uncertainty is given by:

\[r = 1 - \frac{1}{NM} \sum_i \sum_m \delta_{\mu_m(b^m_i), \hat b_i}\]

This algorithm runs in time \(O[M(N + B^3)]\) where \(M\) is the number of partitions, \(N\) is the length of the partitions and \(B\) is the number of labels used.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

References

[peixoto-revealing-2021]

Tiago P. Peixoto, “Revealing consensus and dissensus between network partitions”, Phys. Rev. X 11 021003 (2021) DOI: 10.1103/PhysRevX.11.021003 [sci-hub, @tor], arXiv: 2005.13977

Examples

>>> x = [5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 0]
>>> bs = []
>>> for m in range(100):
...     y = np.array(x)
...     y[np.random.randint(len(y))] = np.random.randint(5)
...     bs.append(y)
>>> bs[:3]
[array([5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 3]), array([5, 5, 2, 0, 4, 0, 1, 0, 0, 0, 0]), array([5, 5, 1, 0, 1, 0, 1, 0, 0, 0, 0])]
>>> c, r = gt.partition_overlap_center(bs)
>>> print(c, r)
[1 1 2 0 3 0 3 0 0 0 0] 0.06818181...
>>> gt.align_partition_labels(c, x)
array([5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 0], dtype=int32)