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.

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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?
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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}},(\...
user avatar
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 ...
user avatar
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)...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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} ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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$. ...
user avatar
  • 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'...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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.?
user avatar
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$...
user avatar
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 ...
user avatar
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 ? ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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+...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 382

1
2 3 4 5
11