modularity.igraph: Modularity of a community structure of a graph

Description

This function calculates how modular is a given division of a graph into subgraphs.

Usage

# S3 method for igraph
modularity(x, membership, weights = NULL, ...)
modularity_matrix(graph, membership, weights = NULL)

Arguments

x, graph

The input graph.

membership

Numeric vector, for each vertex it gives its community. The communities are numbered from one.

weights

If not NULL then a numeric vector giving edge weights.

…

Additional arguments, none currently.

Value

For modularity a numeric scalar, the modularity score of the given configuration.

For modularity_matrix a numeic 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 = \frac{1}{2 m} \sum_{i, j} (A_{i j} - \frac{k_{i} k_{j}}{2 m}) δ (c_{i}, c_{j}),$ here $m$ is the number of edges, $A_{i j}$ is the element of the $A$ adjacency matrix in row $i$ and column $j$ , $k_{i}$ is the degree of $i$ , $k_{j}$ is the degree of $j$ , $c_{i}$ is the type (or component) of $i$ , $c_{j}$ 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.

If edge weights are given, then these are considered as the element of the $A$ adjacency matrix, and $k_{i}$ 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 $M_{i j}$ is given as $A_{i j} - d_{i} d_{j} / (2 m)$ , where $A_{i j}$ is the (possibly weighted) adjacency matrix, $d_{i}$ 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, Phyisical Review E 2004, 70, 066111

Examples

Run this code

# NOT RUN {
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)
modularity(g, membership(wtc))

# }

Run the code above in your browser using DataLab

Last chance! 50% off unlimited learning