For questions on spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial,...
1
vote
2answers
33 views
Upper bound on the difference between two elements of an eigenvector
Let $W$ be the non-negative, symmetric adjacency/affinity matrix for some connected graph. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have a heavily weighted edge between them. If $W_{ij} = ...
0
votes
0answers
8 views
What is the difference between k-means and k-medoids?
I need to partition some graphs by using spectral clustering. Those graphs can be symmetric or asymmetric with positive weights on edges.
As I know, both plus indicator vector are three methods for ...
0
votes
0answers
11 views
when does a graph with normalized laplacian have a uniform degree distribution?
Consider the graph $G(A)$ with A as its adjacency matrix. Let $L$ be its Laplacian and $L_{sym} = D^{\frac{1}{2}}LD^{\frac{1}{2}}$ be the normalized Laplacian. Now let $A(L_{sym}) = I - L_{sym}$ ...
0
votes
0answers
12 views
Spectra of composition of graphs (lexicographic product)
I would like to know how to relate the eigenvalues (eigenvectors) of the lexicographic product of two graphs in terms of the eigenvalues (eigenvectors) of the factors...I hope someone can help me...
0
votes
1answer
30 views
For which spectrum is the following result for?
I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read ...
1
vote
0answers
36 views
Bounds on the maximum eigenvalue of the adjacency matrix of a graph.
I managed to proof the following result for the maximum eigenvalue:
$
d_{avg}\leq \lambda_{max} \leq \Delta(G)
$
where $d_{avg}$ is the average degree of the graph while $\Delta(G)$ is the maximum ...
4
votes
1answer
34 views
What graph Laplacians commute
I know that the graph Laplacian of a fully connected graph commutes with the Laplacian of any other graph.
Is there any theorem stating something similar about some more general family of graphs? ...
0
votes
0answers
26 views
Spectral density of a directed graph?
I have two specific queries:
When computing spectral density function for undirected graphs, we have
\begin{equation}
\label{specdensity}
\rho(\lambda) = \frac{1}{n}{\sum_{j=0}^{n-1} ...
2
votes
1answer
74 views
Global solution for spectral clustering
I used spectral clustering for directed graphs suggested by Dengyong Zhou paper to partition the graph.I selected the eigen vectors corresponding to k largest eigen values and then I use kmeans or FCM ...
1
vote
2answers
57 views
Adjacency, Laplacian and Maximum Degree
I am relevantly new to http://math.stackexchange.com/ and this will be my first question, although I have been lurking around for some time now! So, pardon me if I am missing any posting etiquette ...
3
votes
2answers
43 views
Graphs with zero spectrum / nilpotent symmetric matrices
Is there a graph theoretic characterization of those graphs with zero spectrum?
Alternatively, can one at least characterize all symmetric nilpotent (complex) matrices, so that one could recognize ...
0
votes
1answer
64 views
Prove $MM^t=A+kI$ for matrices associated to graphs
How can I prove that $MM^t=A+kI$ for incidence matrix $M$ and adjacency matrix $A$ of a $k$-regular graph with $n$ vertices?
It is easy to see that $MM^t$ is an $n\times n$-matrix (like $A$), ...
1
vote
1answer
58 views
Adjacency matrix defines a distance metric
Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that
\begin{equation}
\sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f}
\end{equation}
where $\mathbf{f}$ holds values of ...
0
votes
1answer
49 views
Eigenvalues of graph's laplacians
I'm trying to tackle a question from a homework assignment and one of the problems concerns the relation between eigenvalues of a graph's laplacian and its complement's laplacian. The relation is:
...
1
vote
2answers
55 views
Spectrum of a 3-regular graph
Let $D_n$ be the following graph on $2n$ vertices: $V=\mathbb{Z}_n\times\{0,1\}$ and $E=\{(i,j)(i+1,j): i\in \mathbb{Z}_n,j\in \{0,1\}\}\cup\{(i,0)(i,1):i\in\mathbb{Z}_n\}$. What is the spectrum of ...
1
vote
1answer
57 views
Spectrum of the cycle graph $C_n$
I am trying to find out the spectrum (the collection of eigenvalues) with their multiplicities of the cycle graph $C_n$. Assuming that $X=\pmatrix{x_1\\x_2\\\vdots\\x_n}$ is the eigenvector, by ...
0
votes
0answers
82 views
Eigenvalues of weighted Laplacian matrix $L$ and $ML$, where $M$ is a diagonal matrix with positive entries
I have a weighted Laplacian matrix of a directed graph and a diagonal matrix $M$ with positive entries. Is it possible to establish a relation between the eigenvalues of $L$ and those of the product ...
1
vote
0answers
26 views
spectral graph theory with “potentials”
Let G be an undirected graph with bounded degree and n vertices. Let L[G] be the corresponding graph Laplacian, which is a symmetric $n \times n$ matrix. Let V be an $n \times n$ diagonal matrix. I am ...
19
votes
5answers
388 views
Motivation for spectral graph theory.
Why do we care about eigenvalues of graphs?
There must be some reason. There is an entire mathematical discipline about them.
I always assumed that spectral graph theory is an extension of graph ...
-1
votes
1answer
70 views
Eigenvalues of a connected graph $G$ are greater than or equal to $-1$ iff $G$ is perfect?
Consider $P_G$ as the characteristic polynomial of the adjacency matrix of the connected graph $G$.
It is easy to prove that $P_{K_n}(x)=(x-n+1)(x+1)^{n-1}$, so all of the eigenvalues of a perfect ...
1
vote
3answers
179 views
How to find the spectrum of the hypercube?
I want to find the proof of the spectrum of the hypercube
1
vote
0answers
58 views
Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?
I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
2
votes
1answer
107 views
Intuitive interpretation of the adjacency matrix as a linear operator.
Naturally we can describe graphs via tables of "yes there is an edge" or "no there is not" between each pair of vertices, so the definition of an adjacency matrix is easily understood. Thinking of ...
4
votes
1answer
84 views
Laplacians, Diagonal Perturbations
Setup: Consider a Laplacian (or Kirchoff) matrix $L = L^T \in \mathbb{R}^{n \times n}$ corresponding to a weighted, undirected and connected graph. That is, a matrix with $L_{ij} \leq 0$ for $i\neq j$ ...
2
votes
1answer
111 views
The number of connected components of a $k$-regular graph equals the multiplicity of k
In similar vein to this question, I am trying to understand the proof of the fact that in a $k$-regular graph, the multiplicity of the eigenvalue $k$ equals the number of connected components.
The ...
3
votes
2answers
423 views
Lowest Eigenvalue of a positive semi-definite matrix
I am reading a paper on spectral graph theory. Let us say we have an adjacency matrix W and a degree matrix D. We construct a Laplacian matrix, L defined as:
L = D - W
The paper claims that L is ...
1
vote
1answer
96 views
Tighter bound on a spectrum of a matrix obtained by partial diagonal shift
A matrix $V\in\mathbb{R}^{n\times n}$ is a full symmetric matrix with negative off-diagonal elements summing (in absolute value) to diagonal elements. Suppose that $V$ has all entries, and let ...
1
vote
1answer
89 views
Strongly connected graph associated with a matrix
This type of matrices $L$ is called Leslie type matrices in Population dynamics:
$$L = \begin{pmatrix} f_{11} & f_{12} & f_{13} & \dotsm & f_{1,i-1} & f_{1,i}& \dotsm & ...
5
votes
3answers
404 views
Eigenvalues of a bipartite graph
Let $X$ be a connected graph with maximum eigenvalue $k$. Assume that $-k$ is also an eigenvalue. I wish to prove that $X$ is bipartite.
Now if $\vec{x}=(x_1,\cdots ,x_n)$ is the eigenvector for ...
2
votes
1answer
125 views
Connectedness of a regular graph and the multiplicity of its eigenvalue
Suppose $X$ is a $k$-regular graph with adjacency matrix $A$. I wish to show that if $k$ has multiplicity $1$ as an eigenvalue of $A$ then $X$ is connected.
By way of contradiction I assume that X is ...
4
votes
0answers
70 views
Extension of Cheeger's inequality with distinguished vertices
The standard Cheeger's inequality for graph $G$ states that
$\frac{1}{2}$ $\lambda$ < $\phi(G)$ < $\sqrt{2\lambda}$
where $\lambda$ is the second smallest eigenvalue of the normalized ...
4
votes
1answer
87 views
Questions on fractional Laplacian graph spectra
Both the signed ($D-A$) and unsigned ($D+A$) Laplacian are of interest in spectral graph theory, see eg Cvetkovic: Bibliography on the signless Laplacian eigenvalues: first one hundred references.
...
4
votes
1answer
102 views
characteristic polynomial of the adjacency matrix of a tree
I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that
$$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$
where $N_k(T)$ is the number ...
2
votes
1answer
1k views
Plotting a one-sided amplitude spectrum
I have a continuous signal $x(t)$ such that
$$x(t)=12\cos(6\pi t)+6\cos(24\pi t)+3\cos(30 \pi t)$$
and is asked to sketch a $1$-sided Amplitude Spectrum of the signal $x(t)$ if sampled above the ...
3
votes
2answers
152 views
A finite graph G is $d$-regular if, and only if, its adjacency matrix has the eigenvalue $λ = d$
Show that a graph $G$ finite with $n$ vertices is $d$-regular if, and only if, the vector with all the coordinates equals to 1 is eigenvetor from eigenvalue $λ = d$ from the adjacency matrix
$A$ ...
8
votes
1answer
366 views
Eigenstructure of discrete Laplacian on uniform grid
The discrete Laplacian of a graph is the matrix $L = D - A$ where $D$ is a diagonal matrix with $d_{ii}$ being the degree of $v_i$, and $A$ is the usual adjacency matrix.
Is there anything known ...
2
votes
0answers
39 views
Properties of a generalized graph
I'll start with formulating my problem and then ask my question:
To generalize a graph $Ga = (Va,Ea)$, we partition its nodes into disjoint sets. The elements of a partitioning $V$ are subsets of ...
3
votes
1answer
173 views
Spectral graph theory and connected components of graphs
We know that multiplicity of least eigenvalue of laplacian matrix of graph gives us number of connected components in graph.What is intuition behind this theorem?
How do we know that this works in ...
6
votes
3answers
667 views
Significance of eigenvalue
When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
16
votes
1answer
1k views
What do the eigenvectors of an adjacency matrix tell us?
The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality.
What do the second, third, etc. eigenvectors tell us?
Motivation: A standard information ...
9
votes
5answers
876 views
Spectrum of adjacency matrix of complete graph
Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$.
...
1
vote
0answers
102 views
Spielman. Spectral Graph Theory Proposition
Spielman says in Lecture 3: Laplacians and Adjacency Matrices
Fiedler’s Theorem will follow from an analysis of the eigenvalues of tri-diagonal matrices with zero row-sums. These may be viewed as ...
1
vote
1answer
113 views
Relationship Between Eigenvalue and Degree
I have a question regarding Rayleigh quotient.
It's well known that maximal eigenvalue can be found by
$$\lambda_{\max}(M)=\max_{x\neq 0}\frac{x^{T}Mx}{x^{T}x}.$$
Using this how to prove that ...
1
vote
0answers
63 views
algebraic connectivity of the giant component
In percolation theory there is this idea of a giant component, and I am curious what is known about its algebraic connectivity. I looked on google but I was not able to find anything particularly ...
7
votes
1answer
185 views
Spielman's proof of graph connectivity
I use Spielman's lectures on course Spectral Graph Theory
I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
0
votes
1answer
147 views
Proof of Algebraic connectivity
I am very curious about the proof of Algebraic connectivity
Algebraic connectivity:
The algebraic connectivity of a graph $G$ is the second-smallest eigenvalue of the Laplacian matrix of $G$. ...
7
votes
1answer
134 views
Two formulas for the minimal eigenvalue of a graph
Hello again everybody,
I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
10
votes
1answer
228 views
What does the minimal eigenvalue of a graph say about the graph's connectivity?
I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
2
votes
0answers
302 views
Is there any relation between the principal eigenvalue of sub matrix and the original matrix?
I am wondering whether there is any relation between principal eigenvalue of sub matrix and the original matrix.
In fact I am facing a problem which is to select $n$ rows and $n$ columns from the ...
2
votes
1answer
239 views
Does an $n\times n$ adjacency matrix of a scale-free network graph have $n$ distinct eigenvalues?
Question updated
Suppose that I have an $n\times n$ adjacency matrix $\mathbf{A}$ of a simple graph $G$ where the entry $(i,j)$ represent the number of edges between node $i$ and $j$ in $G$. Note ...
