EVOLUTION-MANAGER
Edit File: cluster_spinglass.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: Finding communities in graphs based on statistical meachanics</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_spinglass {igraph}"><tr><td>cluster_spinglass {igraph}</td><td style="text-align: right;">R Documentation</td></tr></table> <h2>Finding communities in graphs based on statistical meachanics</h2> <h3>Description</h3> <p>This function tries to find communities in graphs via a spin-glass model and simulated annealing. </p> <h3>Usage</h3> <pre> cluster_spinglass( graph, weights = NULL, vertex = NULL, spins = 25, parupdate = FALSE, start.temp = 1, stop.temp = 0.01, cool.fact = 0.99, update.rule = c("config", "random", "simple"), gamma = 1, implementation = c("orig", "neg"), gamma.minus = 1 ) </pre> <h3>Arguments</h3> <table summary="R argblock"> <tr valign="top"><td><code>graph</code></td> <td> <p>The input graph, can be directed but the direction of the edges is neglected.</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> <tr valign="top"><td><code>vertex</code></td> <td> <p>This parameter can be used to calculate the community of a given vertex without calculating all communities. Note that if this argument is present then some other arguments are ignored.</p> </td></tr> <tr valign="top"><td><code>spins</code></td> <td> <p>Integer constant, the number of spins to use. This is the upper limit for the number of communities. It is not a problem to supply a (reasonably) big number here, in which case some spin states will be unpopulated.</p> </td></tr> <tr valign="top"><td><code>parupdate</code></td> <td> <p>Logical constant, whether to update the spins of the vertices in parallel (synchronously) or not. This argument is ignored if the second form of the function is used (ie. the ‘<code>vertex</code>’ argument is present). It is also not implemented in the “neg” implementation.</p> </td></tr> <tr valign="top"><td><code>start.temp</code></td> <td> <p>Real constant, the start temperature. This argument is ignored if the second form of the function is used (ie. the ‘<code>vertex</code>’ argument is present).</p> </td></tr> <tr valign="top"><td><code>stop.temp</code></td> <td> <p>Real constant, the stop temperature. The simulation terminates if the temperature lowers below this level. This argument is ignored if the second form of the function is used (ie. the ‘<code>vertex</code>’ argument is present).</p> </td></tr> <tr valign="top"><td><code>cool.fact</code></td> <td> <p>Cooling factor for the simulated annealing. This argument is ignored if the second form of the function is used (ie. the ‘<code>vertex</code>’ argument is present).</p> </td></tr> <tr valign="top"><td><code>update.rule</code></td> <td> <p>Character constant giving the ‘null-model’ of the simulation. Possible values: “simple” and “config”. “simple” uses a random graph with the same number of edges as the baseline probability and “config” uses a random graph with the same vertex degrees as the input graph.</p> </td></tr> <tr valign="top"><td><code>gamma</code></td> <td> <p>Real constant, the gamma argument of the algorithm. This specifies the balance between the importance of present and non-present edges in a community. Roughly, a comunity is a set of vertices having many edges inside the community and few edges outside the community. The default 1.0 value makes existing and non-existing links equally important. Smaller values make the existing links, greater values the missing links more important.</p> </td></tr> <tr valign="top"><td><code>implementation</code></td> <td> <p>Character scalar. Currently igraph contains two implementations for the Spin-glass community finding algorithm. The faster original implementation is the default. The other implementation, that takes into account negative weights, can be chosen by supplying ‘neg’ here.</p> </td></tr> <tr valign="top"><td><code>gamma.minus</code></td> <td> <p>Real constant, the gamma.minus parameter of the algorithm. This specifies the balance between the importance of present and non-present negative weighted edges in a community. Smaller values of gamma.minus, leads to communities with lesser negative intra-connectivity. If this argument is set to zero, the algorithm reduces to a graph coloring algorithm, using the number of spins as the number of colors. This argument is ignored if the ‘orig’ implementation is chosen.</p> </td></tr> </table> <h3>Details</h3> <p>This function tries to find communities in a graph. A community is a set of nodes with many edges inside the community and few edges between outside it (i.e. between the community itself and the rest of the graph.) </p> <p>This idea is reversed for edges having a negative weight, ie. few negative edges inside a community and many negative edges between communities. Note that only the ‘neg’ implementation supports negative edge weights. </p> <p>The <code>spinglass.cummunity</code> function can solve two problems related to community detection. If the <code>vertex</code> argument is not given (or it is <code>NULL</code>), then the regular community detection problem is solved (approximately), i.e. partitioning the vertices into communities, by optimizing the an energy function. </p> <p>If the <code>vertex</code> argument is given and it is not <code>NULL</code>, then it must be a vertex id, and the same energy function is used to find the community of the the given vertex. See also the examples below. </p> <h3>Value</h3> <p>If the <code>vertex</code> argument is not given, ie. the first form is used then a <code><a href="cluster_spinglass.html">cluster_spinglass</a></code> returns a <code><a href="communities.html">communities</a></code> object. </p> <p>If the <code>vertex</code> argument is present, ie. the second form is used then a named list is returned with the following components: </p> <table summary="R valueblock"> <tr valign="top"><td><code>community</code></td> <td> <p>Numeric vector giving the ids of the vertices in the same community as <code>vertex</code>.</p> </td></tr> <tr valign="top"><td><code>cohesion</code></td> <td> <p>The cohesion score of the result, see references.</p> </td></tr> <tr valign="top"><td><code>adhesion</code></td> <td> <p>The adhesion score of the result, see references.</p> </td></tr> <tr valign="top"><td><code>inner.links</code></td> <td> <p>The number of edges within the community of <code>vertex</code>.</p> </td></tr> <tr valign="top"><td><code>outer.links</code></td> <td> <p>The number of edges between the community of <code>vertex</code> and the rest of the graph. </p> </td></tr> </table> <h3>Author(s)</h3> <p>Jorg Reichardt for the original code and Gabor Csardi <a href="mailto:csardi.gabor@gmail.com">csardi.gabor@gmail.com</a> for the igraph glue code. </p> <p>Changes to the original function for including the possibility of negative ties were implemented by Vincent Traag (<a href="http://www.traag.net/">http://www.traag.net/</a>). </p> <h3>References</h3> <p>J. Reichardt and S. Bornholdt: Statistical Mechanics of Community Detection, <em>Phys. Rev. E</em>, 74, 016110 (2006), <a href="https://arxiv.org/abs/cond-mat/0603718">https://arxiv.org/abs/cond-mat/0603718</a> </p> <p>M. E. J. Newman and M. Girvan: Finding and evaluating community structure in networks, <em>Phys. Rev. E</em> 69, 026113 (2004) </p> <p>V.A. Traag and Jeroen Bruggeman: Community detection in networks with positive and negative links, <a href="https://arxiv.org/abs/0811.2329">https://arxiv.org/abs/0811.2329</a> (2008). </p> <h3>See Also</h3> <p><code><a href="communities.html">communities</a></code>, <code><a href="components.html">components</a></code> </p> <h3>Examples</h3> <pre> g <- sample_gnp(10, 5/10) %du% sample_gnp(9, 5/9) g <- add_edges(g, c(1, 12)) g <- induced_subgraph(g, subcomponent(g, 1)) cluster_spinglass(g, spins=2) cluster_spinglass(g, vertex=1) </pre> <hr /><div style="text-align: center;">[Package <em>igraph</em> version 1.3.5 <a href="00Index.html">Index</a>]</div> </body></html>