Clique partitioning algorithms

Source: R/member_cliques.R

These functions create a vector of nodes' memberships in cliques:

  • node_in_roulette() assigns nodes to maximally diverse groups.

node_in_roulette(.data, num_groups, group_size, times = NULL)

Arguments

.data

An object of a manynet-consistent class:

  • matrix (adjacency or incidence) from {base} R

  • edgelist, a data frame from {base} R or tibble from {tibble}

  • igraph, from the {igraph} package

  • network, from the {network} package

  • tbl_graph, from the {tidygraph} package

num_groups

An integer indicating the number of groups desired.

group_size

An integer indicating the desired size of most of the groups. Note that if the number of nodes is not divisible into groups of equal size, there may be some larger or smaller groups.

times

An integer of the number of search iterations the algorithm should complete. By default this is the number of nodes in the network multiplied by the number of groups. This heuristic may be insufficient for small networks and numbers of groups, and burdensome for large networks and numbers of groups, but can be overwritten. At every 10th iteration, a stronger perturbation of a number of successive changes, approximately the number of nodes divided by the number of groups, will take place irrespective of whether it improves the objective function.

Maximally diverse grouping problem

This well known computational problem is a NP-hard problem with a number of relevant applications, including the formation of groups of students that have encountered each other least or least recently. Essentially, the aim is to return a membership of nodes in cliques that minimises the sum of their previous (weighted) ties:

$$\sum_{g=1}^{m} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} x_{ij} y_{ig} y_{jg}$$

where \(y_{ig} = 1\) if node \(i\) is in group \(g\), and 0 otherwise.

\(x_{ij}\) is the existing network data. If this is an empty network, the function will just return cliques. To run this repeatedly, one can join a clique network of the membership result with the original network, using this as the network data for the next round.

A form of the Lai and Hao (2016) iterated maxima search (IMS) is used here. This performs well for small and moderately sized networks. It includes both weak and strong perturbations to an initial solution to ensure that a robust solution from the broader state space is identified. The user is referred to Lai and Hao (2016) and Lai et al (2021) for more details.

References

On the maximally diverse grouping problem

Lai, Xiangjing, and Jin-Kao Hao. 2016. “Iterated Maxima Search for the Maximally Diverse Grouping Problem.” European Journal of Operational Research 254(3):780–800. doi:10.1016/j.ejor.2016.05.018 .

Lai, Xiangjing, Jin-Kao Hao, Zhang-Hua Fu, and Dong Yue. 2021. “Neighborhood Decomposition Based Variable Neighborhood Search and Tabu Search for Maximally Diverse Grouping.” European Journal of Operational Research 289(3):1067–86. doi:10.1016/j.ejor.2020.07.048 .