For questions related to the study of properties of a graph in relationship to the spectral properties of some associated matrix.

learn more… | top users | synonyms

7
votes
0answers
532 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N \...
7
votes
0answers
299 views

What can we say about two graphs if they have similar adjacency matrices?

Suppose we have two (finite, simple, undirected) graphs, what can we say about these graphs if they have similar adjacency matrices? Observations to begin with: If $G_1$ and $G_2$ are isomorphic, ...
6
votes
0answers
191 views

Constructing a directed graph from its spectrum

This is related to the following question from cs theory stack exchange: http://cstheory.stackexchange.com/questions/3742/reverse-graph-spectra-problem So it seems as if given a sequence of real ...
5
votes
0answers
119 views

Theoretical link between the graph diffusion/heat kernel and spectral clustering

The graph diffusion kernel of a graph is the exponential of its Laplacian $\exp(-\beta L)$ (or a similar expression depending on how you define the kernel). If you have labels on some vertices, you ...
5
votes
0answers
70 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
4
votes
0answers
39 views

Multiplicity of 0 eigenvalue of directed graph Laplacian matrix

I am looking for a result (if it exists) for directed graphs relating the multiplicity of 0 eigenvalues of the directed Laplacian matrix. Consider a directed graph $\mathcal{G}=(\mathcal{V},\mathcal{...
4
votes
0answers
137 views

What do the eigenvalues/vectors of a metric describe?

Given a finite metric space $(X = \{ x_i \}_{i=1}^n,d)$, one can form the matrix $A$ of pairwise distances $a_{ij} = d(x_i, x_j)$. What does the eigenspectrum of this matrix say about the metric $d$? ...
4
votes
0answers
74 views

Question about Szemeredi's regularity lemma and eigenvalues of a graph

In the context of Szemeredi's regularity lemma, is there any way to relate the eigenvalues of the ambient graph with the densities of an $\epsilon$-regular partition? More precisely, if $V(G) = V_{0}...
4
votes
0answers
276 views

spectral radius (adjacency matrix) of a partitioned graph

Is the following bound on the largest eigenvalue of a partitioned graph known? It seems like it should be but I am not able to find a reference to it. Given a graph $G=(V,E)$ whose vertices are ...
4
votes
0answers
82 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 ...
3
votes
0answers
87 views

Integral identity graphs — smallest example

From Paulus Graphs. "The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs (or asymmetric) and identity graphs (a graph spectrum ...
3
votes
0answers
49 views

sum of the modulus eigenvalues of a matrix A >= B.

Kindly help me to prove/disprove the following statement. Let $A$ be a symmetric matrix of order $n \times n$ with all the diagonal entry equal to $0$, and other non-diagonal entry equal to $k$ (...
3
votes
0answers
40 views

Possible lower Bound of radius of a graph

First of all I would like to ask people to forgive me because the question that I am about to ask is based on results of a study that I was involved in this year. The project was about designing ...
3
votes
0answers
86 views

Eigenvalue of Block matrix: Adjacency of complete bipartite Graph

Let $A\in \{0,1\}^{mn \times mn}$ be the adjacency matrix of a complete bipartite graph with $m$ and $n$ vertices each, i.e. let $A$ be the matrix consisting of two blocks $A_1\in \{0,1\}^{m \times m}$...
3
votes
0answers
40 views

What do we know about inverses of matrices which are “like” Laplacians of graphs?

Consider the Laplacian $L$ of a bipartite graph. Is there any generic understanding we have about what $1/(z-L)$ looks like? [say $z > \lambda_\max(L)$)] You can consider variations of $L$ like ...
3
votes
0answers
30 views

How networks with high largest eigenvalues are more robust?

In the literature, it sometimes indicates that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust. Robustness here is relevant to link/...
3
votes
0answers
79 views

Is there an easy way to realize a graph (i.e. get adjacency matrix) from a fundamental cut-set or loop matrix?

I am looking to realize a graph (i.e. write down its adjacency or incidence matrix) given a fundamental cut-set matrix or loop matrix (with respect to an arbitrary spanning tree). Is there some ...
3
votes
0answers
217 views

Interesting Questions in Spectral Graph Theory

In the past, I have worked on few problems in Spectral graph theory and their applications to Physics. I have read parts of Fan Chung's book and Daniel Spielman lecture notes. I really enjoyed the ...
3
votes
0answers
79 views

Is the upper Cheeger Inequality tight?

The (upper) Cheeger Inequality says: Let $G$ be an unweighted, undirected, regular graph of degree $d$. Let $\lambda_2$ be the second eigenvalue of the Laplacian matrix of $G$, and let $\phi(G)$ ...
2
votes
0answers
8 views

Can a graph be recovered from its Bonacich centrality vector?

Let $A$ be the adjacency matrix of a directed graph with $n$ vertices and spectral radius $\lambda$. Let $I$ be the $n \times n$ identity matrix and let $e \in \mathbb{R}^n$ be the vector of 1's. For $...
2
votes
0answers
207 views

Is each edge interpreted like a $2$-cycle?

Let $a_k$ a an eigenvalue of the adjacency matrix $A$ of a planar cubic graph with $n$ vertices. For the returning paths without backtracking we get the generating function of $$G(x,a)=\frac{1-x^2}{1-...
2
votes
0answers
27 views

Integral roots of a circulant matrix

When does the circulant matrix have only integral roots? For example: adjacency matrix for $K_n$ has all the roots integral which is circulant, but in case of Cycle on $n>3$ it is circulant but it ...
2
votes
0answers
52 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
2
votes
0answers
66 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
2
votes
0answers
141 views

Clustering with SVD

I'm trying to do some clustering on a graph, which is represented by an adjacency matrix $B = A^2$, where $A$ is symmetric. I tried several methods like taking the eigenvectors of the Laplacian $L = ...
2
votes
0answers
71 views

Spectral gaps of common graphs

I'm looking for the spectral gap of common graphs (alternatively, the mixing time of a (lazy) random walk on these graphs). Asymptotic values are fine. Assume that every node has a sufficient number ...
2
votes
0answers
44 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
2
votes
0answers
38 views

Spectral radius of a time-varying matrix with strictly positive increment

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ where $t$ denotes the time. If $A(t)$ changes over time with each time a random element in $A(t)$ is being ...
2
votes
0answers
44 views

Fast Cholesky Factrorization for Tree Laplacians

Suppose $T_1$ and $T_2$ represent two Laplacian matrices of two spanning trees of $n$ vertices. Since the Cholesky factorization needs $O(n)$ time for each $T_i\ (i=1,2)$ due to the tree structure, ...
2
votes
0answers
162 views

a closed formula to enumerate the self avoiding walks of a graph

Let $G$ be a directed graph with $N$ nodes and weighted adjacency matrix $W $ defined by $$ W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & \...
2
votes
0answers
132 views

interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...
2
votes
0answers
66 views

How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seem to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...
2
votes
0answers
60 views

Possible Eigenvalues of Graph

How would one prove (or disprove) that there is no such graph $G$ with $\lambda$ as an eigenvalue? I tried setting up a system of equations to see if it's possible for $-\frac{1}{2}$ to be an ...
2
votes
0answers
100 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}$ ...
2
votes
0answers
416 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 ...
2
votes
0answers
53 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 $Va$...
2
votes
0answers
796 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 ...
1
vote
0answers
18 views

How to prove the following statement for a simple graph to be bipartite?

Let $G$ be a simple graph on finite number of vertices and $A$ be its adjacency matrix. Suppose, if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, then $-\lambda$ is also an eigenvalue of $A$...
1
vote
0answers
23 views

How to prove the determinant of resistance matrix $R$?

Let $G$ be a connected graph with $n$ vertices, $R$ be the resistance matrix of $G$, $\tau$ be the $n\times 1$vector with components $\tau_1,\tau_2,...\tau_n$,and $\tau_i=2-\sum_{j\thicksim i} r(i,j)$ ...
1
vote
0answers
22 views

Recommended overlapping community detection algorithms?

Looking for overlapping community detection algorithm with following properties: undirected unweighted graph potentially overlapping communities good scalability to 1M nodes good intuitive results ...
1
vote
0answers
40 views

Merging two nodes in a directed graph with transitions

Let's say I have $M=\begin{bmatrix}1&2&1\\ 4&2&0 \\ 1& 1& 1\end{bmatrix}$, a $3\times3$ matrix which is the transition matrix or adjacency matrix of a $3$-node graph. I would ...
1
vote
0answers
46 views

Matrix -tree theorem-How to understand the theorem

I am having trouble understanding Kirchhoff's Theorem. The statement I want to prove is that if $\lambda_1,\lambda_2,...,\lambda _{n-1}$ are non-zero eigen values of $L(G)$ then Number of ...
1
vote
0answers
54 views

On the eigenvalues of bipartite graph?

Definition Let $G=U\cup V$ is bipartite graph, where $U$ and $V$ are disjoint sets of size $p$ and $q$, respectively. The complete bipartite graph denoted by $K_{p,q}$ is bipartite graph where every ...
1
vote
0answers
25 views

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
1
vote
0answers
34 views

Spectral radius of perturbed bipartite graphs

I am looking into how perturbation(s) on a bipartite graph affect its spectrum (specifically its spectral radius or largest eigenvalue). Actually I'm not exactly looking into bipartite but the ...
1
vote
0answers
51 views

Semigroup of matrices and expander Cayley graphs

I am interested in proving or disproving that certain Cayley graphs are expander. Let $S$ be the multiplicative semigroup of matrices generated by $A = \left( \begin{array}{cc} a & b \\ 0 & ...
1
vote
0answers
29 views

Probability having a path of length less than a fixed number

A graph $G(V, E)$ is given. For a random pair of nodes $e_1, e_2 \in V$, what is the chance/probability of having a path of size less than $k$ (a fixed number) between $e_1$ and $e_2$ (let's assume ...
1
vote
0answers
81 views

Finding all eigenvalues of the adjacency matrix of a simple graph

I want to find all eigenvalues of the adjacency matrix of the following graph(Graph spectrum), where $G$ and $H$ are complete graphs with $n$ and $m$ vertices, respectively, for positive integers $n,m ...
1
vote
0answers
37 views

Graph having bounded degree

A graph is said to have bounded degree if there exists $N \in \mathbb{N}$ such that, for every $x \in V$, one has $\sum\limits_{y \in V} A_{x,y} \le N$. Show that, in this case, for any $f \in l^2(V)$,...
1
vote
0answers
38 views

A question about minimizing the $\lambda_{max}$ over a set of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ entry matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (if it helps you can assume that $(1)$ all the ...