3 ms·

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

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 https://www.comp.nus.edu.sg/~yuhf/yuh-sybillimit.pdf [2] http://www.internetsociety.org/sites/default/files/dane.pdf 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.

randomwalker 12y ago
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...

randomwalker 12y ago

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