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)