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 oppo

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] [1] https://www.cs.ucsb.edu/~ravenben/publications/pdf/interaction-eurosys09.pdf https://www.cs.ucsb.edu/~ravenben/publications/pdf/interacti... [2] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi13SoK.pdf http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi13SoK.pd... [3] http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi14Communities.pdf http://www.cs.utexas.edu/users/lorenzo/papers/Alvisi14Commun...