leading.eigenvector.community {igraph}R Documentation

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

Description

These functions try to find densely connected subgraphs in a graph by calculating the leading non-negative eigenvector of the modularity matrix of the graph.

Usage

leading.eigenvector.community(graph, steps = -1,
       options = igraph.arpack.default)
leading.eigenvector.community.naive(graph, steps = -1,
       options = igraph.arpack.default)
leading.eigenvector.community.step (graph, fromhere = NULL,
    membership = rep(0, vcount(graph)), community = 0,
    options=igraph.arpack.default)
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 vector.

naive

Logical constant, it defines how the algorithm tries to find more divisions after the first division was made. If TRUE then it simply considers both communities as separate graphs and then creates modularity matrices for both communities, etc. This method however does not maximize modularity, see the paper in the references section below. If it is FALSE then the proper method is used which maximizes modularity.

fromhere

An object returned by a previous call to leading.eigenvector.community.step. This will serve as a starting point to take another step. This argument is ignored if it is NULL.

membership

The starting community structure. It is a numeric vector defining the membership of every vertex in the graph with a number between 0 and the total number of communities at this level minus one. By default we start with a single community containing all vertices. This argument is ignored if fromhere is not NULL.

For community.le.to.memberhip the starting community structure on which steps merges are performed.

community

The id of the community which the algorithm will try to split.

options

A named list to override some ARPACK options.

merges

The merge matrix, possible from the result of leading.eigenvector.community.

Details

The functions documented in these section implement the ‘leading eigenvector’ method developed by Mark Newman and published in MEJ Newman: Finding community structure using the eigenvectors of matrices, arXiv:physics/0605087. TODO: proper citation.

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.

leading.eigenvector.community is the proper implementation of the proposed algorithm. leading.eigenvector.community.naive is considered worse, in this implementation a community found after a division is considered as a separate graph for further divisions. leading.eigenvector.community.step is the proper implementation, but makes only one step, by trying to split the specified community.

From igraph 0.5 these functions use ARPACK to calculate the eigenvectors. See arpack for details.

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

Value

leading.eigenvector.community and leading.eigenvector.community.naive return a named list with the following members:

membership

The membership vector at the end of the algorithm, when no more splits are possible.

merges

The 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.

options

Information about the underlying ARPACK computation, see arpack for details.

leading.eigenvector.community.step returns a named list with the following members:

membership

The new membership vector after the split. If no split was done then this is the same as the input membership vector.

split

Logical scalar, if TRUE that means that the community was successfully splitted.

eigenvector

The eigenvector of the community matrix, or NULL if the eigenvector argument was FALSE.

eigenvalue

The largest positive eigenvalue of the modularity matrix.

options

Information about the underlying ARPACK computation, see arpack for details.

community.le.to.membership returns a named list with two components:

membership

A membership vector, a numerical vector indication which vertex belongs to which community. The communities are always numbered from zero.

csize

A numeric vector giving the sizes of the communities.

Author(s)

Gabor Csardi csardi@rmki.kfki.hu

References

MEJ Newman: Finding community structure using the eigenvectors of matrices, arXiv:physics/0605087

See Also

modularity, walktrap.community, edge.betweenness.community, fastgreedy.community, as.dendrogram in package stats.

Examples

g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(0,5, 0,10, 5, 10))
leading.eigenvector.community(g)

lec <- leading.eigenvector.community.step(g)
lec$membership
# Try one more split
leading.eigenvector.community.step(g, fromhere=lec, community=0)
leading.eigenvector.community.step(g, fromhere=lec, community=1)

[Package igraph version 0.5.5-4 Index]