nested_partition_overlap_center

graph_tool.inference.nested_partition_overlap_center(bs, init=None, return_bs=False)

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)]