graph_tool.inference.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

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\).

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