leading.eigenvector.community

0th

Percentile

Community structure detecting based on the leading eigenvector of the community matrix

This function tries to find densely connected subgraphs in a graph by calculating the leading non-negative eigenvector of the modularity matrix of the graph.

Keywords
graphs
Usage
leading.eigenvector.community(graph, steps = -1, start = NULL,
       options = igraph.arpack.default, callback = NULL, extra = NULL,
       env = parent.frame())
community.le.to.membership(merges, steps, membership)
Arguments
graph
The input graph. Should be undirected as the method needs a symmetric matrix.
steps
The number of steps to take, this is actually the number of tries to make a step. It is not a particularly useful parameter.

For community.le.to.membership the number of merges to produce from the supplied membership

start
NULL, or a numeric membership vector, giving the start configuration of the algorithm.
membership
The starting community structure on which steps merges are performed.
options
A named list to override some ARPACK options.
callback
If not NULL, then it must be callback function. This is called after each iteration, after calculating the leading eigenvector of the modularity matrix. See details below.
extra
Additional argument to supply to the callback function.
env
The environment in which the callback function is evaluated.
merges
The merge matrix, possible from the result of leading.eigenvector.community.
Details

The function documented in these section implements the leading eigenvector method developed by Mark Newman, see the reference below. The heart of the method is the definition of the modularity matrix, B, which is B=A-P, A being the adjacency matrix of the (undirected) network, and P contains the probability that certain edges are present according to the configuration model. In other words, a P[i,j] element of P is the probability that there is an edge between vertices i and j in a random network in which the degrees of all vertices are the same as in the input graph. The leading eigenvector method works by calculating the eigenvector of the modularity matrix for the largest positive eigenvalue and then separating vertices into two community based on the sign of the corresponding element in the eigenvector. If all elements in the eigenvector are of the same sign that means that the network has no underlying comuunity structure. Check Newman's paper to understand why this is a good method for detecting community structure.

community.le.to.memberhip creates a membership vector from the result of leading.eigenvector.community. It takes membership and permformes steps merges, according to the supplied merges matrix.

Value

  • leading.eigenvector.community returns a named list with the following members:
  • membershipThe membership vector at the end of the algorithm, when no more splits are possible.
  • mergesThe merges matrix starting from the state described by the membership member. This is a two-column matrix and each line describes a merge of two communities, the first line is the first merge and it creates community N, N is the number of initial communities in the graph, the second line creates community N+1, etc.
  • optionsInformation about the underlying ARPACK computation, see arpack for details.
  • community.le.to.membership returns a named list with two components:
  • membershipA membership vector, a numerical vector indication which vertex belongs to which community. The communities are always numbered from one.
  • csizeA numeric vector giving the sizes of the communities.

concept

Community structure

References

MEJ Newman: Finding community structure using the eigenvectors of matrices, Physical Review E 74 036104, 2006.

See Also

modularity, walktrap.community, edge.betweenness.community, fastgreedy.community, as.dendrogram

Aliases
  • leading.eigenvector.community
  • community.le.to.membership
Examples
g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(1,6, 1,11, 6, 11))
lec <- leading.eigenvector.community(g)
lec

leading.eigenvector.community(g, start=membership(lec))
Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.