R/member_community.R
member_community_partition.RdThese 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.
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().
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.
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.
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.
Deprecated. The former spelling of max_k.
Still accepted, but warns; please use max_k instead.
Which measure of fit the factions should optimise. One of "hamming" (the default), "phi", or "modularity".
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.
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.
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().
For signed networks, node_in_partition() reads a sign as a sign:
a negative tie inside a group lowers the
weight that the swaps maximise, so negative ties are moved between groups.
Use manynet::to_unsigned() first to consider one sign alone.
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.
For signed networks, node_in_faction() reads a sign as a sign,
and the ideal is structural balance:
positive ties within the factions and negative ties between them.
"hamming" then counts the errors as Doreian and Mrvar (1996) do,
the negative ties within factions plus the positive ties between them,
and an absent tie is no error either way.
"phi" correlates the sign of each pair's tie with whether the pair
shares a faction, and "modularity" maximises signed modularity
(see net_by_modularity()).
Use manynet::to_unsigned() first to consider one sign alone.
Doreian, Patrick, and Andrej Mrvar. 1996. "A partitioning approach to structural balance". Social Networks 18(2): 149-168. doi:10.1016/0378-8733(95)00259-6
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
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.
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_accuracy_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_accuracy_node,
motif_brokerage_node,
motif_clique,
motif_composition,
motif_exposure,
motif_node,
motif_path
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 B B B B A A A
node_in_faction(ison_adolescents, k = 3, variant = "modularity")
#> 3 groups
#> Betty Sue Alice Jane Dale Pam Carol Tina
#> 1 C C A A A B B B