2
$\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$ 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
    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$ 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
    Sep 22, 2017 at 19:17

2 Answers 2

4
$\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$
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.