Syllabus Lesson 131 of 156 · Tracking the person, not the device
Tracking the person, not the device

Identity graphs

Why it matters A loyalty card knows your email. A shopping app knows your phone. A delivery firm knows your address. None of them alone is a full picture, but a data broker that buys all three can join them into one record about you. Building a tiny version yourself shows exactly which shared detail does the joining, and so which detail to stop sharing.

A web of string

Imagine a pinboard with index cards, one per record. Whenever two cards share an email address, a phone number, a device ID or a home address, you tie a piece of string between them. When you are done, each tangle of cards joined by string, however long the chain, is one person.

Data broker: a company that collects, buys and sells information about people, usually people who have never heard of it.

Identity graph: a broker's map that links many records (emails, phones, devices, addresses) to one person. In maths a graph is simply dots (here, records) joined by lines (shared details).

The chain is the clever part. Card A shares an email with card B. Card B shares a phone with card C. A and C have nothing in common, yet they end up in the same tangle. This is how a newsletter sign-up can be joined to a game on your phone without either one ever seeing the other's data.

The practice records

broker_records() returns made-up records from several sources:

{"id": "r014", "source": "survey", "name": "Sam Smith",
 "email": "  SAM.SMITH88@MAIL.EXAMPLE ", "phone": "+44 7700 910283",
 "device": None, "address": None}

Any detail can be missing (None). Emails arrive with odd spaces and capitals, so they must be normalised first: trimmed with .strip() and lower-cased. Phone numbers should keep only their digits, so "+44 7700 910283" and "447700910283" match. ch.isdigit() tells you whether a character is a digit.

Following the string

Build it in three steps:

  1. Index: a dict from each (field, value) pair to the record ids that have it. Two ids under the same key share that detail.
  2. Neighbours: for each record id, the set of ids it shares anything with.
  3. Walk: start at a record nobody has visited, keep a to_visit list, and repeatedly take an id off it, mark it seen, and add its neighbours. Everything you reach is one group.
to_visit = ["r001"]
while to_visit:              # keep going while the list is not empty
    current = to_visit.pop() # take the last id off the list
    ...
In other languages

Brokers and analysts often use a structure called union-find instead of walking. In JavaScript:

const parent = {};
// every record starts as its own group: parent[id] = id
for (const r of records) parent[r.id] = r.id;
const find = x => (parent[x] === x ? x : (parent[x] = find(parent[x])));
const union = (a, b) => { parent[find(a)] = find(b); };
// for each shared (field, value): union(firstIdWithIt, thisId)

And the same in Go:

func find(parent map[string]string, x string) string {
    for parent[x] != x {
        x = parent[x]
    }
    return x
}

A tempting mistake

The script at the bottom also joins on name. Watch the number of people drop: two different people called "Sam Smith" get merged into one. Real brokers make this kind of error too, which is one reason their files about people are often wrong. A wrong record can still be sold and acted on.

The defence

The joins happen through the details you repeat. Use a different email alias for each shop or newsletter (many mail services offer these), give a phone number only when it is truly needed, and avoid "log in with" buttons that hand one account to many sites. You cannot stop a broker drawing string, but you can give it fewer matching cards.

Recap

  • An identity graph joins records that share any detail, and chains of shared details join records that share nothing directly.
  • Normalising (trimming, lower-casing, keeping phone digits) is what makes messy data match.
  • Weak keys such as names merge different people, so broker files contain errors.
  • Fewer repeated details (aliases, no phone, separate logins) means fewer joins.
Your turn

Write two functions. normalise(field, value) returns None for None; otherwise it strips spaces and lower-cases the value, keeps only the digits when field is "phone", and returns None if nothing is left. link_records(records, keys) returns a list of sets of record ids, one set per person: two records are in the same set when they share a normalised value for any field in keys, directly or through a chain of other records. Every record id appears in exactly one set.

Spotted a problem in this lesson? Report it

Code · runs in your browser
Output

        

      

      
      

        Back