# nested_partition_overlap_center#

graph_tool.inference.nested_partition_overlap_center(bs, init=None, return_bs=False)[source]#

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

Parameters:
bslist of list of iterables of int values or list of list of PropertyMap

List of nested partitions.

inititerable of iterables of int values (optional, default: None)

If given, it will determine the initial nested partition.

return_bsbool (optional, default: False)

If True the an update list of nested partitions will be return with relabelled values.

Returns:
cList of numpy.ndarray

Nested partition containing the overlap consensus.

rfloat

Uncertainty in range $$[0,1]$$.

bsList of lists of numpy.ndarray

List of relabelled nested partitions.

Notes

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

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

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

The uncertainty is given by:

$r = 1 - \frac{1}{N-L}\sum_l\frac{N_l-1}{N_l}\sum_i\frac{1}{M}\sum_m \delta_{\mu_m(b^{l,m}_i), \hat b_i^l}.$

This algorithm runs in time $$O[M\sum_l(N_l + B_l^3)]$$ where $$M$$ is the number of partitions, $$N_l$$ is the length of the partitions and $$B_l$$ is the number of labels used, in level $$l$$.

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], [0, 1, 0, 1, 1, 1]]
>>> bs = []
>>> for m in range(100):
...     y = [np.array(xl) for xl in x]
...     y[0][np.random.randint(len(y[0]))] = np.random.randint(5)
...     y[1][np.random.randint(len(y[1]))] = np.random.randint(2)
...     bs.append(y)
>>> bs[:3]
[[array([5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 3]), array([0, 1, 0, 1, 1, 1])], [array([5, 5, 2, 0, 1, 0, 4, 0, 0, 0, 0]), array([0, 1, 1, 1, 1, 1])], [array([5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 2]), array([0, 1, 0, 1, 1, 1])]]
>>> c, r = gt.nested_partition_overlap_center(bs)
>>> print(c, r)
[array([1, 1, 2, 0, 3, 0, 3, 0, 0, 0, 0], dtype=int32), array([0, 1, 0, 1, 1], dtype=int32)] 0.069385...
>>> gt.align_nested_partition_labels(c, x)
[array([5, 5, 2, 0, 1, 0, 1, 0, 0, 0, 0], dtype=int32), array([ 0,  1,  0, -1, -1,  1], dtype=int32)]