Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 $\...