0
votes
0answers
24 views

Tightest upper bound for $\sum_j g_{ij}$ of an adjacency matrix of a graph

If I have an adjacency matrix of a graph $G$ (i.e. $g_{ij}=1$ if $i$ and $j$ are connected and $g_{ij}=0$ if not. $g_{ii}=0$), is there any tighter upper bound on $\sum_{j} g_{ij}$ than just $n-1$ ...
0
votes
0answers
39 views

How to show a total order is product order

Besides the definition of product order, is there any other way to show that a total order on two sets can induce a product order? Because I want to solve the problem below: For two graphs ...
0
votes
1answer
27 views

Constructing an eigenvector for a certain matrix representing a graph with a perfect code

Let $A$ be a symmetric $(0,1)$-matrix whose row sum is $r.$ Suppose I have a $(0,1)$ vector $v$ such that $$Av = \vec{1} - v.$$ By taking the vector $$u = \vec{1} - (r+1)v$$ we see that $$Au = A ...
0
votes
0answers
35 views

Calculating Eigenvector Centrality & Betweenness Centrality formulas explained in simple terms

I'm currently working on a software application that has a function that analyses networks of people and the relationships between them. Two of the important variables we look at are Eigenvector ...
0
votes
0answers
26 views

The lower bound of Cheeger Inequality as the degree goes to infinity

Consider an undirected graph $G(V,E)$ with adjacency matrix $A$ and define the graph Laplacian as \begin{equation} L = D - A \end{equation} where $D$ is a diagonal matrix such that $D(i,i) = d_i$. ...
0
votes
1answer
56 views

Find eigenvalues from a given relation.

This is a simple problem of linear algebra. One without knowing graph theory may solve it. I am missing a small easy logic. Description: Let $G$ be a graph with $n$ vertices and $G^c$ is its ...
2
votes
0answers
47 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 ...
1
vote
1answer
40 views

Rank-one modification of graph Laplacian

Suppose I have a Laplacain matrix for a 3-node-path graph as follows $L=\left[\begin{array}{ccc} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{array}\right]$ Now, I want to ...
0
votes
1answer
45 views

Explicit expression of eigenvalue and eigenvector of a graph

Could any one tell me what kind of graph has the explicit expression of its eigenvalue and eigenvector? Thanks!
1
vote
1answer
140 views

Principal EigenVector of an Adjacency matrix of an undirected graph

For an undirected graph, since the adjacency matrix will be symmetric, can we draw any relations between the principal eigenvector and the degree of nodes in the graph. Also can we do the same with ...
0
votes
1answer
42 views

Can this famous theorem extended to the weighted undirected graphs?

