Mark and Recapture Estimation on Twitter

This is a maths post -- some technical notes on work we did for the Arab Social Media Report produced by The Dubai School of Govenment. Non-mathematicians should see that study instead. If you proceed, you have been warned: there will be equations.

There were several challenges in using the Twitter API to meet the study's research goal. Here I look at population estimation: how to measure the population size by sampling.

Capture/Recapture and the Lincoln-Petersen Formula

Twitter themselves do not provide data on the geographical distribution of their userbase, and they're a little opaque about their true user population with dead accounts bolstering the numbers. What little official data there is, focuses on those countries with the highest per capita Twitter penetration. In other words, announcements have generally ignored the Arabian peninsula.

At the highest level, estimating population size is a simple two step process due to a clever idea from ecological surveying called mark-recapture technique (also known as capture/recapture).

Capture/recapture looks at the overlap between different samples in order to estimate the total size of a population. The degree of overlap tells you how complete your samples were, and hence the size of the population.

We used a sampling process to collect a couple of samples -- sets of users for each country. The samples were obtained by the simple process of looking for people tweeting. In principle, this is all that is required in order to apply the standard Lincoln-Petersen formula for mark-recapture population estimation.[1]

Not So Fast Mr Bond

However, the Lincoln-Petersen formula relies on several assumptions:

That the population does not significantly change between samples i.e. there aren't many people joining or leaving Twitter across the sampling period.

That the sampling procedure does not have an effect on individual behaviours (in ecological sampling the act of capturing an animal might sometimes kill it).

That all individuals in the population are equally likely to be captured.

Assumption 1 is a reasonable approximation – although Twitter is growing, the change in the Twitter population over a short period will be relatively small. Assumption 2 is also valid as the sampling process is completely passive and cannot affect individual behaviours.

However assumption 3 clearly does not hold for a message-based sampling technique. Different twitter users exhibit very different patterns of activity: some post many times a day, others once a month. Such a population is said to be heterogenous. We have attempted to correct for this as follows.

Correcting for heterogeneity

The chances of being picked up in a sweep are linked to activity. More frequent twitter users are more likely to turn up in both sweeps. Activity levels are far from uniform (as confirmed here and in various studies, e.g. [2]). This has the effect that the standard Lincoln-Petersen formula will very significantly underestimate the population size.

We correct for this by assigning a prior distribution for the likelihood of being seen. This allows a corrected formula to be calculated. This correction uses extra information about users supplied by Twitter, as described below.

Note: given longer histories with more sweeps, there are other models which can be fitted for capture behaviour. See [3] for an overview of techniques. With two sweeps, it is necessary to use a prior distribution to model the heterogenity effect. Without an informative prior, the maximum likelihood estimator for population size with heterogenity is only the number of individuals seen.

We assume that an individual's capture probability is linearly correlated with their average post frequency, which we can calculate from their Twitter profile.

Let s₁, s₂ be the number of individuals captured in sweep 1 and 2 respectively, let m₂ be the number of marked individuals found in sweep 2 (the overlap) and let N be the total population (which is what we wish to estimate).

We divide the population into those caught in sweep 1, and those who were not captured in sweep 1. Let M be the individuals captured and marked in sweep1, and U the individuals not captured in sweep 1. These sub-populations have different probabilities of being captured in sweep 2, which we denote p_M and p_U respectively. p_M is the average posterior probability of capture given a previous capture, and p_U is the average posterior probability of capture given no previous capture.

Given p_U, we could estimate |U| = (s₂ - m₂)/p_U and hence N = |U| + s₁.

But we don't have p_U -- what we have is an estimator for p_M = m₂/s₁

So we have more work to do.

Let F_M, F_U be the tweet frequency distributions for M and U, i.e. F_M has the probability function P(frequency|M). We measure F_M directly, creating a histogram. We can then estimate the prior distribution for F since P(frequency=f |M) is proportional to f.Prior(frequency=f) by the link with tweet frequency. This estimate is unstable around low frequencies, so we set a minimum activity threshold of one tweet per fortnight. We use the prior F as an estimator for F_U. This is reasonable, but does have some bias towards higher frequencies, which will result in the final correction being smaller than it should be, and hence our result is below the ideal estimate.

