Memberships in maximally diverse cliques

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

• node_in_roulette() assigns nodes to maximally diverse groups.

node_in_roulette(
  .data,
  groups,
  group_size,
  times = NULL,
  decay = 1,
  attribute = NULL,
  balance = 0.5,
  num_groups = NULL
)

Arguments

.data

A network object of class stocnet, igraph, tbl_graph, network, or similar. Internally any of these will be coerced to an efficient implementation. For more information on possible coercions, see e.g. manynet::as_stocnet().

groups

An integer indicating the number of groups desired, or a vector of the size of each group, which must sum to the number of nodes. The groups then keep exactly these sizes.

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

Integer scalar, how many times the algorithm repeats its work. Where the algorithm is stochastic, this is how many times it runs, and the best or the most frequent result is kept. Where the algorithm searches, this is how many steps the search takes. More repetitions give a more reliable result and take longer, so each function documents its own default.

decay

A proportion between 0 and 1 by which a tie in a longitudinal or dynamic network is discounted for each wave or unit of time before the latest. By default 1, so that every earlier tie costs the same.

attribute

Optionally, the name of a node attribute, or a vector with a value for each node, on which the groups should be mixed.

balance

A proportion between 0 and 1 that weighs mixing on the attribute against keeping tied nodes apart. By default 0.5.

num_groups

Deprecated. The former spelling of groups. Still accepted, but warns; please use groups instead.

Value

A node_member character vector the length of the nodes in the network, of group memberships "A", "B", etc for each node. If the network is labelled, then the assignments will be labelled with the nodes' names.

Details

times defaults to the number of nodes multiplied by the number of groups. This heuristic may be insufficient for small networks and numbers of groups, and burdensome for large ones, but can be overwritten. Each iteration makes a weak perturbation, and keeps it only if it improves the objective function. At every 10th iteration, the search starts again from a stronger perturbation of the best solution so far, a number of successive changes approximately the number of nodes divided by the number of groups.

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.

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.

Repeated rounds

The history of earlier rounds is held in the network data. A weighted network costs each pair by the weight of their tie. A longitudinal network, with a wave for each earlier round, or a dynamic network, with a time (or begin and end) for each tie, costs each tie by decay for each wave or unit of time before the latest. With decay = 1, every earlier meeting costs the same; with decay = 0, only the latest meetings cost anything. A date is discounted for each day.

To record a new round, add the membership's ties to the network as a new wave, as in the examples.

Mixing on an attribute

Where an attribute is given, the function also places nodes that differ on that attribute in the same group, as in the diversity-based assignment of the grouper package. Both costs are first scaled to \([0,1]\). A categorical attribute costs a pair 1 where their categories differ, and a numeric attribute costs a pair their absolute difference over its maximum. balance then weighs the attribute against the ties: 0 considers only the ties, and 1 only the attribute.

Cognitive social structures

A cognitive social structure records each node's report of the ties in the whole network, in a by column that names who reported each tie. Counting every report as a tie of its own would count each tie once for every perceiver who reports it. So the functions here first combine the reports into the locally aggregated structure of Krackhardt (1987), with the intersection rule: a tie exists if both of its ends report it, and a message says so. A tie that names no reporter is kept as it is.

A tie-level function still returns one value for each report, so that the result can be added back to the network it was given. Each report takes the value of the tie that it reports. A report of a tie that is not in the aggregated structure takes NA, or FALSE for a mark. tie_is_random() is the exception, and draws among the reports.

To combine the reports in a different way, do this before the function, e.g. with manynet::to_aggregated(over = "by").

Krackhardt, David. 1987. "Cognitive social structures". Social Networks 9(2): 109-134. doi:10.1016/0378-8733(87)90009-8

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 .

See also

Other memberships: member_brokerage, member_community, member_community_hier, member_community_link, member_community_modular, member_community_partition, member_community_spread, member_components, member_core, member_diffusion, member_equivalence

Other nodal: mark_core, mark_degree, mark_diff, mark_nodes, mark_select_node, measure_assort_node, measure_broker_node, measure_brokerage, measure_central_between, measure_central_close, measure_central_degree, measure_central_eigen, measure_closure_node, measure_core, measure_diffusion_node, measure_diverse_node, member_brokerage, member_community, member_community_hier, member_community_modular, member_community_partition, member_community_spread, member_components, member_core, member_diffusion, member_equivalence, motif_brokerage_node, motif_clique, motif_composition, motif_exposure, motif_node, motif_path

Examples

node_in_roulette(ison_adolescents, groups = 3)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 C     A     B     A     C     C     A     B    
# Mix the groups on an attribute
marvel_friends <- to_unsigned(to_uniplex(fict_marvel, "relationship"), "positive")
node_in_roulette(marvel_friends, groups = 3, attribute = "Gender")
#> 3 groups
#>   Abomination `Ant-Man` Apocalypse Beast `Black Panther` `Black Widow` Blade
#> 1 C           A         C          C     B               C             B    
#> # ... and 46 more values from this nodeset. Use `print_all(...)` to print all values.
# Record three rounds as waves, discounting older meetings by half
net <- create_empty(8)
for(round in 1:3){
  grp <- node_in_roulette(net, group_size = 4, decay = 0.5)
  pairs <- which(outer(grp, grp, "==") & upper.tri(diag(8)), arr.ind = TRUE)
  net <- add_ties(net, pairs, attr_list = list(time = rep(round, nrow(pairs))))
}
net
#> 
#> ── # Empty network ─────────────────────────────────────────────────────────────
#> # A longitudinal, undirected network of 8 nodes and 36 ties over 3 waves
#> 
#> ── Ties 
#> # A tibble: 36 × 3
#>    from    to  time
#>   <int> <int> <int>
#> 1     1     2     1
#> 2     3     4     1
#> 3     1     5     1
#> 4     2     5     1
#> 5     3     6     1
#> 6     4     6     1
#> # ℹ 30 more rows
#>