# Are social networks typically good expanders?

I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility of these graphs. One basic question is: Are these graphs typically good expander graphs?

Has anyone checked, say, the facebook graph's spectral gap? Or the spectral gap of other large real-world networks? I am hoping that someone can point me in the right direction to learn about this topic.

• Since each step in an iterative eigenvalue algorithm for $n$ by $n$ matrices typically requires $cn^2$ steps, the graphs for which we can decide easily whether they are expanders are much smaller than the web scale graphs you ask about. Even $n=10^5$ is a challenge. However, social networks are quite special. Essentially you are asking whether it is possible to approximate an eigenvalue in something like quasilinear time and quasilinear space in $n$, if the input graph is sparse and its vertex degrees follow a power law. Nov 20 '16 at 11:39
• Huh, I've been focused on theory for too long. It never even crossed my mind that the facebook graph might be so large that it might be infeasible to compute its spectral gap. Nov 21 '16 at 7:06