Questions tagged [graph-laplacian]

A simple graph has a symmetric matrix L = D - A associated with it called the Laplacian matrix, where D is the diagonal matrix of degrees and A is the adjacency matrix, often studied for its spectrum (eigenvalues).

Filter by
Sorted by
Tagged with
0 votes
1 answer
20 views

Missing eigenvectors of the ring graph Laplacian

Spielman has some notes where he explains that the eigenvectors of the Laplacian of the ring graph are $$ x_k(u) = \sin(\frac{2\pi ku}{n})\\y_k(u) = \cos(\frac{2\pi ku}{n}) $$ for $1 \leq k \leq n/2$ ...
user avatar
0 votes
0 answers
6 views

Laplacian integral graphs and graph Join

There is one famous theorem that states the following: Let $G$ be a connected graph of order $n$. Then $n$ is a Laplacian eigenvalue of $G$ if and only if $G$ is the join of two graphs. In connection ...
user avatar
0 votes
0 answers
12 views

Absorption probabilities of standard random walk on a graph using Laplacian system solves

Suppose we have a weighted undirected graph $G = (V, E)$. Consider the standard random walk $X_n$ on this graph where the transition probabilities are given by $P[X_1 = v \mid X_0 = u] = \frac{w_{uv}}{...
user avatar
0 votes
0 answers
25 views

Why Laplacian algebra instead of Adjacency algebra?

I'm reading the paper `New bounds for the max-$k$-cut and chromatic number of a graph' by E.R. van Dam and R. Sotirov. In this paper, the authors attempt to find a new bound for the max-$k$-cut ...
user avatar
1 vote
1 answer
21 views

Determining the Laplacian for a signed graph

I was reading the paper: On the Laplacian Eigenvalues of Signed Graphs, when I had this question. When we determine the Laplacian of a signed graph, why do we take the unsigned degree matrix D, but ...
user avatar
  • 907
0 votes
0 answers
16 views

Fiedler Vector for directed and not strongly connected graph

Anyone know if there is any work that deal with Fiedler vector graph partition, for the case of connected, directed, but not strongly connected graph? Thanks
user avatar
  • 1
0 votes
0 answers
15 views

Graph Laplacian for weight matrix with negative edges

How can I normalize my weight matrix to get a positive semi-definite Laplacian, if I am using a weight matrix with negative edges?
user avatar
0 votes
0 answers
29 views

Eigenvalues of graph laplacian question

I need some guidance on solving the following question I am stuck on: Let L be a graph Laplacian matrix of a graph G = (V, E) with n vertices. Denote the eigenpairs of L by {λi,ψi} for every i=1..n, ...
user avatar
  • 11
0 votes
0 answers
18 views

Why Spectral Embedding leads us to the low-dimensional embeddings?

Dimension Reduction is well versed technique in Machine Learning. We often use this tool. One such tool is Spectral Embedding. It follows three steps:- Constructing the Adjacency Graph Choosing the ...
user avatar
  • 333
-1 votes
3 answers
107 views

Non-negative diagonal perturbation of Laplacian matrix

In this previous question is stated that given a weighted undirected Laplacian corresponding to a connected graph $L$ it's well known that if you add a small positive (resp. negative) amount to any ...
user avatar
  • 387
1 vote
0 answers
38 views

How to recover the Adjacency Matrix from the Normalized Laplacian?

The normalized Laplacian of a graph is defined as $\mathcal{L}=D^{-1/2}(D-A)D^{-1/2}$, where $A$ and $D$ are the adjacency and degree matrices of the graph. If the graph is simple (no multiple edges ...
user avatar
  • 9
0 votes
0 answers
20 views

Different smallest eigenvector for different Grounded Laplacian

I've been struggling for a couple weeks trying to prove this statement. I don't know if the statement is true, but my simulations suggest that it is. Given two Laplacian matrices $L_{B_1} = L_1 + D_1$...
user avatar
  • 1
0 votes
0 answers
48 views

How to approximate a matrix using generalized Laplacian? (project a matrix into Laplacian)

Equivalently, how to project a matrix into the space of generalized Laplacian matrices. More formally, let $M_0 \in \mathbb{R}^{n\times n}$, find $$\text{argmin}_{M \in G}|| M - M_0||^2_F,$$ where $||\...
user avatar
  • 392
1 vote
2 answers
61 views

Most efficient to solve $(I + L)x = b$ where $L$ is graph Laplacian

Assume $G$ is a graph with $n$ vertices, and $L = D - W$ is its graph Laplacian matrix. I want to solve the linear equation $(I + L)x = b$, where $I$ is the identity matrix, $b$ is a constant vector, ...
user avatar
0 votes
0 answers
64 views

Relationship between square of adjacency matrix and Laplacian matrix

Consider a simple undirected graph with $n$ elements. Let $A$ be the adjacency matrix of the graph with elements $a_{ij}$. Let $L$ be the graph Laplacian with $L=D-A$ where $D$ is the degree matrix. ...
user avatar
  • 71
0 votes
1 answer
38 views

Sum of unstable diagonal matrix with laplacian

I am trying to solve the following problem that seems trivial at first sight but I don't know where to start for a rigorous approach. Consider the following matrix $M = A - L$ where $A$ is an unstable,...
user avatar
  • 387
0 votes
0 answers
40 views

Range $u_{\mathrm{max}}-u_{\mathrm{min}}$ of the solution to graph Poisson equation $Lu=b$

I found out an interesting phenomenon when trying to solve the linear equation $Lu=b$, and I don't know how to interpret such phenomenon. Goal: Fit $u(x, y)=\cos(x)$ for $x,y \in [0,\pi]$. We draw ...
user avatar
  • 23
0 votes
0 answers
34 views

On the SOS property of the graph Laplacian

I'm reading this paper, and I have a some questions about a property of the graph Laplacian matrix. Definitions Let $G\triangleq\langle V,E \rangle$ be a graph (without loops for simplicity), where $V\...
user avatar
3 votes
1 answer
159 views

Origins of the Graph Laplacian

I understand the definition and the properties of a graph Laplacian but is there any text around how it was derived and what steps led to its discovery? I ask this because it seems rather arbitrary ...
user avatar
0 votes
0 answers
64 views

Irreducible Laplacian matrix

Let $\mathcal{G}$ be a strongly connected weighted digraph with corresponding (weighted) adjacency matrix $\mathbf{A}\in\mathbb{R}^{n\times n}_{\geq0}$ and out-degree matrix $\mathbf{D}\in\mathbb{R}^{...
user avatar
0 votes
1 answer
97 views

Linear Algebra: if matrices $\mathbf{A} + \mathbf{B} = \mathbf{I}$, then do $\mathbf{A}$ and $\mathbf{B}$ have the same eigenvectors?

Just had a quick question which I think ought to be simple, but I can't fully convince myself of the result. Question: If matrices $\mathbf{A} + \mathbf{B} = \mathbf{I}$, ($\mathbf{I}$ is the identity ...
user avatar
0 votes
0 answers
22 views

if $B^3=C^3=BC=\mathbb I$ can we say anything about $L$ if $e^L=B+C?$

My intuition on matrix exponentials, hermitian matrices, unitary matrices, adjacency matrices, and Laplacian matrices is not superb now. For example, let $A$ be a matrix with $A^2=\mathbb I$. $A$ may ...
user avatar
  • 253
0 votes
0 answers
62 views

Row/Column Sum of a Laplacian Matrix

so I know that the row sum and the column sum for a laplacian matrix should always be 0. I am running a code on Matlab and after a certain time, one of the row sums comes out to be 0.0001. Is that ...
user avatar
2 votes
0 answers
43 views

Calculate the Laplacian of Kuramoto model

I am trying to calculate the Laplacian of the Kuramoto model which describes the phase dynamics of a set of $N$ phase oscillators $i$ with natural frequencies $\omega_i$ $$ \dot{\theta}_i = \omega_i + ...
user avatar
  • 31
0 votes
1 answer
51 views

Spectral radius of discrete Laplacian

We discretize the domain $\Omega = [0,1]^2$ with the step size $\Delta x = \frac{1}{n-1}$. Then, for the largest eigenvalue of the discrete Laplacian it holds $$\lambda_{\max}(-\Delta)\leq 8(n-1)^2.$$ ...
user avatar
  • 909
0 votes
0 answers
21 views

p-Laplacian eigenfunctions dimensionality reduction

Consider the standard Laplacian operator in a discrete setting, for example a graph. It is well known that once you compute a basis of eigenvectors, it is possible to reduce the dimension for solving ...
user avatar
0 votes
0 answers
21 views

Complex valued eigenvector for graph laplacian

I have to carry out a transformation of a vector using a orthogonal matrix obtained after EVD of the graph laplacian L = Degree matrix - Adjacency matrix. The ...
user avatar
  • 101
0 votes
0 answers
12 views

Are there requirements that hold for all kinds of graph Laplacian?

So I am aware of this question; Graph Laplacian, requirements but it doesn't help me for two reasons; It appears to be about the unnormalised laplacian $L=D-A$, I'm looking for properties that hold ...
user avatar
0 votes
0 answers
182 views

Null space squared Laplacian matrix

I have a matrix $G$ that is a row-normalized adjacency matrix of a connected graph. This means that all entries are $\geq 0$ and every row sums to one. The diagonal only contains zeros. From the ...
user avatar
  • 13
3 votes
1 answer
718 views

Significance of the random walk normalized graph Laplacian

I've been studying the graph Laplacian and random walks on graphs. The Wikipedia article on the Graph Laplacian defines the random walk normalized Laplacian in detail. But, unfortunately, it does not ...
user avatar
1 vote
1 answer
75 views

Connected components of infinite graph from adjacency matrix

For a finite graph, we can find the number of connected components of the graph as $\dim \ker L$, where $L = D - A$ is the Laplacian matrix. Does this still hold true for an infinite graph where every ...
user avatar
2 votes
1 answer
26 views

Relationship between the Path Graph, $P_v$ and the Cycle Graph, $C_{2v}$

In Daniel A. Spielman's book Spectral and Algebraic Graph Theory, (http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf) on page 54, he notes the following relationship between a Path and a Cycle ...
user avatar
  • 21
0 votes
0 answers
18 views

FPRAS for approximating eigenvalues of graph Laplacians

Is there a fully polynomial-time randomized approximation scheme (FPRAS) to approximate the eigenvalues (or even the largest one) of graph Laplacians? By FPRAS, I mean the algorithm runs in time $\...
user avatar
2 votes
2 answers
365 views

Largest laplacian eigenvalue lower bound

I'm currently dealing with a problem that I'm unsure how to start. Let G be a graph with largest Laplacian eigenvalue $\lambda_1$ and maximum degree $\Delta > 0$. Show that $\lambda_1 \geq \Delta + ...
user avatar
  • 133
1 vote
0 answers
40 views

Graph version of the PDE : $- \Delta u + \lambda u = 0$

Consider the (formal) continuous laplacian problem $- \Delta u = f$ on a bounded domain $\Omega$ with condition on the edge $\partial \Omega$. In graph theory, a similar problem can be consider : $AU=...
user avatar
  • 2,006
0 votes
1 answer
86 views

Range of eigenvalue in a normalized adjacency matrix

Assuming that $G$ is a simple and undirected graph, no isolated node and let $A$ be the adjacency matrix of $G$. My question is that, what is the range for the eigenvalue of the following normalized ...
user avatar
  • 191
1 vote
0 answers
43 views

Name or symbol for this simple Laplacian matrix

Is there a special name for a symbol for such Laplacian matrix? $$ \begin{bmatrix} 2 & -1 & 0 & 0 & -1\\ -1 & 2 & -1 & 0 & 0\\ 0 & -1 & 2 & -1 & 0\\ 0&...
user avatar
  • 1,401
1 vote
1 answer
52 views

Rank-one modification of a Laplacian as the Laplacian of a larger, weighted graph

The Laplacian $L$ is usually defined for simple graphs, that is, graphs with no self-loops or multiple edges. Consider however the $n\times n$ matrix $M=L+P$, where $P$ has null entries except for one ...
user avatar
-1 votes
1 answer
157 views

What does it mean that a laplacian of directed graph has full rank?

Suppose we have a directed graph $G=(V, E)$ with $N=|V|$ nodes. Define normalized graph laplacian as $L=I-AD^{-1}$ where $A$ is a adjacency matrix of $G$ and $D$ is a degree matrix of $G$. I'm ...
user avatar
0 votes
1 answer
277 views

Laplacian of bipartite graph

It is well know that in the case of weighted graph with positive weights, the dimension of the kernel of the Laplacian is the number of connected components of the corresponding graph. This fails when ...
user avatar
1 vote
0 answers
77 views

Effective resistance of weighted bipartite graph

Question: Let $K_{m,n}$ be a weighted complete bipartite graph with weights $w_{ij}$ for each edge $(i,j)$. What is the effective resistance $R_{i,j}$ between any two nodes of the graph? I am ...
user avatar
1 vote
1 answer
474 views

Laplacian matrix and the eigenvalue 0 of bipartite graphs with no perfect matching

Let $G$ be a bipartite graph with no perfect matching. Show that $\lambda = 0$ is an eigenvalue of the adjacency matrix of $G$. Hint: I do know that I should use the Laplacian matrix of $G$ and also $\...
user avatar
  • 488
1 vote
0 answers
145 views

Dirichlet Energy for Graphs, Derivation

I would like to prove this formulation of the Dirichlet Energy for Graph Neural Networks $$ \begin{aligned} E(\mathbf{X}) &=\frac{1}{d_{i}} \sum_{j \in \mathcal{N}(i)} w_{i j}\left\|\mathbf{x}_{i}-...
user avatar
  • 401
1 vote
0 answers
59 views

Laplacian embedding of a graph with spherical constraint

TL;DR Is there any way to solve the following matrix equation $$ (L - \Lambda)Y = 0 $$ where $L \in \mathbb{R}^{n \times n}$, $Y \in \mathbb{R}^{n \times k}$ (with $k < n$) is a matrix of unknowns, ...
user avatar
  • 382
2 votes
1 answer
427 views

Why use the Fiedler vector?

The Fiedler vector is defined as $$\vec{x_2}=\arg\min_{||\vec{x}||=1,\ \vec{x}^t\vec{x_1}=0}\ \sum_{(ij)\in E}(x_i-x_j)^2,$$ where $\vec{x_1}$ is the smallest eigenvalue's eigenvector. It can be used ...
user avatar
0 votes
1 answer
148 views

Laplacian Graph Embeddings with Weighted Graphs

In "A Simple Baseline Algorithm for Graph Classification" it says your graph $G$ must be "undirected and unweighted". Why must it be unweighted? Looking through the equations it is ...
user avatar
  • 101
1 vote
0 answers
87 views

Finding the eigenvalues of a discrete laplacian on an infinite lattice

If we define the Laplacian as a square matrix with zeroes on the diagonal, and -1 on the diagonals exactly above and below the main diagonal, and 0 everywhere else, how would one go about finding its ...
user avatar
0 votes
1 answer
301 views

Graph laplacian: second smallest eigenvalue

Let $G$ be a weighted undirected graph with vertex set $V$ and weight matrix $W$. Given $S\subset V$, we define $$cut(S,S^c):=\sum_{i\in S,j\in S^c} w_{ij}$$ Let $L$ be the graph Laplacian of $G$. It ...
user avatar
1 vote
0 answers
129 views

Eigenvalues of the product of: a symmetrical Laplacian matrix; and a diagonally dominant matrix with positive diagonal terms

I have: a symmetric Laplacian matrix L with the usual zero eigenvalue and all other eigenvalues have positive real parts, and: a strictly diagonally dominant matrix M with strictly positive diagonal ...
user avatar
1 vote
1 answer
805 views

Graph Laplacian quadratic form, unusual notation

I have following task: Let A be the adjacency matrix and L the graph Laplacian of a simple undirected connected graph G. Show that for an arbitrary vector of real numbers x ∈ $\mathbb{R}^n$ the graph ...
user avatar

1
2 3 4 5