There is well-known bound on the largest eigenvalue of graphs that says $$\sqrt{d_{max}}\leq \lambda_{max}$$. Is it also true for weighted graphs? (Where as usual, the degree of a vertex in a weighted ...
0
votes
1answer
21 views

Is there any weighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?

Is there any weighted or unweighted graph which smallest eigenvalue of its adjacency matrix is greater than 1?
0
votes
1answer
50 views

Are perfect graphs always invertible?

Is it always the case that perfect graph is invertible? Also, is it any meaningful relation between inverse of a perfect graph and itself? Thanks.
0
votes
1answer
74 views

0 eigenvalue of weighted laplacian

I consider (weighted) directed graph and eigenvalues of its laplacian matrix. If a graph contains rooted out-branching which is the subgraph possessing a node can approaching to any nodes in the ...
3
votes
0answers
60 views

Eigenvalues of weighted Laplacian

Let $L_{n \times n}$ be a Laplacian matrix of a directed graph, for example, $$ L = \begin{bmatrix} 2 & -1 & -1\\ 0 & 1 & -1\\ -1 & 0 &1 \end{bmatrix}. $$ Gersgorin disc ...
1
vote
1answer
112 views

Minimal spectral radius of a primitive matrix

Given the set of all primitive matrices of dimensions $m$ by $m$ that are non-negative and integer - which one is the matrix with the minimal spectral radius? Edit (according to the first comment): ...
1
vote
2answers
78 views

Upper bound on the difference between two elements of an eigenvector

Let $W$ be the non-negative, symmetric adjacency/affinity matrix for some connected graph. If $W_{ij}$ is large, then vertex $i$ and vertex $j$ have a heavily weighted edge between them. If $W_{ij} = ...
2
votes
0answers
111 views

network centrality: when does the most central node coincide for eigenvalue and degree centrality measures

I'm trying to understand when the most central node of a graph is the same when measured according to the degree- and eigenvalue-centrality measures. That is, if $\mathbf{x}$ is the principal ...
1
vote
0answers
27 views

Delocalization of eigenvectors in Expanding Graphs

Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest(or second-highest) eigenvalues are delocalized ? By delocalization I mean that every ...
1
vote
0answers
29 views

finding the decomposition of Laplacian matrix with position of zero elements unchanged

I'd like to know whether it's possible to find the decomposition of a Lapalacian matrix $A$ $B^TB = A$ where $B$ has the same dimension with $A$ and the position of zero elements in $B$ is the same ...
4
votes
1answer
162 views

What is the difference between first and second right eigenvectors of a row stochastic matrix and their meaning?

In an $n\times n$ non negative row stochastic matrix (rows sum up to 1). The entries of the stochastic matrix I have represent directed links between countries. Why is the first right eigenvector a ...
8
votes
1answer
287 views

Why does this matrix have 3 nonzero distinct eigenvalues

Consider the $n \times n$ matrix $$A=\left[ \begin{array}{cccc} 0 & 1 & ... & 1 \\ 1 & 0 & & 0 \\ \vdots & & \ddots & \\ 1 & 0 & & 0% ...
2
votes
1answer
510 views

Parameter for Katz centrality of a graph

I am teaching a course using M.E.J. Newman's Networks. It covers several measures of vertex centrality. One of them is the Katz centrality. Let $G$ be a graph and let $A$ be its adjacency matrix. ...
1
vote
0answers
150 views

Is there a simple interpretation of the eigenvectors of a graph (visualizable?)?

I want to understand eigenvectors obtain from graphs (adjacency matrices) in an analogous way as they are interpreted from principal component analysis of a set of images, which is easy:Eigenfaces ...
6
votes
1answer
122 views

Is Eigenvector/eigenvalues of a sub graph similar to the main graph?

In Gephi I visualized a graph to calculate the eigenvalues,then I choose a portion of graph (e.g 6 vertex with their edges) and delete all others. I calculate the eigenvalues again and noticed that I ...
2
votes
0answers
43 views

maxcut and the minimal eigenvalue

For an adjacency matrix $A$ that represent a graph $G=\langle V,E\rangle$, I need to show that the maxcut is bounded by: $$ \mathrm{maxcut} \leq \frac{1}{2}|E| - \frac{|V| \lambda_{\min}(A)}{4}, $$ ...
0
votes
1answer
59 views

Question related to a proof about the multiplicity of some eigenvalues

I have a question related to Lemma 4.2 from this pdf (which is, btw quite a nice exposition of Hoffman Singleton work on the classifications of Moore graphs of diameter 2 and 3.) We are given a $n ...
2
votes
1answer
96 views

Possible relation between spectra bounds of two matrices

A Laplacian matrix $L\in\mathbb{R}^{n\times n}$, is a symmetric matrix with entries, \begin{equation} l_{ij}=\begin{cases} 1=\sum_{i,~ i\neq j} w_{ij} &\mbox{if } i=j \\ -w_{ij} & ...
4
votes
1answer
165 views

Eigenvalues of a special block matrix associated with strongly connected graph

Definition Let $G=(V,E,A)$ be a strongly connected directed graph, where $V=\{1,2,...,n\}$ denotes the vertex set, $E$ is the edge set, and $A$ is the associated adjacent matrix with $0-1$ weighting, ...
7
votes
3answers
1k views

Significance of eigenvalue

When I represent a graph with a matrix and calculate its eigenvalues what does it signify? I mean, what will spectral analysis of a graph tell me?
22
votes
1answer
3k views

What do the eigenvectors of an adjacency matrix tell us?

The principal eigenvector of the adjacency matrix of a graph gives us some notion of vertex centrality. What do the second, third, etc. eigenvectors tell us? Motivation: A standard information ...
11
votes
5answers
2k views

Spectrum of adjacency matrix of complete graph

Fooling around in matlab, I did an eigenvalue decomposition of the adjacency matrix of $K_5$. ...
2
votes
0answers
193 views

Eigenvalues of regular graphs

Could someone give me a hint for exercise 2.iii of these lecture notes? The exercise asks to show that a $k$-regular undirected graph (without loops) whose adjacency matrix $A$ has eigenvalues ...
7
votes
1answer
371 views

Spielman's proof of graph connectivity

I use Spielman's lectures on course Spectral Graph Theory I have few question regarding Lecture 2. The Laplacian, especially Lemma 2.3.1 (Graph connectivity). Please, help me to make it a little bit ...
8
votes
1answer
177 views

Two formulas for the minimal eigenvalue of a graph

Hello again everybody, I'm reading Fan Chung's monograph Spectral Graph Theory. In it, she has two formulas for the minimal eigenvalue of a graph. She doesn't explain why they're equivalent, and I'm ...
12
votes
1answer
455 views

What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this ...
4
votes
2answers
246 views

Graphs with eigenvalues of large multiplicity

For a strongly regular graph, there are exactly 3 eigenvalues, all nonzero (I believe). One has multiplicity 1, which means the other two have pretty high multiplicities. There are tables that give ...
3
votes
1answer
786 views

Is there any relation between the principal eigenvector of the original matrix and its inverse?

This question pop'd up when I was studying graph. I am thinking about the relation between principal eigenvector of adjacency matrix $A$ and its inverse $A^{-1}$, do they have any relation?
0
votes
2answers
267 views

Why the eigenvectors of the Laplacian of a Ring graph are sinusoids?

The eigenvectors of the Laplacian of a Ring graph with $n$ vertices are: $x_k(u) = \sin(2\pi ku/n)$ and $y_k(u) = \cos(2\pi ku/n)$ for $1\leq k \leq n/2$. The explanation according to Spielman's ...
2
votes
1answer
170 views

Kinks in the eigenvalue spectrum of short range lattices

Take a periodic one-dimensional lattice of size $N$ with $2k$ nearest neighborers. That is, vertex $i$ is connected to $i+1,i+2,...,i+k$ and $i-1,i-2,...i-k$ (with the understanding that the indices ...
1
vote
1answer
243 views

eigen decomposition of an interesting matrix (general case)

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= b^{L},$ the set of all different sequences of length $L$ where each element of the sequence can be an integer in $\left \{ 0, 1, .., b-1 ...
4
votes
1answer
337 views

eigen decomposition of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
5
votes
2answers
521 views

Knowledge about Graph Spectral Theory and correlation between a graph Weighted Adjacency matrix and its eigenvalues

I know that this question is some sort of bridge between Informatics and Mathematics, not knowing the best place where to post this question, I opted for this place because of the type of answer I ...