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.
0
votes
0answers
18 views
Find a matrix that describes a modularity score of a partition.
For a partition P of a network of n nodes and m edges into two disjoint communities, $V_{1}$ and $V_{2}$. Let $s=[s_{1},s_{2},...,s_{n}]$ where each $s_{i}$, corresponding to each vertex is 1 if that ...
0
votes
1answer
33 views
When do the eigenvectors of a Laplacian matrix form a basis?
Eigenvectors do not always form a basis. When do the eigenvectors of a Laplacian matrix form a basis? When the associated adjacency matrix is symmetric? Why?
0
votes
0answers
13 views
Characterization of second largest normalized Laplacian eigenvalue
I understand that for an undirected simple graph $G$ we have that the second largest eigenvalue $\lambda_1$ satisfies $$\lambda_1 = \inf_{f \bot T \mathbf{1} } \frac{\sum_{u \sim v} (f(u) - f(v))^2}{\...
0
votes
1answer
22 views
Eigenvalues of path graph $P_n$ from eigenvalues of a cycle graph $C_{2n}$
Let $P_n$ be a path graph. This is from my textbook: View $P_n$ as the result of folding $C_{2n}$, where the folding has no fixed vertices. An eigenvector of $C_{2n}$ that is constant on the preimages ...
0
votes
0answers
6 views
A proof for the existence of $n$ non-negative eigenvalues of the Graph Laplacian
For the Graph Laplacian, we have
$$L = D - W $$
Where $D$ is the degree matrix and $W$ is the weighted adjacency matrix. Can anyone provide a proof for the existence of $n$ non-negative eigenvalues ...
1
vote
1answer
42 views
Show that the largest eigenvalue of a graph is strictly larger than the largest eigenvalue of any subgraph
Let G be a connected graph and H be any proper subgraph of G (obtained from
removing at least one edge or at least one vertex of G). Show that the largest eigenvalue of A(G) is strictly larger than ...
2
votes
1answer
41 views
Small diameter, mixing time, and Expander graphs
Let $\Gamma_n$ be a family of $d$-regular finite simple graphs.
1). $\Gamma_n$ has logarithmic diameter if $diam(\Gamma_n) = O(\log |\Gamma_n|)$;
2). $\Gamma_n$ has logarithmic mixing time if
$$ \...
1
vote
0answers
30 views
Change to spectral radius due to removal of a single vertex from graph
Say we have a graph $G$ on $n$ vertices, with eigenvalues $\lambda_1 \leq \dots \leq \lambda_n$ and spectral radius $\rho_G$. Let $H$ be the induced subgraph where we remove a single vertex from $G$, ...
0
votes
0answers
13 views
General subgraph counts using eigenvalues
Let $G$ be a graph. Then we know the number of cycles of length $l$ in $G$ is just the $l$-th spectral moment of the adjacency matrix.
I want to know if there is any such formula for general ...
0
votes
1answer
48 views
Graphs with zero eigenvalues
I search about known graphs have spectrum with the most zero eigenvalues respect to their adjacency matrix. I know null, complete, bipartite and cocktel party graphs.
Any kind of suggestion is ...
0
votes
1answer
66 views
Graphs with rational eigenvalues
Let $A$ be the adjacency matrix of a graph with eigenvalues $\lambda_i$. My questions are:
Is there any assumption/conditions for a graph to have all rational eigenvalues ($\lambda_i \in \mathbb{Q} \;...
0
votes
0answers
16 views
Approximate graph
Let $L_{G}$ be the Laplacian of a graph $G$ with irrational eigenvalues. I am curious to know:
Is there any efficient way to find an approximate graph $\hat{G}$ such that all the eigenvalues of this ...
0
votes
1answer
40 views
Spectral analysis
Prove that graph with the largest eigenvalue less than $2$ is acyclic.
I tried to prove the above statement by taking into consideration the maximum degree. Maximum degree is greater than equal to ...
0
votes
0answers
21 views
Distance spectral radius of unicyclic graph
Let $U$ be a unicyclic graph of order $d+2$ (shown in figure). We obtain a graph $U(p_2,...,p_d,p_{d+2})$ of order $n$ from $U$ by attaching $p_i$ pendant vertices to each $v_i \in (U)\backslash\{v_1,...
0
votes
0answers
22 views
Computing coefficients of the generating function counting trees with forbidden members
How can I compute the coefficients $r^{(n)}_p$ with a Python code using the following equations?
\begin{equation}\label{10}
r^{(n)}(x)= S^{(n)}(x)-\frac{1}{2}\left[ (S^{(n)}(x))^2-S^{(n)}(x^2)\right]
...
2
votes
0answers
58 views
Characteristic polynomial of a tree
I'm trying to understand the article: László Lovász, Jozsef Pelikan, On the Eigenvalues of Trees, Periodica Mathematica Hungarica, March 1973.
I'm not sure I fully understand the proof of Lemma 1: if $...
1
vote
1answer
47 views
Almost all trees are cospectral (Allen Schwenk's 1973 article)
I am currently working on the following article: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral.
There are a few things that I don't understand, and since the ...
1
vote
0answers
11 views
Do strongly regular graphs maximize spectral gaps?
Across the set of d-regular n-vertex graphs, if there is a strongly regular graph in that set, it often (always, as far as I was able to check) seems to maximize the spectral gap: $\lambda_1 - \...
0
votes
1answer
45 views
eigenvalues weighted ring graph
Consider an undirected ring graph of $n$-vertices. To be more specific, each node $i$ has edges $(i,i+1)$ and $(i,i-1)$. When all edges have weight $w_{i,j}=1$ then the eigenvalues and eigenvectors of ...
1
vote
0answers
19 views
It is possible for the nodes of a network to have a different total cost. If they have the same value in degree centrality?
I do same simulations with randoms networks and for each network and calculates different measures such degree centrality. In the network is likely more than one node to have the highest degree value. ...
0
votes
1answer
32 views
How to understand the spectrum of a graph?
This is from my textbook: $A$ is the adjacency matrix of a finite graph. Writing down $A$ requires one to assign some numbering to the vertices. However, the spectrum of the matrix obtained does not ...
1
vote
0answers
30 views
Perron-Frobenius theorem in non-negative block matrices with some zero columns
Assume we have a non-negative block square matrix $B$ as follows
$B=\left[
\begin{array}{c|c|c}
\mathbf{0}&\mathbf{B}_{12}&\mathbf{B}_{13}\\
\hline
\mathbf{0}&\mathbf{B}_{22}& \mathbf{...
2
votes
1answer
40 views
Prove $D-A$ is similar to $D+A$ iff the graph is connected and bipartite
If $A$ is the adjacency matrix for the Graph $G$ and $D$ is the diagonal matrix of degrees, $D-A$ is the laplacian of the graph and $D+A$ is sometimes called the signless laplacian.
I want to prove ...
2
votes
0answers
78 views
Modifying Heat Kernel Equation for Graphs
In spectral graph theory, I am aware that the following weight recurrence:
$$ w_t(v_i) = \frac{1}{2}w_{t-1}(v_i)+\sum_{v_j \mid \exists e_{ij} }\frac{1}{2deg(v_i)} w_{t-1}(v_j) $$
Can be expressed ...
0
votes
0answers
28 views
Functions upon weights of a graph
Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such ...
0
votes
0answers
32 views
Is there anything special about the matrix $D^{-1}AD^{-1}$?
I wonder if the matrix $M = D^{-1}AD^{-1}$ has some special properties where $A$ is the adjacency matrix of a graph and $D$ is its diagonal degree matrix.
I know that $D^{-1}A$ is the probability ...
0
votes
0answers
20 views
Sampling probabilities for half-sparsification algorithm
https://dl.acm.org/citation.cfm?id=2948062
In their article(simple parallel and distributed algorithms for spectral graph sparsification 2016), Koutis and Xu gave a combinatorial algorithm for ...
0
votes
1answer
26 views
Expectation in spectral sparsification algorithms
I am new to random matrices. I am studying the (Sampling) sparsification algorithms done by Daniel Spielman, Teng, Srivastava.
They used the concept of graph sampling to obtain a good spectral ...
0
votes
1answer
32 views
Create a space between clouds
I have a dataset associated with labels. According to https://arxiv.org/pdf/1802.03426.pdf --> UMAP (Uniform Manifold Approximation and Projection) which is a novel manifold learning technique for ...
0
votes
0answers
18 views
Decomposition of a block matrix related to graph Laplacians
I'm working on graph networks in a communications problem and I have trouble understanding how to work with this $3 \times 3$ block matrix related to graph Laplacians:
D =
\begin{bmatrix}
\rho ...
0
votes
0answers
14 views
Directed graphs with non-normal adjacency or laplacian matrices
Is there a class of directed graphs whose adjacency or laplacian matrices will always be non-normal?
1
vote
0answers
17 views
Geometric series of binary relation
Let $\rho\subset X\times X$ be a symmetric binary relation on a finite set $X$. Let $\overline{\rho}\subset X\times X$ be its transitive closure :
$$
\overline{\rho}=\bigcup_{i=0}^\infty \rho^{\circ i}...
2
votes
0answers
49 views
Does the Laplacian of a path graph have the smallest eigenvalues for any tree graph of equal number of vertices?
Suppose there are two connected graphs with $|V|=n$. One is a path graph $P$ and the other is an arbitrary tree graph $T\neq P$. If $L(G)$ is the Laplacian of the graph $G$, is it true that
$$L(T) - L(...
1
vote
1answer
454 views
Laplacian of a directed weighted graph
I know that for a simple undirected graph $\mathcal{G}(V,E) $ the Laplacian matrix $L$ is defined as:
$$ L:=D-A$$ where $D$ is the degree diagonal matrix and $A$ is the adjacency matrix of $\mathcal{G}...
2
votes
0answers
17 views
Is $\|\lambda\|_3 << \|\lambda\|_2$ for all sub-matrices of a random matrix?
Let $A\in\{0,1\}^{n\times n}$ be a random, symmetric matrix, in which each upper triangular entry is sampled iid. from Bernoulli($p$).
Let $\lambda=(\lambda_1, \dots, \lambda_n)$ be the vector of ...
2
votes
2answers
83 views
How did Spectral Graph theory emerge?
I was wondering how did Spectral graph theory, this multidisciplinary area between Linear Algebra and Graph theory start?
How did it emerge?
Was there a certain problem (maybe graph isomorphism ...
0
votes
0answers
39 views
Is the gap between the largest and second largest eigenvalues of a symmetric, unnormalized adjacency matrix related to expansion of the network?
I am working on analyzing an algorithm and its variance depends on the gap between largest and second largest eigenvalues of the adjacency matrix of an undirected, weighted graph. However, the ...
1
vote
1answer
118 views
Do there exist $d$-regular expander families with Cheeger constant greater than $d/2$?
Definitions.
For a finite simple graph $G=(V, E)$, the Cheeger constant for $G$ is defined as
$$
h(G) = \inf_{S} \frac{e(S, S^c)}{\min\{|S|, |S^c|\}}
$$
where $S$ runs over all non-empty proper ...
1
vote
1answer
66 views
Why are we interested in finding the spectrum of products of graphs?
Recall that the spectrum (Laplacian spectrum resp.) of a simple undirected graph is the spectrum of its adjacency matrix (Laplcian matrix resp.).
Moreover, many products of graphs have been ...
2
votes
0answers
110 views
Partition function inequality for Gibbs states associated with graphs
Suppose I have two undirected graphs $G_1$ and $G_2$ with the same vertex set $V$ and let $A_1$ and $A_2$ denote their respective adjacency matrices. Define the intersection of the two graphs $G_\cap$ ...
0
votes
0answers
20 views
Families of $d$-regular undirected graphs with small spectral gaps
I'm trying to workout some results and would like to know of families of (deterministic) graphs that are regular and undirected that have low spectral gap. In particular, they should not be good ...
1
vote
0answers
35 views
Small spectral gap implies bottleneck for regular graphs?
Suppose that $G = ([2n], E)$ is a $d$-regular, undirected graph. If every subset of exactly $n$ nodes has at least $d^2$ edges emanating away from it (so $E(S, \overline{S}) \geq d^2$ for every $S \...
0
votes
0answers
49 views
Regular graphs has exactly one main eigenvalue
An eigenvalue $\lambda_{1} $ is said to be a main eigenvalue if it has an associated eigenvector $x_{1} $ whose sum of entries is nonzero, in other words the projection of $e $, the all ones vector, ...
0
votes
1answer
25 views
Relationship between poor spectral expansion and poorly connected subset.
Suppose I have a $d$-regular graph $G = (V, E)$ on $n$ vertices, with second largest eigenvalue $\lambda_2 = cd$, for some $c \in (1/2, 1)$ (which means its spectral expansion is a small constant). ...
2
votes
1answer
184 views
Why the second smallest eigenvalue of the Laplacian of a tree is $\leq1$
I know that the second smallest eigen value of the Laplacian of a star with $n>2$ is $1$.
I want to show the vice versa, i.e., if the second smallest eigen value of a tree is $1$ then the tree is ...
2
votes
0answers
43 views
Distribution of 2nd smallest eigenvalue in an random graph
In a random graph $G(n, p)$, is there any result formalizing the distribution of the 2nd-smallest eigenvalue $\lambda_2$?
$$
P(\lambda_2 \geq x)
$$
1
vote
1answer
77 views
Quotient matrix and interlacing
If $A$ is an adjacency matrix of the connected graph $G$ and $B_\pi$ is its quotient matrix corresponding to an equitable partition $\pi={C_1,C_2,...,C_m}$. Since this quotient matrix is diagonally ...
0
votes
1answer
95 views
Eigenvectors to the largest eigenvalue $\lambda_1$ of $A\geq 0$ are non-zero only at the end of the longest chains when $\lambda_1=0$?
Let $n>0$ and $A\in M_{n\times n}(\{0,1\})$. Suppose the largest eigenvalue $\lambda_{1}=0$ vanishes. Then there is no closed path in the graph, only chains. I have read the claim that only the end ...
0
votes
0answers
170 views
What is the Perron-Frobenius theorem for non-negative matrices?
Let $M\succeq 0$ (i.e. $M_{ij}\geq 0$ for all $i,j$). No further conditions on $M$ such as irreducibility, aperiodicity, or what not. What is the formulation of the theorem in this case?
I believe ...
0
votes
0answers
21 views
Finding a binary matrix with particular singular value and vector
Given an unnormalised vector $v\in\mathbb{N}^n$, find a binary matrix $X\in\{0,1\}^{m\times n}$ with the smallest possible $m$ such that $v$ is a right singular vector of $X$ with singular value $\...
