scg_semi_proj

0th

Percentile

Semi-Projectors

A function to compute the \(L\) and \(R\) semi-projectors for a given partition of the vertices.

Usage
scg_semi_proj(groups, mtype = c("symmetric", "laplacian", "stochastic"),
  p = NULL, norm = c("row", "col"), sparse = igraph_opt("sparsematrices"))
Arguments
groups

A vector of nrow(X) or vcount(X) integers giving the group label of every vertex in the partition.

mtype

The type of semi-projectors. For now “symmetric”, “laplacian” and “stochastic” are available.

p

A probability vector of length length(gr). p is the stationary probability distribution of a Markov chain when mtype = “stochastic”. This parameter is ignored in all other cases.

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.

Details

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 $$L_{\alpha j}=R_{\alpha j}= $$$$ \frac{1}{\sqrt{|\alpha|}}\delta_{\alpha\gamma(j)},$$ the (row) Laplacian semi-projectors as $$L_{\alpha j}=\frac{1}{|\alpha|}\delta_{\alpha\gamma(j)}\,\,\,\, $$$$ \textrm{and}\,\,\,\, R_{\alpha j}=\delta_{\alpha\gamma(j)},$$ and the (row) stochastic semi-projectors as $$L_{\alpha j}=\frac{p_{1}(j)}{\sum_{k\in\gamma(j)}p_{1}(k)}\,\,\,\, $$$$ \textrm{and}\,\,\,\, R_{\alpha j}=\delta_{\alpha\gamma(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.

Value

L

The semi-projector \(L\).

R

The semi-projector \(R\).

References

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

See Also

scg-method for a detailed introduction. scg, scg_eps, scg_group

Aliases
  • scg_semi_proj
  • scgSemiProjectors
Examples
# NOT RUN {
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)

# }
Documentation reproduced from package igraph, version 1.2.2, License: GPL (>= 2)

Community examples

Looks like there are no examples yet.