Certainly social media profits short term from these schemes... as long as they don't get out of control and threaten the entire business model. So the cynic in me suggests Facebook and the like aren't actually interested in eliminating the scams entirely but rather keeping them managed within certain parameters while appearing to be trying to do everything they can to shut them down.
If this were my project to investigate, I'd want a random sampling of, say, new account registrations from within the past month or three. A 100-1,000 profile sample would be sufficient to get a strong estimate of the mean, based on scoring of accounts based on some sort of activity profile.
Remember: what's most critical in data analysis isn't the size of the sample, but the selection of it. Facebook have direct access to their own data and could ensure that any such selected sample was in fact random. Further Monte-Carlo re-sampling of a larger sample (e.g., subsets of the 1,000 sample set) could show possible non-randomness.
Other identifiable parameters, especially clustering of registrations through proxies, would also be generally determinable.
Note that the decrease in uncertainty from increasing a sample size (and hence: analysis costs) 10x is only about 3.2 -- your standard deviation decreases with the square root of the sample size. For a normal distribution a sample of only 30 is generally considered sufficient for "large-sample" methods. Most national opionion and political surveys are based on samples of 300 people. The cost that's incurred comes from the fact that once you've selected your sample you make repeated contact attempts to reach all those identified for inclusion.
By contrast, self-selected surveys, and most particularly online surveys and popularity polls, are highly susceptible to sampling bias. Most often, they're not analysis tools but contact-selection or lead-generation tools. They may have limited utility in identifying issues of concern, but should not be relied on in ranking them absent further research.
The only thing I didn't catch was how they were to figure out which of the accounts in the sample were fake.
Fake accounts are almost certainly going to have characteristics which distinguish them from legitimate ones, and likely a quantitative, manual, or combined assessment might determine that. Points to consider:
⚫ Photo images. Search for duplicates or analyze for manipulation.
⚫ Correlation with other data sources. Real names, Social Security, marketing, and numerous databases exist which tend to point to more legitimate profiles.
⚫ Direct contact. Set up events, meet-ups, special purchase offers, etc., or otherwise try to elicit direct action. Even statistically differential response rates are useful.
⚫ Social graph. Real people _interact_ with other real people, and there's a web of trust or certification which can be imputed or determined.
⚫ Network profiles. Identifying large numbers of accounts with similar or suspicious profiles _and_ originating from the same or adjacent network addresses (CIDR/BGP block), or from known nonresidential space that's _not_ a generally-used proxy, would be a strong indicator. If proxy use continues to climb, that's going to be less useful (and I suspect this will be the case).
Tests along these or similar lines could be used to generate more general scoring algorithms for identifying suspect accounts.
Once you've done the manual assessments, deriving heuristics for broader estimates are also possible. The key is having training data of known classified accounts.