# Tagged Questions

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

11 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 ...
17 views

### Eigenvalues of the sum of Laplacian matrix and the all ones matrix

Given an undirected graph and its Laplacian is $L$. I need to find the eigenvalues of the sum: $L + \mathbf{11^T}$ (where $\mathbf{1}$ is the all-ones vector, which means that $\mathbf{11^T}$ is a ...
31 views

27 views

### Do you need to know a lot of (regular?) graph theory to get into spectral graph theory?

Do you need to know a lot of (regular?) graph theory to get into spectral graph theory? What are the prerequisites?
22 views

### Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
26 views

### Number of connected components in a graph.

$\newcommand{\R}{\mathbb R}$ Let $G=(V,E,W:E\mapsto\R)$ be an undirected weighted graph with node set $V=(v_1,\dots,v_n)$, edge set $E\subseteq V\times V$ and weights over the edges $W_{ij}$. The ...
41 views

### Ball in a $k$-regular tree

Let $X$ be a finite k-regular graph. Fix a vertex $x_0$ and, for $r <\frac{g(X)}{2}$, consider the ball centered at $x_0$ and of radius r in X. Show that it is isometric to any ball with the same ...
24 views

### Creating a Hermitian matrix that is also positive semi-definite

Given some measurements on empirical data (in the form of a multigraph with two weighted edges between every pair of vertices), I would like to place the measurements in a Hermitian matrix that also ...
56 views

### eigenvalues of cycle graph and its complement graph

I am trying to find the eigenvalue of cycle graph and its complement. How to simplify.Suppose $\omega^{1}+\omega^{n-1}=2\cos (2\pi/n)$, then, $\omega^{\frac{n-1}{2}}+\omega^{\frac{n+1}{2}}=\ ?$ Is ...
37 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 ...
5 views

### What Laplacian should we use for spectral clustering?

The second eigenvector of the normalized Laplacian $I-D^{-1}W$ or the symmetric normalized Laplacian $I-D^{-1/2}WD^{-1/2}$ can be used to approximate a minmizer of the normalized cut problem. Which ...
97 views

### Bounding 2nd-smallest eigenvalue of the Laplacian of the binary tree

I am reading on my own the notes of this lecture series from 2012: http://www.cs.yale.edu/homes/spielman/561/2012/lect04-12.pdf. In section 4.7.2 (page 8) it's mentioned that we can prove a lower ...
29 views

### Optimal partitioning of a planar graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
20 views

### Spectrum of the circulant graph

How to prove that the eigenvalue of cycle $C_n=\lambda_r=2 cos(2\pi r/n)$?where $r=0,1,...n-1$, which is proved for the circulant matrix with first row $(v_0=0,v_1=1,v_2=0, ...v_{n-2}=0,v_{n-1}=1)$, ...
59 views

### Eigenvectors of graph laplacian

Let $L$ be the laplacian matrix of a graph $G$, i.e. $L = D - A$, where $D$ is the degree matrix, and $A$ the adjacency matrix. Let $v_i$ be an eigenvector of $L$. Let $x,y$ be two vertices of the ...
22 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 ...
72 views

55 views

### Confusion between spectral radius of matrix and spectral radius of the operator

The adjacency matrix $A(G)$ of an infinite undirected graph $G$ is considered as a bounded self-adjoint linear operator $A$ on the Hilbert Space $l^2(G)$ (last section of ...
72 views

### Characteristic polynomial of a block matrix

Let $A$ be an $n\times n$ symmetric matrix whose diagonal are is covered by zero blocks (square, but not of a fixed size) and all other entries are $1$ (one). How can I find its Characteristic ...
38 views

### Highest eigenvalues/vectors of graph laplacian

In page 8 of the paper Laplacian Eigenmaps for dimensionality reduction and Data Representation it reads: Standard methods show that the solution is provided by the matrix of eigenvectors ...
17 views

### Size of intersection of balls on non-ameanable graphs

Let $G$ be a vertex-transitive non-ameanable graph and let $B(x,n)$ be the ball of radius $n$ centered on the vertex $x$. I am interested in estimates on the cardinality of the following set, ...
19 views

### How to perturb an adjacecny matrix in order to have the highest increase in spectral radius?

Let's suppose I have a generic directed graph $G$ and it's adjacency matrix $A$. I can add an arc wherever I want in the graph. (i.e. perturb the matrix A changing a single 0 into a 1). Where should ...
35 views

I was going through the lectures of Graph Partitioning and Expanders - Stanford Online. In lecture 1, near the end of page 5, I came across this inequality for regular graphs: $$\phi(S) \leq h(S) \leq ... 0answers 14 views ### The image of a a vector in the edge space when multiplied by it's incidence matrix. Consider a graph G=(V,E) and it's incidence matrix M. Let \textbf{x} be the characteristic vector for a standard basis vector in \mathcal{E} (a vector corresponding to the one element edges ... 0answers 37 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 ... 0answers 4 views ### PageRank metaphor as suspended unlimited capacity pools What do you think about my metaphor of the centrality measure PageRank? PageRank is an algorithm for evaluating node centrality: it's a function f:G \to R^n where n is the number of nodes in the ... 0answers 27 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 ... 1answer 28 views ### Construction of graph Laplacian I have a weighted undirected graph, and all the edge-weights are non-negative. According to the definition of the graph Laplacian matrix, L=D-W. In literature, I found that D is known as degree ... 0answers 45 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 ... 1answer 40 views ### spectrum of complete p-partite graphs I need to determine the spectrum of the complete p-partite graph ( in which each partite set has m vertices) using the complement. How can i show this? I know the spectrum of the adjacency matrix of ... 0answers 49 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$$ ...
$A,B$ are 2 adjacency matrices of $d$ Regular graphs(not Strongly Regular graphs). I would like to know- 1.Results/ information related to Eigen values of A,B. There is a formula for ...