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_bs
bool
(optional, default:False
) If
True
the given list of partitions will be updated with relabelled values.
- bslist of iterables of
- Returns:
- c
numpy.ndarray
Partition containing the overlap consensus.
- r
float
Uncertainty in range \([0,1]\).
- c
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)