modularity: 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 class 'igraph':
modularity(x, membership, weights = NULL, \dots)

Arguments

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

A numeric scalar, the modularity score of the given configuration.

concept

Modularity

Details

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_{ij}$ 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 $\delta(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$.

References

MEJ Newman and M Girvan: Finding and evaluating community structure in networks. Physical Review E 69 026113, 2004.

Examples

Run this code

g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(1,6, 1,11, 6, 11))
wtc <- walktrap.community(g)
modularity(wtc)
modularity(g, membership(wtc))

Run the code above in your browser using DataLab

Get 50% off unlimited learning