How should one define expansion for irregular graphs?

Question

This question is related to a previous question: Does it make sense to talk about expansion in irregular graphs?

A family of expanders can be defined as a sequence of graphs whose spectral gap is bounded from below by a constant. If you want your graphs to be $d$-regular, then the largest spectral gap that you can achieve is $d - 2\sqrt{d-1}$ (this is the Alon-Boppana theorem). These are Ramanujan graphs, for which there are several constructions.

However, many real-world networks are far from regular. Indeed, their degrees tend to obey a power law, so that there are vertices of quite high degree ($n^{\alpha}$ for some $\alpha>0$), even though the graph may have a linear number of edges. If one wants to know whether these graphs are good expanders, it would be nice to compare them to the best expanders with such a degree sequence.

A motivating example for having a new definition for irregular expanders is the "star" graph, in which one vertex is connected to all of the others, and there are no additional edges. Here, although the number of edges is only $n-1$, the spectral gap is enormous - it is $\sqrt{n-1}$. So it looks like the spectral gap can be much larger when the graph is allowed to be non-regular.

So my question is: Is anything known about the maximal expansion among graphs with a given degree sequence?

Answer 1

The answer rather depends what you want. It looks to me like you're interested in `two-sided' expansion, that is, you want to know that the graph in some sense looks random, as opposed to 'one-sided' expansion where you are simply interested in having enough edges everywhere (the '-sided' refers to putting lower, or both upper and lower, bounds on numbers of edges in cuts, when you're following that definition).

One option is simply to look at not the adjacency matrix, but a weighted version. The result is worked out in http://www.tau.ac.il/~nogaa/PDFS/jquasi7.pdf . (I guess you know this, given your location..). The effect of weighting is more or less to force regularity, in the case of the star you would effectively replace the star with a balanced complete bipartite graph.

Alternatively, if you really want to know that the adjacency matrix is in some sense close to a random, or random bipartite, matrix (even though you allow some exceptionally high degree vertices) then the answer is that eigenvalue characterisations and cut-norm type characterisations are simply different in this setting. A single vertex adjacent to everything doesn't affect cut norms much once you have superlinearly many edges, but it does show up in the spectrum. I think in this regime you do not really want to know about the spectrum; what does it tell you? (It's not much related to the simple random walk when degrees are far from regular)