R/member_community.R
member_community_non.Rd
These functions offer algorithms for partitioning networks into sets of communities:
node_in_optimal()
is a problem-solving algorithm that seeks to maximise
modularity over all possible partitions.
node_in_partition()
is a greedy, iterative, deterministic
partitioning algorithm that results in two equally-sized communities.
node_in_infomap()
is an algorithm based on the information in random walks.
node_in_spinglass()
is a greedy, iterative, probabilistic algorithm,
based on analogy to model from statistical physics.
node_in_fluid()
is a propogation-based partitioning algorithm,
based on analogy to model from fluid dynamics.
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.
The different algorithms offer various advantages in terms of computation time, availability on different types of networks, ability to maximise modularity, and their logic or domain of inspiration.
node_in_optimal(.data)
node_in_partition(.data)
node_in_infomap(.data, times = 50)
node_in_spinglass(.data, max_k = 200, resolution = 1)
node_in_fluid(.data)
node_in_louvain(.data, resolution = 1)
node_in_leiden(.data, resolution = 1)
An object of a manynet-consistent class:
matrix (adjacency or incidence) from {base}
R
edgelist, a data frame from {base}
R or tibble from {tibble}
igraph, from the {igraph}
package
network, from the {network}
package
tbl_graph, from the {tidygraph}
package
Integer indicating number of simulations/walks used.
By default, times=50
.
Integer constant, the number of spins to use as an upper limit of communities to be found. Some sets can be empty at the end.
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.
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.
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.
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.
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.
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.
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.
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.
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
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
Reichardt, Jorg, and Stefan Bornholdt. 2006. "Statistical Mechanics of Community Detection" Physical Review E, 74(1): 016110–14. doi:10.1073/pnas.0605965104
Traag, VA, and Jeroen Bruggeman. 2008. "Community detection in networks with positive and negative links".
Parés F, Gasulla DG, et. al. 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
Blondel, Vincent, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. 2008. "Fast unfolding of communities in large networks", J. Stat. Mech. P10008.
Traag, V. A., L Waltman, and NJ van Eck. 2019. "From Louvain to Leiden: guaranteeing well-connected communities", Scientific Reports, 9(1):5233. doi:10.1038/s41598-019-41695-z
Other memberships:
mark_core
,
member_cliques
,
member_community_hier
,
member_components
,
member_equivalence
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_partition(ison_adolescents)
#> 2 groups
#> Betty Sue Alice Jane Dale Pam Carol Tina
#> 1 A B B A A A B B
node_in_partition(ison_southern_women)
#> 2 groups
#> Evelyn Laura Theresa Brenda Charlotte Frances Eleanor Pearl Ruth Verne Myra
#> 1 B B B B B B B B B B B
#> # ... with 7 more values from this nodeset unprinted. Use `print(..., n = Inf)` 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 A A A A A
#> # ... with 1 more values from this nodeset unprinted. Use `print(..., n = Inf)` to print all values.
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_spinglass(ison_adolescents)
#> 3 groups
#> Betty Sue Alice Jane Dale Pam Carol Tina
#> 1 A A C C C B B B
node_in_fluid(ison_adolescents)
#> 3 groups
#> Betty Sue Alice Jane Dale Pam Carol Tina
#> 1 A A B B B B C C
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)
#> 8 groups
#> Betty Sue Alice Jane Dale Pam Carol Tina
#> 1 A B C D E F G H