Construct and use the Normalized Laplacian — NormalizedLaplacian • invertiforms

A convenience function to create NormalizedLaplacian S4 objects, which are useful for finding the normalized Laplacian of the adjacency matrix of a graph.

Usage

NormalizedLaplacian(A)

# S4 method for NormalizedLaplacian,sparseMatrix
transform(iform, A)

# S4 method for NormalizedLaplacian,sparseMatrix
inverse_transform(iform, A)

Arguments

A: A matrix to transform.
iform: An Invertiform object describing the transformation.

Value

NormalizedLaplacian() creates a NormalizedLaplacian object.
transform() returns the transformed matrix, typically as a Matrix.
inverse_transform() returns the inverse transformed matrix, typically as a Matrix.

Details

We define the normalized Laplacian $L(A)$ of an $n \times n$ graph adjacency matrix $A$ as

$L(A)_{ij} = \frac{A_{ij}}{\sqrt{d^{out}_i} \sqrt{d^{in}_j}}$

where

$d^{out}_i = \sum_{j=1}^n \| A_{ij} \|$

and

$d^{in}_j = \sum_{i=1}^n \| A_{ij} \|.$

When $A_{ij}$ denotes the present of an edge from node $i$ to node $j$ , which is fairly standard notation, $d^{out}_i$ denotes the (absolute) out-degree of node $i$ and $d^{in}_j$ denotes the (absolute) in-degree of node $j$ .

Note that this documentation renders most clearly at https://rohelab.github.io/invertiforms/.

Examples


library(igraph)
library(igraphdata)

data("karate", package = "igraphdata")

A <- get.adjacency(karate)

iform <- NormalizedLaplacian(A)

L <- transform(iform, A)
A_recovered <- inverse_transform(iform, L)

all.equal(A, A_recovered)
#> [1] TRUE