cluster_optimal

0th

Percentile

Optimal community structure

This function calculates the optimal community structure of a graph, by maximizing the modularity measure over all possible partitions.

Keywords
graphs
Usage
cluster_optimal(graph, weights = NULL)
Arguments
graph
The input graph. Edge directions are ignored for directed graphs.
weights
Optional positive weight vector for optimizing weighted modularity. If the graph has a weight edge attribute, then this is used by default. Supply NA to ignore the weights of a weighted graph.
Details

This function calculates the optimal community structure for a graph, in terms of maximal modularity score.

The calculation is done by transforming the modularity maximization into an integer programming problem, and then calling the GLPK library to solve that. Please the reference below for details.

Note that modularity optimization is an NP-complete problem, and all known algorithms for it have exponential time complexity. This means that you probably don't want to run this function on larger graphs. Graphs with up to fifty vertices should be fine, graphs with a couple of hundred vertices might be possible.

Value

References

Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering, IEEE Transactions on Knowledge and Data Engineering 20(2):172-188, 2008.

See Also

communities for the documentation of the result, modularity. See also cluster_fast_greedy for a fast greedy optimizer.

Aliases
  • cluster_optimal
  • optimal.community
Examples
## Zachary's karate club
g <- make_graph("Zachary")

## We put everything into a big 'try' block, in case
## igraph was compiled without GLPK support

try({
  ## The calculation only takes a couple of seconds
  oc <- cluster_optimal(g)

  ## Double check the result
  print(modularity(oc))
  print(modularity(g, membership(oc)))

  ## Compare to the greedy optimizer
  fc <- cluster_fast_greedy(g)
  print(modularity(fc))
}, silent=TRUE)
Documentation reproduced from package igraph, version 1.0.0, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.