By the link with tweet frequency described above, we have p_M = k.mean(F_M) and p_U = k.mean(F_U) for some value k.

And without further ado, this gives N = s₁ + (s₂ – m₂).(s₁/m₂).(mean(F_M)/mean(F_U))

Simples.*

Note that the Lincoln-Petersen formula is a special case of this equation, where p_M = p_U. Which is to say, if you put the homogenity assumption back in, you'll get Lincoln-Petersen out.

*The handful of lines shown here took some work, with help from the good Dr Halliwell, and some computational modelling work to double check the reasonableness of it all.

Correcting for the unlocatable population

A significant number of users choose to withhold their location, or provide non-geographical locations e.g. "wherever there is dancing". Because a country-based sampling process has to discard unresolved locations, without correction we would underestimate the population size.

In order to correct for this, we estimated the size of this effect for each country surveyed. We searched for tweets with the location-identifying phrases, "I'm in X" and "here in X" for both the country name and large cities within that country. We performed these searches in both English and Arabic.

These searches pick up a mixture of:

Identifiable tourists and visitors (identified by the fact that they give their location as a different country).

Identifiable local people (identified by their location).

People who do not give out their proper location.

Let's assume that: (a) the people who use such phrases do not have any bias for or against putting their proper location into their user description, and (b) the people who withhold their location are visitors or locals in proportion to the ratio of identified visitors and identified locals.

Now we can estimate the proportion of locals who withhold their location.

Putting these things together allowed us to go beyond sample measurements to estimate the underlying populations.

References

Seber, G.A.F., The Estimation of Animal Abundance and Related Parameters. Caldwel,New Jersey: Blackburn Press.

http://blogs.hbr.org/cs/2009/06/new_twitter_research_men_follo.html (10% of users create 90% of volume)

Sophie Baillargeon Louis-Paul Rivest, Rcapture: Loglinear Models for Capture-Recapture in R

37 Signals: Better writing than software

I just read "Rework" by 37Signals. This is a quick enjoyable read. The book is 100 odd pieces of advice, each presented as ~1.5 pages of text with a cartoon. The writing is clear and to the point. The advice is a mixture of:

• Common sense.
• Uncommon sense: Things which go against conventional wisdom, but are good advice when you think about it.
• Over-generalisations: Sadly a lot of the advice only works if you're 37 signals. For example "write about your work and you can build an audience" is great if you are brilliant marketers who can dedicate time to creating a high-profile blog that gets a lot of traffic and reputation. If you can't - and that will be most of us then - this isn't going to repay the effort you put in.

The strangest thing is that reading their book, you'd think 37 Signals produce simple-yet-beautiful software. But I use their software, and it's lousy. Basecamp does not do one thing well. It does a few things, all of them rather poorly. I much prefer other group-work tools - mostly the ones you don't think of as tools anymore, such as email, shared calendars, and version-control - which are simpler, better at their job, and free. The best bit about Basecamp is the email integration, which makes it's messaging only marginally worse than plain old email.

If you're asking "why do I use it then?", it's because other people sometimes pay me to do so. I'm opinionated but I'm not pig-headed.

It occurs to me that 37 Signals are not selling Basecamp. That appears to be their business, but what they're really selling is a philosophy and a story. It's a story about who your organisation is and how it works. The software is merchandising. People like the story so they buy the merchandise.

Is that a criticism? I'm not sure. Most business is engaged in buying and selling stories. The stories may be about who we are, better connection to your friends, higher productivity, ROI... The stories come with some product attached - software, a car, etc. The stories may be true or false. But we buy the story first. Sometimes the story is strong enough (or we buy into it enough) that even if the product stinks, we keep believing in the story.

An example of really powerful stories: My wife and I are looking for a new house, and thinking "this is where the kids will play". The people selling houses are thinking "this is the home we bought together as newly weds" (or similar). No wonder house prices get inflated.

Conversely, pensions are, for the under 30s, a good product with a lousy story. Everyone knows they will need a pension. But the story "you need to set aside money because you're going to grow old and infirm" -- it's not a story people want to buy. So many people don't, until some life-changing event (having kids or something happens to their parents) puts the fear into them.

Even the best product needs a good story if it is to succeed.