community  R Documentation 
These functions offer different algorithms useful for partitioning networks into sets of communities:
node_optimal()
is a problemsolving algorithm that seeks to maximise
modularity over all possible partitions.
node_kernaghinlin()
is a greedy, iterative, deterministic
partitioning algorithm that results in two equallysized communities.
node_edge_betweenness()
is a hierarchical, decomposition algorithm
where edges are removed in decreasing order of the number of
shortest paths passing through the edge.
node_fast_greedy()
is a hierarchical, agglomerative algorithm,
that tries to optimize modularity in a greedy manner.
node_leading_eigen()
is a topdown, hierarchical algorithm.
node_walktrap()
is a hierarchical, agglomerative algorithm based on random walks.
node_infomap()
is a hierarchical algorithm based on the information in random walks.
node_spinglass()
is a greedy, iterative, probabilistic algorithm,
based on analogy to model from statistical physics.
node_fluid()
is a propogationbased partitioning algorithm,
based on analogy to model from fluid dynamics.
node_louvain()
is an agglomerative multilevel algorithm that seeks to maximise
modularity over all possible partitions.
node_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_optimal(.data)
node_kernighanlin(.data)
node_edge_betweenness(.data)
node_fast_greedy(.data)
node_leading_eigen(.data)
node_walktrap(.data, times = 50)
node_infomap(.data, times = 50)
node_spinglass(.data, max_k = 200, resolution = 1)
node_fluid(.data)
node_louvain(.data, resolution = 1)
node_leiden(.data, resolution = 1)
.data 
An object of a

times 
Integer indicating number of simulations/walks used.
By default, 
max_k 
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. 
resolution 
The ReichardtBornholdt “gamma” resolution parameter for modularity. By default 1, making existing and nonexisting 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 NPcomplete problem with exponential time complexity. The guidance in the igraph package is networks of <50200 nodes is probably fine.
This is motivated by the idea that edges connecting different groups are more likely to lie on multiple shortest paths when they are the only option to go from one group to another. This method yields good results but is very slow because of the computational complexity of edgebetweenness calculations and the betweenness scores have to be recalculated after every edge removal. Networks of ~700 nodes and ~3500 ties are around the upper size limit that are feasible with this approach.
Initially, each node is assigned a separate community. Communities are then merged iteratively such that each merge yields the largest increase in the current value of modularity, until no further increases to the modularity are possible. The method is fast and recommended as a first approximation because it has no parameters to tune. However, it is known to suffer from a resolution limit.
In each step, the network is bifurcated such that modularity increases most. The splits are determined according to the leading eigenvector of the modularity matrix. A stopping condition prevents tightly connected groups from being split further. Note that due to the eigenvector calculations involved, this algorithm will perform poorly on degenerate networks, but will likely obtain a higher modularity than fastgreedy (at some cost of speed).
The general idea is that random walks on a network are more likely to stay within the same community because few edges lead outside a community. By repeating random walks of 4 steps many times, information about the hierarchical merging of communities is collected.
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 nonhomogenous 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 reassigned in a local, greedy way: each node is moved to the community where it achieves the highest contribution to modularity. When no further modularityincreasing 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 socalled 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):172188.
Kernighan, Brian W., and Shen Lin. 1970. "An efficient heuristic procedure for partitioning graphs." The Bell System Technical Journal 49(2): 291307. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1002/j.15387305.1970.tb01770.x")}
Newman, M, and M Girvan. 2004. "Finding and evaluating community structure in networks." Physical Review E 69: 026113.
Clauset, A, MEJ Newman, MEJ and C Moore. "Finding community structure in very large networks."
Newman, MEJ. 2006. "Finding community structure using the eigenvectors of matrices" Physical Review E 74:036104.
Pons, Pascal, and Matthieu Latapy "Computing communities in large networks using random walks".
Rosvall, M, and C. T. Bergstrom. 2008. "Maps of information flow reveal community structure in complex networks", PNAS 105:1118. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1073/pnas.0706851105")}
Rosvall, M., D. Axelsson, and C. T. Bergstrom. 2009. "The map equation", Eur. Phys. J. Special Topics 178: 13. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1140/epjst/e2010011791")}
Reichardt, Jorg, and Stefan Bornholdt. 2006. "Statistical Mechanics of Community Detection" Physical Review E, 74(1): 016110–14. \Sexpr[results=rd]{tools:::Rd_expr_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. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1007/9783319721507_19")}
Blondel, Vincent, JeanLoup 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 wellconnected communities", Scientific Reports, 9(1):5233. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1038/s4159801941695z")}
Other memberships:
cliques
,
components()
,
core
,
equivalence
node_optimal(ison_adolescents)
node_kernighanlin(ison_adolescents)
node_kernighanlin(ison_southern_women)
node_edge_betweenness(ison_adolescents)
node_fast_greedy(ison_adolescents)
node_leading_eigen(ison_adolescents)
node_walktrap(ison_adolescents)
node_infomap(ison_adolescents)
node_spinglass(ison_adolescents)
node_fluid(ison_adolescents)
node_louvain(ison_adolescents)
node_leiden(ison_adolescents)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.