Memberships in communities that optimise a quality function

These functions score a partition with a quality function, such as modularity, and search for the partition that scores best:

• node_in_optimal() is a problem-solving algorithm that seeks to maximise modularity over all possible partitions.

• node_in_spinglass() is a greedy, iterative, probabilistic algorithm, based on analogy to model from statistical physics.

• node_in_louvain() is an agglomerative multilevel algorithm that seeks to maximise modularity over all possible partitions.

• node_in_leiden() is an agglomerative multilevel algorithm that seeks to maximise the Constant Potts Model over all possible partitions.

They differ in the quality function, in how thoroughly they search, and so in how large a network they can be used on. See member_community for a comparison with the other community detection algorithms.

node_in_optimal(.data)

node_in_spinglass(.data, max_k = 200, resolution = 1)

node_in_louvain(.data, k = NULL, max_k = 8L, resolution = 1, Kmax = NULL)

node_in_leiden(.data, k = NULL, max_k = 8L, resolution = NULL, Kmax = 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().

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.

resolution

The Reichardt-Bornholdt “gamma” resolution parameter for modularity. By default 1, making existing and non-existing ties equally important. Smaller values make existing ties more important, and larger values make missing ties more important. node_in_leiden() takes NULL by default, and then uses the density of the network, since the Constant Potts Model gives every node its own community at any higher resolution.

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.

Kmax

Deprecated. The former spelling of max_k. Still accepted, but warns; please use max_k 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.

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_optimal() and node_in_louvain() read a tie's weight as the strength of a pull into the same community, and a negative tie is hostility rather than such a pull. Where the network is signed, they therefore consider only the positive ties, and say so. node_in_spinglass() reads a sign as a sign. Use manynet::to_unsigned() first to control this yourself.

Optimal

The general idea is to calculate the modularity of all possible partitions, and choose the community structure that maximises this modularity measure. Note that this is an NP-complete problem with exponential time complexity. The guidance in the igraph package is networks of <50-200 nodes is probably fine.

Spin-glass

Here max_k is the number of spins, an upper limit on the communities found rather than a bound on a search, so some can end up empty.

This is motivated by analogy to the Potts model in statistical physics. Each node can be in one of k "spin states", and ties (particle interactions) provide information about which pairs of nodes want similar or different spin states. The final community definitions are represented by the nodes' spin states after a number of updates. A different implementation than the default is used in the case of signed networks, such that nodes connected by negative ties will be more likely found in separate communities.

Louvain

The general idea is to take a hierarchical approach to optimising the modularity criterion. Nodes begin in their own communities and are re-assigned in a local, greedy way: each node is moved to the community where it achieves the highest contribution to modularity. When no further modularity-increasing reassignments are possible, the resulting communities are considered nodes (like a reduced graph), and the process continues. Where k is given, the resolution parameter is searched for the value that returns that number of communities, and resolution is ignored.

Leiden

The general idea is to optimise the Constant Potts Model, which does not suffer from the resolution limit, instead of modularity. As outlined in the {igraph} package, the Constant Potts Model object function is:

$$\frac{1}{2m} \sum_{ij}(A_{ij}-\gamma n_i n_j)\delta(\sigma_i, \sigma_j)$$

where m is the total tie weight, \(A_{ij}\) is the tie weight between i and j, \(\gamma\) is the so-called resolution parameter, \(n_i\) is the node weight of node i, and \(\delta(\sigma_i, \sigma_j) = 1\) if and only if i and j are in the same communities and 0 otherwise. Compared to the Louvain method, the Leiden algorithm additionally tries to avoid unconnected communities. The resolution is the density of the network by default, after Traag et al., since the Constant Potts Model gives every node its own community at any higher resolution. This holds for an unweighted network too, where each tie weighs 1. Where k is given, the resolution parameter is searched for the value that returns that number of communities, and resolution is ignored.

References

On optimal community detection

Brandes, Ulrik, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner. 2008. "On Modularity Clustering", IEEE Transactions on Knowledge and Data Engineering 20(2):172-188.

On spinglass community detection

Reichardt, Jorg, and Stefan Bornholdt. 2006. "Statistical Mechanics of Community Detection" Physical Review E, 74(1): 016110–14. doi:10.1073/pnas.0605965104

Traag, Vincent A., and Jeroen Bruggeman. 2009. "Community detection in networks with positive and negative links". Physical Review E, 80(3): 036115. doi:10.1103/PhysRevE.80.036115

On Louvain community detection

Blondel, Vincent, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. 2008. "Fast unfolding of communities in large networks", J. Stat. Mech. P10008.

On Leiden community detection

Traag, Vincent A., Ludo Waltman, and Nees Jan van Eck. 2019. "From Louvain to Leiden: guaranteeing well-connected communities", Scientific Reports, 9(1):5233. doi:10.1038/s41598-019-41695-z

See also

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

Other memberships: member_brokerage, member_cliques, member_community, member_community_hier, member_community_link, 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_cliques, member_community, member_community_hier, 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_optimal(ison_adolescents)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     B     B     B     C     C     C    
node_in_spinglass(ison_adolescents)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 C     C     B     B     B     A     A     A    
node_in_louvain(ison_adolescents)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     B     B     B     C     C     C    
node_in_leiden(ison_adolescents)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     B     B     B     B     B     C     C