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).
239
questions
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$ ...
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 ...
- 61
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}}{...
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 ...
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 ...
- 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
- 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?
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, ...
- 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 ...
- 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 ...
- 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 ...
- 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$...
- 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 $||\...
- 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, ...
- 63
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. ...
- 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,...
- 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 ...
- 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\...
- 311
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 ...
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}^{...
- 1
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 ...
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 ...
- 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 ...
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 + ...
- 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.$$
...
- 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 ...
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 ...
- 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 ...
- 103
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 ...
- 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 ...
- 177
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 ...
- 4,534
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 ...
- 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 $\...
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 + ...
- 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=...
- 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 ...
- 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&...
- 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 ...
-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 ...
- 43
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 ...
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 ...
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 $\...
- 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}-...
- 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, ...
- 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 ...
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 ...
- 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 ...
- 151
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 ...
- 947
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 ...
user850304
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 ...
- 15