Memberships in communities that follow a spreading process

These functions follow a process as it spreads over the network, and read the communities off where it settles:

• node_in_infomap() is an algorithm based on the information in random walks.

• node_in_fluid() is a propogation-based partitioning algorithm, based on analogy to model from fluid dynamics.

• node_in_labels() is a fast, propagation-based algorithm in which nodes iteratively adopt whichever community label is most common among their neighbours.

They need no quality function, and are among the fastest algorithms, but each run can return a different partition. See member_community for a comparison with the other community detection algorithms.

node_in_infomap(.data, times = 50)

node_in_fluid(.data, k = NULL, max_k = 8L, Kmax = NULL)

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

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.

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.

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

These algorithms 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. Only node_in_spinglass() reads a sign as a sign. Use manynet::to_unsigned() first to control this yourself.

Infomap

Motivated by information theoretic principles, this algorithm tries to build a grouping that provides the shortest description length for a random walk, where the description length is measured by the expected number of bits per node required to encode the path.

Fluid

The general idea is to observe how a discrete number of fluids interact, expand and contract, in a non-homogenous environment, i.e. the network structure. Unlike the {igraph} implementation that this function wraps, this function iterates over all possible numbers of communities and returns the membership associated with the highest modularity.

Label propagation

Every node is initially given a unique label. Nodes are then visited in random order, each adopting whichever label is most frequent among its neighbours, until no node has a label that a majority of its neighbours does not share. Densely connected groups quickly converge on a common label, which is what makes the communities.

This is the fastest of the algorithms here, running in near-linear time, which makes it useful on large networks where the others are infeasible. The trade-off is that it is stochastic: because both the visiting order and ties between equally frequent labels are broken at random, repeated runs on the same network can return different partitions, and on sparse networks it may return a single community. Set a seed for reproducibility, or use node_in_community() to select among algorithms by modularity.

Where k is given, the algorithm becomes semi-supervised. The k nodes of highest degree are each given a distinct, fixed label, every other node starts with a label of its own, and propagation runs as normal. Seeding alone tends to leave more than k labels standing, so any surplus groups are then merged in the order that best preserves modularity, until exactly k communities remain.

References

On infomap community detection

Rosvall, M, and C. T. Bergstrom. 2008. "Maps of information flow reveal community structure in complex networks", PNAS 105:1118. doi:10.1073/pnas.0706851105

Rosvall, M., D. Axelsson, and C. T. Bergstrom. 2009. "The map equation", Eur. Phys. J. Special Topics 178: 13. doi:10.1140/epjst/e2010-01179-1

On fluid community detection

Parés Ferran, Dario Garcia Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguade, Jesus Labarta, Ulises Cortes, and Toyotaro Suzumura. 2018. "Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm". In: Complex Networks & Their Applications VI Springer, 689: 229. doi:10.1007/978-3-319-72150-7_19

On label propagation community detection

Raghavan, Usha Nandini, Reka Albert, and Soundar Kumara. 2007. "Near linear time algorithm to detect community structures in large-scale networks", Physical Review E, 76(3):036106. doi:10.1103/PhysRevE.76.036106

See also

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

Other memberships: member_brokerage, member_cliques, member_community, member_community_hier, member_community_link, member_community_modular, member_community_partition, 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_partition, member_components, member_core, member_diffusion, member_equivalence, motif_brokerage_node, motif_clique, motif_composition, motif_exposure, motif_node, motif_path

Examples

node_in_infomap(ison_adolescents)
#> 1 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     A     A     A     A     A     A    
node_in_fluid(ison_adolescents)
#> 3 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     C     C     C     B     B     B    
node_in_labels(ison_adolescents)
#> 2 groups
#>   Betty Sue   Alice Jane  Dale  Pam   Carol Tina 
#> 1 A     A     A     A     A     A     B     B