# graph_tool.inference.partition_overlap_center#

graph_tool.inference.partition_overlap_center(bs, init=None, relabel_bs=False)[source]#

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

Parameters:
bslist of iterables of int values

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.

If enabled during compilation, this algorithm runs in parallel.

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)