4
$\begingroup$

I need a simple upper bound on the $\lambda_1$ the largest Laplacian eigenvalue of $G$ (aka $L(G)$ matrix). $G$ is a connected weighted graph without any loop or multiple edges. I've search the literature and found some paper regarding this. For example:

$$ \lambda_1 \leq \max_{i~j} \left\{\lambda_1 (\sum_{k:k\sim i}w_{ik}) + \sum_{k:k\sim j}\lambda_1(w_{jk}) \right\} $$

which $w_{ij}$ is the weight between the node $i$ and $j$. Also it's been assumed that the laplacian eigenvalues are ordered as $\lambda_1 \geq \ldots \geq \lambda_n = 0$. The literature is focused on giving thigher bounds while I need more simpler ones. Tightness is a good point but second priority.

  • Weight in $G$ are all positive and between 0 and 1 i.e ($a_{ij} \in [0,1]$)
  • Being simpler in term of mathematical complexity and less dependency to various variables is far more important than tightness.
  • Simpler also means have less computational complexity to be implemented. For example $\lambda_1 \underset{?}{\leq} 2\Delta$ which $\Delta$ is the largest $G$'s degree is considered simple (let's suppose it's correct).
$\endgroup$
4
  • $\begingroup$ if you apply Gershgorin circle theorem to the Laplacian matrix, you find all eigenvalues are lying inside the disc $| \lambda - \Lambda| \le \Lambda$. $\endgroup$ Commented Sep 21, 2017 at 10:48
  • $\begingroup$ @achillehui, I checked it. It seems a general bound based on LA. But I don't think if it would be any simpler that the above in term of complexity. I've to first find the $R_i$ for each row of $L(G)$ then compute the Gershgorin disk around $a_{ii}$ i.e. $D(a_{ii}, R_i)$ and then find the maximum. However reading wikipeida I couldn't figure it out what $D(a_{ii}, R_i)$ means. Should I sum up all entries within the disc? or just consider the maximum member of disc? From the proof I deduce that I might be able to write $\lambda \leq |a_{ii}|+R_i$. $\endgroup$
    – PiTao
    Commented Sep 21, 2017 at 11:54
  • $\begingroup$ $D(a_{ii},R_i)$ is the disc centered at $a_{ii}$ ( the $i^{th}$ diagonal element = degree of vertex $v_{i}$ ) with radius $R_i$ (the sum of absolute values of off-diagonal elements of $i^{th}$ row, which again equals to the degree of vertex $v_i$) (assume all weights = 1). $\endgroup$ Commented Sep 21, 2017 at 12:33
  • $\begingroup$ @achillehui, seems promising. Please rewrite your comment as an answer to make it accepted. One simple bound is $tr(L)$, but this is tighter and not that complex. $\endgroup$
    – PiTao
    Commented Sep 22, 2017 at 19:17

2 Answers 2

7
$\begingroup$

Given a graph $G$ with vertices $v_1, \ldots, v_n$ and a set of weights $w_{ij} = w_{ji} \in [0,1]$ assigned to edges $v_i v_j$. The Laplacian matrix $L(G ; w)$ is defined by the formula:

$$L(G ; w)_{ij} = \begin{cases} a_i, & i = j\\ -w_{ij},& i \sim j\\ 0 & \text{ otherwise } \end{cases} \quad\text{ where }\quad a_i = \sum_{k : k\sim i} w_{ik} $$

Since $\sum\limits_{j=0}^n L(G;w)_{ij} = 0$ for each $i$, the row sum of $i^{th}$ row coincides with the diagonal element $a_i$. $$R_i \stackrel{def}{=} \sum_{j\ne i} \left|L(G;w)_{ij}\right| = \sum_{j : j \sim i} |-w_{ij}| = \sum_{j : j \sim i } w_{ij} = a_i$$

By Gershgorin circle theorem, the eigenvalues $\lambda_1 \ge \cdots \ge \lambda_n$ are located inside the union of a bunch of closed discs:

$$\lambda_1, \ldots,\lambda_n \in \bigcup_{i=1}^n \bar{B}( a_i, R_i ) = \bigcup_{i=1}^n \bar{B}( a_i, a_i )$$

Notice for any pair of non-negative numbers $r, s$, we have $\bar{B}( r, r ) \subset \bar{B}( s, s )$ whenever $r \le s$.
Above union is a single disc and $$\lambda_1, \ldots, \lambda_n \in \bar{B}( a_{max}, a_{max} ) \quad\text{ where }\quad a_{max} = \max(a_1,\ldots,a_i)$$

Since all $w_{ij} \in [0,1]$, we have $a_{max} \le \Delta(G)$, the maximum degree of $G$. This leads to $$\lambda_1, \ldots, \lambda_n \in \bar{B}(\Delta(G),\Delta(G))$$ As a result, the largest eigenvalue $\lambda_1$ is bounded from above by $2\Delta(G)$.

$\endgroup$
3
$\begingroup$

Another simple one is given by Anderson, Morley, Eigenvalues of the Laplacian of a graph:

$$ \lambda_1 \leq \max_{ij} \ d_i + d_j, $$

where $d_i = \sum_{k: k\sim i} w_{ik}$ is the weighted degree of node $i$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .