5
$\begingroup$

In the literature, it is sometimes indicated that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust against link/node removals. However, these statements are usually NOT accompanied with references.

I am looking for some explanation on why is this so? Or pointers to some work that investigate/explain this.

I wonder if this statement is simply the result of difference between link density? I doubt its so simplistic. Is there any study on network robustness comparing networks with same link density but different largest eigenvalues (or spectral radius)?

$\endgroup$
2
  • $\begingroup$ Do you definitely mean large eigenvalues? A small second eigenvalue guarantees quasirandomness and so, for example, many short paths between any pair of vertices. $\endgroup$
    – Ben Barber
    Jun 12, 2015 at 23:01
  • 2
    $\begingroup$ I give you an example. One paper stated this (without reference): "The largest eigenvalues are particularly important. Most networks with high values for these largest eigenvalues have small diameter, expand faster and more robust.". They use the original (non-normalized version) of Laplacian matrix. $\endgroup$
    – Val K
    Jun 14, 2015 at 9:54

3 Answers 3

5
$\begingroup$

I am not sure, because no specific reference was given, but I suspect this is referring to the well known fact that the isoperimetric constant can be bounded below by eigenvalues, as in Proposition 4.2.5 of Lubotzky's book Discrete Groups, Expanding Graphs and Invariant Measures. If the isoperimetric constant is $c$, then a set of $m$ nodes cannot be isolated by removing less than $cm$ links (unless the set has more than half of the vertices in the entire graph).

$\endgroup$
1
  • $\begingroup$ Thanks Dave. So, it seems that it is not really related to link density (as I suspected). I am not familiar with isoperimetric constant. Will need to do some reading now. Do you have any pointers / past work using this constant for designing communication networks? $\endgroup$
    – Val K
    Jun 14, 2015 at 9:44
4
$\begingroup$

As @Morris answered the reason is behind in connectivity and rapid connection which is compacted in isoperimetric parameter of graphs. The isoperimetric parameter has bounded by eigenvalues in some nice inequality. Also, you can see that Cayley graphs are good objects for designing network, which one of main reason is its connectivity, since an $r$-regular connected cayley graph has connectivity $r$. But for study much more I suggest these two books which are very good in related to your question:

"Graph Spectra for Complex Networks" by Piet van Mieghem

"Expander Families and Cayley Graphs: A Beginner's Guide" by Mike Krebs and Anthony Shaheen.

$\endgroup$
1
  • $\begingroup$ Thanks Shahrooz for the pointers. I will dig them out and study a little further. $\endgroup$
    – Val K
    Jun 14, 2015 at 9:42
4
$\begingroup$

The following papers might contain relevant information to your question:

Robustness of networks against viruses: the role of the spectral radius, by A. Jamakovic, R.E. Kooij, P. Van Mieghem, E.R. van Dam

https://www.nas.ewi.tudelft.nl/people/Rob/telecom/jamakovic.pdf

Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint, by Yang Wang, Deepayan Chakrabarti, Chenxi Wang and Christos Faloutsos

http://www-2.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/PUBLICATIONS/srds03-virus.pdf

$\endgroup$
4
  • $\begingroup$ Thanks Sebi. I am aware of these work but in these, it is the smaller values of largest eigenvalues making the network more robust (against epidemic spreading). However, I'm looking into robustness against node/link removals. So it is more about the structure of the network topologies rather than the information flows/paths... if you get what I mean. $\endgroup$
    – Val K
    Jun 15, 2015 at 10:13
  • 1
    $\begingroup$ When adding/removing node/links, there is work estimating the change in the spectral radius: C. Maas, Perturbation results for the adjacency spectrum of a graph, Z. angew Math. Mech., 67 (1987), 428–430; Li, C., H. Wang and P. Van Mieghem, 2012, Bounds for the spectral radius of a graph when nodes are removed, Linear Algebra and its Applications, vol. 437, pp. 319-323; $\endgroup$ Jun 15, 2015 at 11:41
  • $\begingroup$ Unfortunately, I couldn't get my hand on this paper (the one by C. Maas). Had scoured the Internet and my library... can you point me to any where I can download this? Thank you. $\endgroup$
    – Val K
    Jun 15, 2015 at 13:05
  • 2
    $\begingroup$ "Eigenspaces of Graphs" by Cvetkovic, Rowlinson and Simic contains a description of the results of Maas (Section 6.4). I think Maas results were generalized by Zhou Bo, The changes in indices of modified graphs, Linear Algebra Appl. 356 (2002), 95–101 (see Theorem 1). $\endgroup$ Jun 15, 2015 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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