modularity {igraph}R Documentation

Modularity of a community structure of a graph

Description

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

Usage

modularity(graph, membership, weights = NULL)

Arguments

graph The input graph.
membership Numeric vector, for each vertex it gives its community. The communities are numbered from zero.
weights If not NULL then a numeric vector giving edge weights.

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=1/(2m) * sum(Aij-ki*kj/(2m)delta(ci,cj),i,j),

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 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 ki is the sum of weights of adjacent edges for vertex i.

Value

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

Author(s)

Gabor Csardi csardi@rmki.kfki.hu

References

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

See Also

walktrap.community, edge.betweenness.community, fastgreedy.community, spinglass.community for various community detection methods.

Examples

g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(0,5, 0,10, 5, 10))
wtc <- walktrap.community(g)
memb <- community.to.membership(g, wtc$merges, steps=12)
modularity(g, memb$membership)

[Package igraph version 0.5.2 Index]