Thank you for listening

Computer Science Level 3

NSA collects metadata for a large fraction of the cell phone calls placed in the United States. Upon inspection, analysts are allowed to make three hops from a targeted calling account. In other words, they're allowed to inspect the metadata for every contact that the targeted person has made, for every contact that those contacts have made, for every contact that those contacts have made, and finally, for all the contacts that those contacts have called, i.e. three "hops". One person in a community of 10,000 is targeted for having called a grandparent in Yemen.

In addition, there are two toll free hotlines, one for emergency assistance that is called by 214 unique community members, and another for information about various community events that is called by 673 unique community members. The full calling record for the community is listed here .

You are a journalist who has been given the calling record by a whistleblower inside NSA. You know that the targeting has been carried out but you don't know the phone number of the targeted individual. To get a sense of how many people fall under the dragnet when this one person is targeted, find the number of 2-hop connections for the following phone numbers, and report the average: 1 , 17, 793, 1200, 3402

Assumptions

Each line representing a call between two numbers. The two integers are the "phone numbers" of the two individuals involved in the call.

caller1 caller 2
1       2312
1       555
1       2794
1       3057
1       4032
1       4609
1       5707

The number of unique contacts for each caller has been generated according to the best fit to a real distribution published by Sprint corporation.

The answer is 5129.8.

1 solution

Josh Silverman Staff
Mar 6, 2015

We can conquer this problem with a modified depth first search. Whereas conventional DFS iteratively branches out from a root node until it reaches a terminal node, here we want to terminate after we're two hops away from the root node, i.e. we visit our neighbors, our neighbors, and our neighbor's neighbor's neighbor's.

Before we code our search, we need to import the phone calls and store all the direct calling partners (their 0-hop connections) of each user in a dictionary.

# import call records
calls = open('2015_march_calls.txt').readlines()[1:]
calls = [[x for x in _.strip().split()] for _ in calls]

# make dict with call partners for each community member
call_dict = {}
for k, v in calls:
    call_dict.setdefault(k, []).append(v)
    call_dict.setdefault(v, []).append(k)

In short, we trim the return character from each line of the data, and split the lines on whitespace. Then, we append the first phone number to the 0-hop entry of the second phone number and vice versa. We use the setdefault method to avoid initializing the dictionary separate from updating it.

Now, we wish to visit the caller's neighbors, accumulate them into a list of "reached" people, then visit the neighbors of every caller in our "reached" list, so long as they're not already in our list, and add them to our list. Finally, we want to cut this process off once we've made added all the 2-hop connections of the caller being targeted.

Consider the following implementation:

def dfs_hop(G, v, hops_left, reached=None):   
    # initialize our 'reached' list
    if reached is None:
        reached = []
    # append the node under consideration to the `reached` list
    reached.append(v)
    # go through every vertex in the 0-hop neighbor
    # list of current node
    for vertex in G[v]:
    # if the vertex has not been reached, and we have hops left,
    # call depth-first-search on the vertex, and decrement the 
    # number of hops_left by 1
        if vertex not in reached and hops_left >= 0:
            dfs_hop(G, vertex, hops_left - 1, reached)
    # return the list of reached vertices, unique by construction
    return reached

Calling this routine on the sample phone numbers, [1, 17, 793, 1200, 3402] , i.e.

1	`dfs_hop(call_dict, v, 2)`

we find [4644, 5928, 5541, 5365, 4171] 2-hop neighbors for those phone numbers, which puts the sample mean around 5,000.

The reason the expanse of the hopping gets so large so quickly is due to the structure of calling networks. Most nodes are very closely connected to dense sub-networks of other callers.

Note that with just 2-hops, subpoenaing the records of a single caller intrudes on the privacy of half this community. As NSA is allowed to inspect 3-hops, if in the population of the United States, the average caller has 40 direct contacts, this potentially provides access to the calling records of $40^4 \approx 2.5\times10^6$ 3-hop neighbors per targeted individual.

Thank you for listening

The answer is 5129.8.

1 solution

0 pending reports