How to Hide Within a Social Network

Social networks like Facebook are no big deal for graph theory. A social network is, after all, itself a graph—a mathematical structure consisting of various objects (or nodes) connected by links (or edges) in various configurations with varying complexities. Graph theory was good at parsing networks like Facebook long before Facebook even existed.

A consequence of this is that it’s very hard to “hide” within a social network. We can completely anonymize our social network presence, but we’re always subject to the bare fact of existing in a network, which is connectivity to others. We may be able to hide our names, but we are quite unable to hide who we are with respect to the network. Put differently, we have a role within our networks that is defined by how we interact with them. In a network, we are who we know.

The transparency of these roles—or network-defined identities—may be less neccessary than it seems, however. In a paper published this week in Nature Human Behavior by Polish computer scientist Marcin Waniek and colleagues offers a defensive algorithm that can be used to hide central or important figures within a social network. As a demonstration, they showed how the technique, known as ROAM (for “remove one, add many”), could be used to easily cloak the role of 9/11 attack leader Mohamed Atta within his (real-life) terrorist network.

“Can individuals or groups disguise their standing in the network to escape detection?," Waniek and co. write. "This matters because, on the one hand, it assists the general public in protecting their privacy against intrusion from government and corporate interests, while on the other hand, it assists counter-terrorism units and law-enforcement agencies in understanding how criminals and terrorists could escape detection, especially given the increasing reliance of terrorists on social media survival strategies.”

The metric in question here is what's known as centrality. Essentially, it describes how well-connected a network member is (how many connections it has, or "degree"), how important each one of the member's connections are, and the distance it is from other important network nodes (how many node-to-node hops away they are). An implication of these metrics is that connections are more or less important based on the centrality of the other nodes they connect to. Like, if I have a billion Facebook friends but each one of those friends only has one or two friends, then I'm not actually very important in the network, despite the number of connections.

The ROAM algorithm has two components. The first is pretty simple. To hide a network node, we just have to remove its connections to other nodes. That does the trick, but it's not really hiding the importance of a network node, it's just making it less important. To do the hiding, we have to maintain as many connections to the network as possible. This is the second part of the algorithm, the "add many" part. We keep the hidden node connected to its network by rerouting the erased connections through other nodes. So, is A is connections with B and C, it can cut off B and then introduce B to C. B and C become connections, and the link from A to B is re-established.

So, we're methodically removing our close connections and adding new, less direct connections in their place. This sounds pretty simple, but when we get into IRL networks, the algorithm starts to get really, really complex fast. In fact, it becomes an NP-hard problem, which is basically means that it's practically uncomputable. Waniek and his group were able to speed things up by forcing the algorithm to consider only connectivity within the hidden node's graph neighborhood, or its closest connections. Hiding is then possible, "without requiring massive computational power nor expertise in sophisticated optimization techniques," they write.

As alluded to above, Waniek doesn't view this ability as a necessarily good thing. Hiding is good because privacy and evading persecution, of course, but we'd still like to be able to shake Attas-like figures from social networks. The authors conclude: "Our findings suggest that counter-terrorism units may benefit from developing tools that identify not only the individuals and groups whose ranking (according to any measure of choice) is high, but also those whose ranking increases suspiciously and unexpectedly after making just a few modifications to the network."