EVOLUTION-MANAGER
Edit File: cluster_optimal.html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>R: Optimal community structure</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <link rel="stylesheet" type="text/css" href="R.css" /> </head><body> <table width="100%" summary="page for cluster_optimal {igraph}"><tr><td>cluster_optimal {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Optimal community structure</h2> <h3>Description</h3> <p>This function calculates the optimal community structure of a graph, by maximizing the modularity measure over all possible partitions. </p> <h3>Usage</h3> <pre> cluster_optimal(graph, weights = NULL) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph. Edge directions are ignored for directed graphs.</p> </td></tr> <tr valign="top"><td><code>weights</code></td> <td> <p>The weights of the edges. It must be a positive numeric vector, <code>NULL</code> or <code>NA</code>. If it is <code>NULL</code> and the input graph has a ‘weight’ edge attribute, then that attribute will be used. If <code>NULL</code> and no such attribute is present, then the edges will have equal weights. Set this to <code>NA</code> if the graph was a ‘weight’ edge attribute, but you don't want to use it for community detection. A larger edge weight means a stronger connection for this function.</p> </td></tr> </table> <h3>Details</h3> <p>This function calculates the optimal community structure for a graph, in terms of maximal modularity score. </p> <p>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. </p> <p>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. </p> <h3>Value</h3> <p><code>cluster_optimal</code> returns a <code><a href="communities.html">communities</a></code> object, please see the <code><a href="communities.html">communities</a></code> manual page for details. </p> <h3>Examples</h3> <pre> ## Zachary's karate club g <- make_graph("Zachary") ## We put everything into a big 'try' block, in case ## igraph was compiled without GLPK support ## 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)) </pre> <h3>Author(s)</h3> <p>Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> </p> <h3>References</h3> <p>Ulrik Brandes, Daniel Delling, Marco Gaertler, Robert Gorke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner: On Modularity Clustering, <em>IEEE Transactions on Knowledge and Data Engineering</em> 20(2):172-188, 2008. </p> <h3>See Also</h3> <p><code><a href="communities.html">communities</a></code> for the documentation of the result, <code><a href="modularity.igraph.html">modularity</a></code>. See also <code><a href="cluster_fast_greedy.html">cluster_fast_greedy</a></code> for a fast greedy optimizer. </p> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>