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_bs
bool
(optional, default:False
) If
True
the an update list of nested partitions will be return with relabelled values.
- bslist of list of iterables of
- Returns:
- cList of
numpy.ndarray
Nested partition containing the overlap consensus.
- r
float
Uncertainty in range \([0,1]\).
- bsList of lists of
numpy.ndarray
List of relabelled nested partitions.
- cList of
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)]