modularity

0th

Percentile

Modularity of a community structure of a graph

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

Keywords
graphs
Usage
modularity(graph, membership)
Arguments
graph
The input graph.
membership
Numeric vector, for each vertex it gives its community. The communities are numbered from zero.
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}{2m} \sum_{i,j} A_{ij}-\frac{k_ik_j}{2m}\delta(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.

Value

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

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.

Aliases
  • modularity
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)
Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)

Community examples

Looks like there are no examples yet.