| leading.eigenvector.community {igraph} | R Documentation |
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.
leading.eigenvector.community(graph, steps = -1, weights = NULL,
start = NULL, options = igraph.arpack.default,
callback = NULL, extra = NULL, env = parent.frame())
community.le.to.membership(merges, steps, membership)
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 |
weights |
An optional weight vector. The ‘weight’ edge
attribute is used if present. Supply ‘ |
start |
|
membership |
The starting community
structure on which |
options |
A named list to override some ARPACK options. |
callback |
If not |
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
|
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.
leading.eigenvector.community returns 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 |
options |
Information about the underlying ARPACK computation,
see |
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 one. |
csize |
A numeric vector giving the sizes of the communities. |
The callback argument can be used to supply a function that is
called after each eigenvector calculation. The following arguments are
supplied to this function:
The actual membership vector, with zero-based indexing.
The community that the algorithm just tried to split, community numbering starts with zero here.
The eigenvalue belonging to the leading eigenvector the algorithm just found.
The leading eigenvector the algorithm just found.
An R function that can be used to multiple the actual modularity matrix with an arbitrary vector. Supply the vector as an argument to perform this multiplication. This function can be used with ARPACK.
The extra argument that was passed to
leading.eigenvector.community.
Gabor Csardi csardi.gabor@gmail.com
MEJ Newman: Finding community structure using the eigenvectors of matrices, Physical Review E 74 036104, 2006.
modularity, walktrap.community,
edge.betweenness.community,
fastgreedy.community,
as.dendrogram
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))