Questions tagged [spectral-graph-theory]
For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.
529
questions
1
vote
0
answers
15
views
Spectral radius and maximum degree of a graph [duplicate]
How can I show that the spectral radius of a graph $G$ is less than or equal to its maximum degree?
I have an unweighted graph $G=(V,E)$, where $V$ is its vertex set and $E$ its edge set. The degree ...
- 11
0
votes
0
answers
10
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
26
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
17
views
Can any Markov chain on a finite state space be modelled as a random walk on a graph? What about models of non-finite state space MC?
I am reading about mixing times of Markov chains, and one result I am looking at concerns characterising when a phenomenon called 'cutoff' occurs, based on "the inverse spectral gap of the Markov ...
- 2,947
1
vote
0
answers
16
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 ...
- 280
0
votes
0
answers
9
views
How can I select K value of K-means from eigengap?
I have studied perturbation theory and spectral graph theory to calculate the optimal number of clusters .Eigengap heuristic suggests the number of clusters k is usually given by the value of k that ...
- 280
0
votes
0
answers
16
views
Confusion regarding the derivation of graph convolution
I am currently studying Spectral Graph Convolutions, and I am following this document: https://atcold.github.io/pytorch-Deep-Learning/en/week13/13-1/. They have derived the convolution as follows:
The ...
- 33
0
votes
0
answers
8
views
Graph join and the Laplacian spectrum of a graph $G$ having eigenvalue 1 of multiplicity 2.
Let $G$ be a connected graph of order $n$ with a Laplacian spectrum of the following form
$$\sigma_L(G)=\{0,1,1,\mu_4,\ldots,\mu_n\},$$
where all the eigenvalues are integer numbers with exactly one ...
- 69
3
votes
1
answer
69
views
what are the benefits of using Spectral K-means over Simple K-means ? and how Spectral K-means overcomes the local minimum problem of K-means?
I have understood why K-means get stuck in local minima
Now I am curious to know how spectral k-means helps to avoid this local minima problem?
According to this paper A tutorial on Spectral,
...
- 280
0
votes
0
answers
20
views
maximum eigenvalue of graphs different in only one edge
Show that if the graphs $G, G'$ differ in only one edge, then $|\lambda_1(G) −
\lambda_1(G')|\leq 1$, where $\lambda_1$ indicates the maximum eigenvalue of a graph.
First, I'm not sure if I ...
0
votes
0
answers
23
views
Spectra of a weighted path graph
In Spectra of Simple Graphs
, it is given that an unweighted path graph with $n$ vertices has eigenvalues
$$
2\cos(\pi j/(n+1)), j = 1,\cdots, n.
$$
All multiplicities are 1. Assuming the edges of ...
- 33
0
votes
0
answers
5
views
How to write in form of a function the eigenvalues sets of a particular order.
I am trying to write in the form of a function the following set of eigenvalues. The superscript indicates the multiplicity of a particular eigenvalue.
$\sigma_L(\beta_{2k})=\{0,(n_{2k})^{n_{2k-1}},(\...
- 69
0
votes
0
answers
55
views
A directed version of strongly regular graphs
Strongly Regular Graphs (SRGs) can be defined as $k$-regular graphs with exactly two distinct eigenvalues different from $k.$
Define Strongly Regular Digraphs (SRDs) as $k$-regular digraphs with ...
- 376
0
votes
0
answers
20
views
Eigenvalues generalization of some specific order.
I have Laplacian spectrum of some families of graphs as follows:
$\sigma_L(\beta_1)=\{0,n_1^{n_1-1}\}$,
$\sigma_L(\beta_2)=\{0,n_2^{n_1-1},(n_1+n_2)^{n_2}\}$,
$\sigma_L(\beta_3)=\{0,n_3^{n_2},(n_1+n_3)...
- 69
1
vote
1
answer
53
views
prove that $\Delta(G)\leq \lambda_{max}^2$
Let $G$ be a graph and let $\lambda$ be its largest eigenvalue. Prove that
$$\Delta(G)\leq \lambda^2$$
where $\Delta(G)$ is the maximum degree of vertices of $G$.
I've seen this problem being regarded ...
0
votes
0
answers
105
views
Meaning of eigenvalues of an adjacency matrix
I know the eigen vector of a matrix transformation is the vector that turns it into a scalar transformation.
But in the context of a adjacency matrix and in a graph, what does the eigen vector or ...
0
votes
0
answers
15
views
How RatioCut leads to unnormalized spectral clustering?
I have understood the underlying concepts of spectral clustering and how inter cluster distance equation is mapped to a matrix form and how it is optimized using lagrange multiplier. But unable to ...
- 280
0
votes
0
answers
20
views
Eignevectors of limit matrix and limit of eigenvector sequence (for irreducible Markov chains)
I have the following:
Problem
Suppose $T$ is an $n\times n$ irreducible row stochastic matrix. Fix a row $\hat{i}$. Let $\epsilon\in(0,1)$.
Define $T(\epsilon)$ by:
$$t_{jk}(\varepsilon)=\begin{cases} ...
- 2,673
1
vote
0
answers
46
views
Why to normalize an adjacency matrix?
In Kipf & Welling (2017) paper https://arxiv.org/pdf/1609.02907.pdf. It uses the normalized adjacency matrix $\mathbf{A}_{symm} = \mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$. I know the largest ...
- 123
1
vote
2
answers
95
views
Why aren't the eigenvectors of a graph's adjacency matrix useful for the graph isomorphism problem?
I know eigenvalues of a graph's adjacency matrix are very heavily studied because of their relationship to the structure of the graph, but how come no one studies the eigenvectors? Even if they don't ...
- 384
3
votes
0
answers
30
views
Absolute spectral gap of simple random walk on box (Levin–Peres–Wilmer exercise 13.2)
I am working on the following problem from Levin–Peres–Wilmer, "Markov Chains and Mixing Times," chapter 13:
Exercise 13.2. Show that for the lazy simple random walk on the box $\{1,\dots,n\...
- 969
2
votes
3
answers
41
views
Closed Walks and Edge Addition
If $G$ is a simple graph with adjacency matrix $A$, then $c_k(G):=\mbox{tr}A^k$ gives the number of closed walks in $G$ of length $k$. Let $G'$ denote the graph obtained from $G$ by adding an edge ...
- 421
1
vote
1
answer
90
views
Largest eigenvalue of a bipartite biregular graph
Let $G$ be a bipartite biregular graph. That is, $G$ is a bipartite graph with vertex sets $V_1$ and $V_2$ such that every vertex in $V_1$ has degree $d_1$ and every vertex in $V_2$ has degree $d_2$. ...
- 687
1
vote
1
answer
59
views
Spectra of Graphs
Suppose $G$ is simple (no loops or multiple edges) graph of order $n$. Its adjacency eigenvalues $\lambda_1\geq \lambda_2\geq \cdots\geq \lambda_n$ satisfy $\lambda_1+\lambda_n+\cdots+\lambda_n=0.$ I'...
- 421
0
votes
1
answer
60
views
Is there is any relationship between determinant and spectral radius of the matrix?
We all know that determinant is the product of the eigen values of a matrix. I have found some general term for the determinant of the adjacency matrices from some series of graphs. Can i establish ...
- 41
1
vote
2
answers
60
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
4
votes
1
answer
50
views
Is it known how many graphs on $n$ vertices have the same characteristic equations?
Is there a formula that shows how many simple graphs on $n$ vertices have the same characteristic equations?
To be crystal-clear, I am not asking about a function that says how many graphs share the ...
- 1,137
0
votes
1
answer
29
views
Largest eigenvalue of a weighted sum of two matrices
Let $A$ be the adjacency matrix of an undirected and simple graph (so it is symmetric and the entries are 0 or 1).
Suppose I have a decomposition $A = B + C$ where $B$ and $C$ are matrices of same ...
- 1
1
vote
1
answer
24
views
Disconnected Threshold graph is Possible?
I am a little confused in understanding the definition of the Threshold graph. My question is: Is a threshold graph be a disconnected graph? Or a threshold graph will always be connected.?
- 69
1
vote
1
answer
81
views
eigenvalues of line graph
Let $G$ be a simple graph with incidence matrix $M$.
a) Show that the adjacency matrix of its line graph $L(G)$ is $M^t M − 2I$, where $I$ is the $m × m$ identity matrix.
b) Using the fact that $M^t M$...
2
votes
0
answers
83
views
what is the purpose and consequences of Eigenvalues in graph theory? [closed]
I am trying to understand Eigenvalues and their repercussions in graph theory. I have read that Eigenvalues help describe certain parameters of graphs which provide information about the general ...
0
votes
1
answer
42
views
Finding Graph from eigenvectors
I have an matrix A whose columns I want as the eigenvectors of the Laplacian of a graph. I can take any real eigenvalues such that the graph exists. How do I go from here to reconstructing the graph ? ...
- 441
1
vote
0
answers
44
views
Spectral partitioning and Fiedler Vector
As we know, the Fiedler vector is the eigenvector corresponding to the second smallest eigenvalue and this vector can be used for graph partitioning. We also know that this vector comes from a relaxed ...
- 43
1
vote
1
answer
128
views
Measure similarity between isomorphic graphs with different node labels
I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges,...
- 45
0
votes
0
answers
41
views
What is the relationship in the spectra of A and PA, where P is some permutation matrix?
I'm curious what effect a permutation has on the spectrum of a real, symmetrical matrix. More specifically, given adjacency matrix $A$ and a permutation matrix $P$, can I say anything intelligent ...
- 103
1
vote
0
answers
25
views
Change in spectrum of graph by adding pendant vertex
I am wondering the following. If we add a pendant vertex to a graph we are changing the spectrum. Eigenvalue interlacing tells us that the largest e-value of the new graph is at least as big as that ...
- 466
2
votes
1
answer
92
views
How does graph Fourier transform retain structural information?
Context: I am reading about graph Laplacian matrices $L = D - A$ and how their eigenvectors correspond to Fourier modes. From spectral decomposition, $ L = U \Lambda U^{T}$, where $\Lambda$ is a ...
1
vote
1
answer
65
views
Does Laplacian matrix have to be circulant to have eigenvectors which are Fourier modes?
I am reading the following book/notes on Graph Representation Learning (here) and have a number of questions from Chapter 7.
Context: In section 7.1.3 of the notes, we have the following bit of the ...
2
votes
0
answers
50
views
Question about eigenvectors of Laplacian matrix in relation to graph Fourier transform?
I am reading the following book/notes on Graph Representation Learning (here) and have a number of questions from Chapter 7.
Context: In section 7.1.3 of the notes, we have the following bit of the ...
0
votes
0
answers
52
views
What is the intuition behind graph convolution?
I am reading the following book/notes on Graph Representation Learning (here) and have a number of questions from Chapter 7. I will use this post to ask one of them.
Context: In section 7.1 of the ...
2
votes
2
answers
238
views
Spectral radius of a graph
I researched about the spectral radius and was confused. There are two definitions.
The spectral radius of a finite graph is defined to be the spectral radius of its adjacency matrix. the spectral ...
- 361
1
vote
1
answer
104
views
the disjoint union of complete graphs is ds, with respect to adjacency matrix.
In Which graphs are determined by their spectrum? proposition 6 states "the disjoint union of complete graphs is DS, with respect to adjacency matrix." A graph is said to be DS (determined ...
- 361
2
votes
1
answer
92
views
spectrum of a regular graph and its girth
How we can find the girth (the shortest cycle) of a regular graph from its adjacency spectrum? I know we can find the number of closed walks of length $k$ by:
$$\operatorname{tr}(A^k)= \displaystyle\...
- 361
1
vote
2
answers
126
views
Eigenvalues of the join of two graphs?
We define the join of two graphs $G = (V(G),E(G))$, $H=(V(H),E(H))$ as the graph:
$$G \wedge H : = (V(G) \cup V(H), E(G) \cup E(V) \cup \{gh: g \in V(G), h \in V(H))$$
If I know the spectrum of the ...
- 1,686
1
vote
1
answer
29
views
Complete bipartite graphs, DS graphs and interlacing theorem
I want to prove $K_{n,n+1}$ is determined by the adjacency spectra, called DS graphs. I try to use theorem 1 of Esser and Harary.
I suppose $tK_1+K_{p,q}$, $p\leq q$, has the same spectra with $K_{n,n+...
- 361
1
vote
1
answer
48
views
why there is no graph whose largest eigenvalue, $\lambda_1$, lies in the intervals $(0,1)$ or $(1,\sqrt{2})$?
why there is no graph whose largest eigenvalue, $\lambda_1$, lies in the intervals $(0,1)$ or $(1,\sqrt{2})$? I think it's becaues of if a graph doesn't have any edge then $\lambda_1=0$, if it has ...
- 361
1
vote
0
answers
40
views
Normalize an adjacency matrix twice
I am working on a graph clustering problem and i've seen that applying two consecutive normalizations on the adjacency matrix gives much better performance than when applying a single one.
I first ...
- 55
3
votes
0
answers
37
views
Trees with two eigenvalues?
Is it possible for a tree of order $n$ ($n$ even) to have eigenvalues $(\lambda_1, \ldots, \lambda_1, -\lambda_1, \ldots, -\lambda_1)$ ? Or perhaps $(\lambda_1, \ldots, \lambda_1, 0,-\lambda_1, \ldots,...
- 421
7
votes
1
answer
349
views
When does a matrix have a positive eigenvector?
The generalised problem is as follows: Is there a condition on a symmetric positive-semi-definite matrix $A$ that ensures that it has a positive eigenvector, i.e. an eigenvector $Av = \lambda v$ such ...
- 435
1
vote
1
answer
111
views
Is largest eigenvalue of Hashimoto matrix of a graph always real
I wonder if there are some results which guarantee that the largest eigenvalue of a Hashimoto matrix of a graph is always real (Hashmioto matrices are square but not symmetric, so in general there are ...
- 382