Social graphs are not fast mixing. This used to be widely assumed but recent empirical measurements have refuted the assumption. [1] If I recall correctly, random walks tend to get stuck in cities and other highly-dense subgraphs.
Six degrees of separation refers to shortest paths, and fast mixing is decidedly _not_ the intuition behind it.
So what do you make of the papers such as SybilLimit[1] or SybilInfer[2] which rely on a fast-mixing assumption? They do seem to claim good empirical results on actual social graphs...
EDIT: Wow, I've read that paper you linked to. So they use the data-set from SNAP like Facebook A and Facebook B.
But, if I understand correctly, these data-sets were formed by combining "egonets", which means they took a set of people and a small ball around them, and put all those balls in the graph. That explains the horrendous eigenvalues.
No. None of the graphs they use are ego-nets. That would be methodologically ridiculous, as you point out.
In fact, the main problem with the paper is the opposite -- the Facebook graphs they use are regional networks borrowed from [1]. This means that Facebook's actual mixing time should be _dramatically higher_ than the times measured in the paper because of the tendency of random walks to get stuck in regional networks. I believe this is the reason their Facebook-A and Facebook-B mixing times are much lower than the others, such as LiveJournal.
Alvisi et al. have a couple of related papers specifically looking at the implications of our new understanding of social-graph random walks for sybil defenses. [2, 3]
Six degrees of separation refers to shortest paths, and fast mixing is decidedly _not_ the intuition behind it.
[1] http://syssec.kaist.ac.kr/~yongdaek/doc/imc2010.pdf