Memberships in communities that fill a set number of groups

These functions divide the nodes into a number of groups that you set, two by default:

• node_in_partition() is a greedy, iterative, deterministic partitioning algorithm that results in two equally-sized communities.

• node_in_faction() is a tabu search for the k groups, of any size, that come closest to being separate cliques.

Since they return the number of groups asked for whether or not the network holds that many communities, check the fit of the result, e.g. with net_by_modularity(). See member_community for a comparison with the other community detection algorithms.

node_in_partition(
  .data,
  k = 2L,
  max_k = 8L,
  start = c("order", "random"),
  Kmax = NULL
)

node_in_faction(
  .data,
  k = 2L,
  variant = c("hamming", "phi", "modularity"),
  times = 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().

k

Integer indicating the target number of communities to return. By default NULL, in which case the algorithm returns the number of communities that it finds itself. Alternatively, a character string naming a selection method: "silhouette" selects the number that maximises the mean silhouette width over geodesic distances, "elbow" selects the number at the elbow of the coverage curve, and "strict" returns the partition in which no tie crosses a group, i.e. the components. Prefer "silhouette"; the elbow method is unreliable where the coverage curve has no clear elbow. If the algorithm cannot return exactly the number of communities requested, a warning is given and the nearest number is returned.

max_k

Integer indicating the maximum number of communities to evaluate for "silhouette" and "elbow". By default 8. Otherwise ignored. Note that for node_in_louvain() and node_in_leiden() each candidate requires its own search over the resolution parameter, so a large max_k is costly on large networks.

start

One of "order" (the default) or "random", naming how the nodes are dealt into the groups to begin with. "order" deals them in node order, which makes the algorithm deterministic. "random" deals them at random, as Kernighan and Lin do. Since the algorithm is sensitive to where it starts, a random start can reach a different partition; set a seed to repeat one.

Kmax

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

variant

Which measure of fit the factions should optimise. One of "hamming" (the default), "phi", or "modularity".

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.

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.

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

Signed networks

node_in_faction() reads a tie as a pull into the same community, and a negative tie is hostility rather than such a pull. Where the network is signed, it therefore considers only the positive ties, and says so. Use manynet::to_unsigned() first to control this yourself.

Partition

The general idea is to assign nodes to two groups, and then iteratively swap pairs of nodes (one from each group) that give a positive sum of net tie costs, where the net tie cost of a node is the difference between the sum of the weights of ties to nodes in the other group (external costs) and the sum of the weights of ties to nodes in the same group (internal costs). A pass exchanges the candidate pairs one at a time and keeps the prefix that leaves the most weight inside the two groups, so a pass never returns a worse split than it started from. Where k is greater than two, the same swap pass is run for every pair of groups, and the rounds repeat until no pass improves the partition. Where start = "order", the default, the nodes are dealt into the groups in node order, and the algorithm is deterministic: one network returns one partition. Where start = "random" they are dealt at random, which is the textbook start, and repeated calls can then return different partitions. The result is not guaranteed to maximise modularity either way, since the algorithm reads the weight of the ties inside the groups and not the modularity, and since it holds the groups at equal size. Note that this algorithm is only applicable to undirected, unipartite networks, and returns k communities of equal size (or as close to equal as possible). For k groups that are free to take any size, see node_in_faction().

Faction

The general idea is that a network of factions is one of separate cliques: every pair of nodes in the same group is tied, and no pair in different groups is. node_in_faction() searches for the partition into k groups that comes closest to that ideal, using a tabu search; see search_tabu() for how it works. Unlike node_in_partition(), the groups are free to take any size, and unlike node_in_optimal(), the number of groups is yours to choose.

variant names how closeness to the ideal is scored:

• "hamming" (the default) counts the errors: the pairs within a group that are not tied plus the pairs in different groups that are.

• "phi" is the correlation between the network and the ideal, with ones for pairs in the same group and zeros for pairs in different groups.

• "modularity" is the share of ties that fall within groups less the share expected if ties fell at random among nodes of the same degrees.

"hamming" and "phi" read the pattern of ties and not their weights, and "modularity" reads a directed network as undirected.

Some care is needed in reading the result. The search always returns k groups, however poor the best fit is, so the groups it returns need not be cohesive: check the fit with net_by_modularity() or net_by_inconsistency(). The search may also end in a local minimum, and it returns one partition even where several fit equally well. Since it begins from random partitions, repeated calls can return different partitions; where they agree, the split is a clear one. Set a seed to repeat a result.

Note that k must be an integer here, since the search needs to know how many groups to fill, and that times is by default the number of nodes multiplied by k.

References

On partitioning community detection

Kernighan, Brian W., and Shen Lin. 1970. "An efficient heuristic procedure for partitioning graphs." The Bell System Technical Journal 49(2): 291-307. doi:10.1002/j.1538-7305.1970.tb01770.x

On faction community detection

de Amorim, Samuel G., Jean-Pierre Barthélemy, and Celso C. Ribeiro. 1992. "Clustering and clique partitioning: Simulated annealing and tabu search approaches." Journal of Classification 9(1): 17-41. doi:10.1007/BF02618466

Borgatti, Stephen P., Martin G. Everett, and Linton C. Freeman. 2002. UCINET for Windows: Software for Social Network Analysis. Harvard, MA: Analytic Technologies.

See also

Other community: member_community, member_community_hier, member_community_link, member_community_modular, member_community_spread

Other memberships: member_brokerage, member_cliques, member_community, member_community_hier, member_community_link, member_community_modular, 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_cliques, member_community, member_community_hier, member_community_modular, 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_partition(ison_adolescents)
#> 2 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 B     A     A     A     A     B     B     B    
node_in_partition(ison_southern_women)
#> 2 groups
#>   Evelyn Laura Theresa Brenda Charlotte Frances Eleanor Pearl Ruth  Verne Myra 
#> 1 A      A     A       A      A         A       A       B     A     B     B    
#> # ... and 7 more values from this nodeset. Use `print_all(...)` to print all values.
#>   E1    E2    E3    E4    E5    E6    E7    E8    E9    E10   E11   E12   E13  
#> 1 A     A     A     A     A     A     A     A     B     B     B     B     B    
#> # ... and 1 more values from this nodeset. Use `print_all(...)` to print all values.
node_in_faction(ison_adolescents)
#> 2 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 B     A     A     A     A     A     B     B    
node_in_faction(ison_adolescents, k = 3, variant = "modularity")
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     B     B     B     C     C     C