Use this if you are using igraph from R
A function to compute the L and R semi-projectors for a given partition of the vertices.
scg_semi_proj(groups, mtype = c("symmetric", "laplacian", "stochastic"), p = NULL, norm = c("row", "col"), sparse = igraph_opt("sparsematrices"))
groups |
A vector of |
mtype |
The type of semi-projectors. For now “symmetric”, “laplacian” and “stochastic” are available. |
p |
A probability vector of length |
norm |
Either “row” or “col”. If set to “row” the rows of the Laplacian matrix sum up to zero and the rows of the stochastic sum up to one; otherwise it is the columns. |
sparse |
Logical scalar, whether to return sparse matrices. |
The three types of semi-projectors are defined as follows. Let gamma(j) label the group of vertex j in a partition of all the vertices.
The symmetric semi-projectors are defined as
delta[alpha,gamma(j)],
R[alpha,j] = 1/sqrt(|alpha|) delta[alpha,gamma(j)],
the (row) Laplacian semi-projectors as
1/|alpha| delta[alpha,gamma(j)] and R[alpha,j] = delta[alpha,gamma(j)],
and R[alpha,j] = delta[alpha,gamma(j)],
and the (row) stochastic semi-projectors as
p[1][j] / sum(p[1][k]; k in gamma(j)) delta[alpha,gamma(j)] and R[alpha,j] = delta[alpha,gamma(j)],
/ sum(p[1][k]; k in gamma(j)) delta[alpha,gamma(j)] and R[alpha,j] = delta[alpha,gamma(j)],
where p[1] is the (left) eigenvector
associated with the one-eigenvalue of the stochastic matrix. L and
R are defined in a symmetric way when norm = col
. All these
semi-projectors verify various properties described in the reference.
L |
The semi-projector L. |
R |
The semi-projector R. |
David Morton de Lachapelle, http://people.epfl.ch/david.morton.
D. Morton de Lachapelle, D. Gfeller, and P. De Los Rios, Shrinking Matrices while Preserving their Eigenpairs with Application to the Spectral Coarse Graining of Graphs. Submitted to SIAM Journal on Matrix Analysis and Applications, 2008. http://people.epfl.ch/david.morton
scg-method for a detailed introduction. scg
,
scg_eps
, scg_group
library(Matrix) # compute the semi-projectors and projector for the partition # provided by a community detection method g <- sample_pa(20, m = 1.5, directed = FALSE) eb <- cluster_edge_betweenness(g) memb <- membership(eb) lr <- scg_semi_proj(memb) #In the symmetric case L = R tcrossprod(lr$R) # same as lr$R %*% t(lr$R) P <- crossprod(lr$R) # same as t(lr$R) %*% lr$R #P is an orthogonal projector isSymmetric(P) sum( (P %*% P-P)^2 ) ## use L and R to coarse-grain the graph Laplacian lr <- scg_semi_proj(memb, mtype="laplacian") L <- laplacian_matrix(g) Lt <- lr$L %*% L %*% t(lr$R) ## or better lr$L %*% tcrossprod(L,lr$R) rowSums(Lt)