This function calculates how modular is a given division of a graph into subgraphs.
Usage
# S3 method for igraph
modularity(x, membership, weights = NULL, resolution = 1, directed = TRUE, ...)
modularity_matrix(
graph,
membership,
weights = NULL,
resolution = 1,
directed = TRUE
)
Arguments
- x, graph
The input graph.
- membership
Numeric vector, one value for each vertex, the membership vector of the community structure.
- weights
If not
NULL
then a numeric vector giving edge weights.- resolution
The resolution parameter. Must be greater than or equal to 0. Set it to 1 to use the classical definition of modularity.
- directed
Whether to use the directed or undirected version of modularity. Ignored for undirected graphs.
- ...
Additional arguments, none currently.
Value
For modularity()
a numeric scalar, the modularity score of the
given configuration.
For modularity_matrix()
a numeric square matrix, its order is the number of
vertices in the graph.
Details
modularity()
calculates the modularity of a graph with respect to the
given membership
vector.
The modularity of a graph with respect to some division (or vertex types) measures how good the division is, or how separated are the different vertex types from each other. It defined as Q=12m∑i,j(Aij−γkikj2m)δ(ci,cj), here m is the number of edges, Aij is the element of the A adjacency matrix in row i and column j, ki is the degree of i, kj is the degree of j, ci is the type (or component) of i, cj that of j, the sum goes over all i and j pairs of vertices, and δ(x,y) is 1 if x=y and 0 otherwise. For directed graphs, it is defined as Q=1m∑i,j(Aij−γkoutikinjm)δ(ci,cj).
The resolution parameter γ allows weighting the random null model, which might be useful when finding partitions with a high modularity. Maximizing modularity with higher values of the resolution parameter typically results in more, smaller clusters when finding partitions with a high modularity. Lower values typically results in fewer, larger clusters. The original definition of modularity is retrieved when setting γ to 1.
If edge weights are given, then these are considered as the element of the A adjacency matrix, and ki is the sum of weights of adjacent edges for vertex i.
modularity_matrix()
calculates the modularity matrix. This is a dense matrix,
and it is defined as the difference of the adjacency matrix and the
configuration model null model matrix. In other words element
Mij is given as Aij−didj/(2m), where Aij is the (possibly
weighted) adjacency matrix, di is the degree of vertex i,
and m is the number of edges (or the total weights in the graph, if it
is weighed).
References
Clauset, A.; Newman, M. E. J. & Moore, C. Finding community structure in very large networks, Physical Review E 2004, 70, 066111
See also
cluster_walktrap()
,
cluster_edge_betweenness()
,
cluster_fast_greedy()
, cluster_spinglass()
,
cluster_louvain()
and cluster_leiden()
for
various community detection methods.
Community detection
as_membership()
,
cluster_edge_betweenness()
,
cluster_fast_greedy()
,
cluster_fluid_communities()
,
cluster_infomap()
,
cluster_label_prop()
,
cluster_leading_eigen()
,
cluster_leiden()
,
cluster_louvain()
,
cluster_optimal()
,
cluster_spinglass()
,
cluster_walktrap()
,
compare()
,
groups()
,
make_clusters()
,
plot_dendrogram()
,
split_join_distance()
Author
Gabor Csardi csardi.gabor@gmail.com
Examples
g <- make_full_graph(5) %du% make_full_graph(5) %du% make_full_graph(5)
g <- add_edges(g, c(1, 6, 1, 11, 6, 11))
wtc <- cluster_walktrap(g)
modularity(wtc)
#> [1] 0.5757576
modularity(g, membership(wtc))
#> [1] 0.5757576