5 ms·
> how hard can it be to spot these kind of non-organic actors in the social graph? Very hard. Graph theory contains some of the hardest problems in computer sc
by allenz 9y ago
> how hard can it be to spot these kind of non-organic actors in the social graph?
Very hard. Graph theory contains some of the hardest problems in computer science. For example, maybe you want to find the largest group of nodes that are all connected to each other. We don't know how to do this. If the largest clique has n nodes, our best approximation methods can find log(n) of them, which is pretty useless.[1]
Spam detection at FB scale is difficult because with so many users many actual accounts will appear unusual in some way, and of course all data can be faked. Google and Yahoo have worked on this for years, yet spammers can still evade their systems: [2]
> there's probably little distinction between FB's valued corporate customers and advertisers and these 'information operations'
The distinction is pretty clear. FB knows exactly who its advertisers are since they pay FB money to promote their posts. It's true that fake news increases engagement, but FB is tackling an easier problem--identifying active operations making millions of fake accounts.
[1] https://en.wikipedia.org/wiki/Clique_problem https://en.wikipedia.org/wiki/Clique_problem
[2] https://news.ycombinator.com/item?id=13802227 https://news.ycombinator.com/item?id=13802227
- fmap 9y agoI agree with you in principle, but I think the problem is more one of scale than of complexity theory. Sure the clique problem is hard to approximate in arbitrary graphs, but the graphs that appear in social networks are far from arbitrary. And indeed, in such scale free networks the clique problem becomes quasi polynomial or polynomial (http://link.springer.com/chapter/10.1007/978-3-642-35261-4_68 http://link.springer.com/chapter/10.1007/978-3-642-35261-4_6...). Approximate solutions are also much easier to find. On the other hand, the sheer size of Facebook's social graph means that anything other than streaming algorithms or local search is pretty much intractable. That makes solving these kinds of problems into interesting engineering challenges.
- allenz 9y agoGood points. Pedantic aside: scale-free is a dangerous assumption for two reasons. First, there may be fairly large deviations from power law in real data, and any such deviation renders the problem intractable. Second, botnets can modify local and possibly global properties in adversarial ways, so as to hide in or make large areas that are not scale-free.
- thr0waway1239 9y agoActually, the graph theorists at FB solved the problem in a few days, but various government agencies insisted that the code should not unearth anything potentially negative about their operations. Its now been years, and they are still trying to get it to work within that constraint.