spinglass.community {igraph}R Documentation

Finding communities in graphs based on statistical meachanics

Description

This function tries to find communities in graphs via a spin-glass model and simulated annealing.

Usage

spinglass.community(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)

Usage

spinglass.community(graph, weights=NULL, spins=25, parupdate=FALSE,
                    start.temp=1, stop.temp=0.1, cool.fact=0.99,
                    update.rule=c("config", "random", "simple"), gamma=1)
spinglass.community(graph, weights=NULL, vertex, spins=25,
                    update.rule=c("config", "random", "simple"), gamma=1)

Arguments

graph

The input graph, can be directed but the direction of the edges is neglected.

weights

The weights of the edges. Either a numeric vector or NULL. If it is null and the input graph has a ‘weight’ edge attribute then that will be used. If NULL and no such attribute is present then the edges will have equal weights.

spins

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.

parupdate

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 ‘vertex’ argument is present).

start.temp

Real constant, the start temperature. This argument is ignored if the second form of the function is used (ie. the ‘vertex’ argument is present).

stop.temp

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 ‘vertex’ argument is present).

cool.fact

Cooling factor for the simulated annealing. This argument is ignored if the second form of the function is used (ie. the ‘vertex’ argument is present).

update.rule

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.

gamma

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.

vertex

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.

Details

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 (ie. between the community itself and the rest of the graph.

Value

If the vertex argument is not given, ie. the first form is used then a named list is returned with the following slots:

membership

Integer vector giving the communities found. The communities have ids starting from zero and for each graph vertex ids community id is given in this vector.

csize

The sizes of the communities in the order of their ids.

modularity

The (generalized) modularity score of the result, as defined in the Reichardt-Bornholdt paper, see references. If gamma is one, then it simplifies to the Newman-Girvan modularity score.

temperature

The temperature of the system when the algorithm terminated.

If the vertex argument is present, ie. the second form is used then a named list is returned with the following components:

community

Numeric vector giving the ids of the vertices in the same community as vertex.

cohesion

The cohesion score of the result, see references.

adhesion

The adhesion score of the result, see references.

inner.links

The number of edges within the community of vertex.

outer.links

The number of edges between the community of vertex and the rest of the graph.

Author(s)

Jorg Reichardt lastname@physik.uni-wuerzburg.de for the original code and Gabor Csardi csardi@rmki.kfki.hu for the igraph glue code

References

J. Reichardt and S. Bornholdt: Statistical Mechanics of Community Detection, Phys. Rev. E, 74, 016110 (2006), http://arxiv.org/abs/cond-mat/0603718

M. E. J. Newman and M. Girvan: Finding and evaluating community structure in networks, Phys. Rev. E 69, 026113 (2004)

See Also

clusters

Examples

  g <- erdos.renyi.game(10, 5/10) %du% erdos.renyi.game(9, 5/9)
  g <- add.edges(g, c(0, 11))
  g <- subgraph(g, subcomponent(g, 0))
  spinglass.community(g, spins=2)
  spinglass.community(g, vertex=0)

[Package igraph version 0.5.5-4 Index]