Tagged Questions

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

3 views

Interpretation of Left Dominant Eigenvector centrality on empty graph

What is the correct interpretation of the centrality measure "left dominant eigenvector" in the case when the matrix is empty? We know that the eigenvalues are all 1, and the eigenvectors are the ...
59 views
+50

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 ...
19 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 ...
187 views

Consider a real symmetric matrix. Such a matrix can be considered as an adjacency matrix of a graph, and in fact may be identified with the graph itself. Now consider the equivalence class of the ...
7 views

Spectral properties of certain weighted adjacency matrices

I would like to know if anyone has ever studied the spectral properties of the weighted adjacency matrix of a digraph where if $w(u,v)$ is the weight of edge $(u,v)$, then $w(v,u) = w(u,v)^{-1}$. ...
21 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 ...
35 views

101 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 ...
39 views

Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)? To make the question as self-contained as ...
33 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 ...
42 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 ...
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
28 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 ...
58 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 ...
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 ...
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 ...
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 ...
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)$, ...
61 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 ...
73 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 ...
39 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, ...
35 views

Relation between edge expansion of graph and sparsity

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 ...
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 ...
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 ...
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 ...
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 ...
29 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 ...