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...

[1] https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf

[2] http://www.internetsociety.org/sites/default/files/dane.pdf

-----

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.