Hiding Within a Social Network
Source: https://motherboard.vice.com/en_us/article/yw5yw7/how-to-hide-within-a-social-network
As we have seen through our understanding of graph theory, it’s very hard to “hide” within a network. Using the example of social networks like Facebook, we may be able to anonymize our social network presence, but we are unable to hide who we are in respect to the network. In a network, our only role is defined by who we know.
A paper published by Polish computer scientist Marcin Waniek and colleagues called Human Nature Behavior offers a defensive algorithm that can be used to hide central or important figures within a social network. The metric in question here is the concept of centrality, which 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.
To demonstrate, they showed how the technique, known as ROAM (for “remove one, add many”) could be use to easily cloak the role of 9/11 attack leader Mohamed Atta within his (real-life) terrorist network. The ROAM algorithm has two components. The first hides a network node by removing 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, if A has 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.
Simply put, we are removing our close connections and adding, new less direct connections in their place. In real life networks, however, the algorithm starts to get really, really complex fast, so much so that it becomes practically uncomputable. Waniek and his group were able to force 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.
The articles relates to any material about graph theory, more specifically to the content related to connected components. It is interesting to see the parallels between the ROAM algorithm and how we have been determining largest connected components and the variations that result when a link or node is deleted or added. What I found the most interesting was the inability of computing ROAM with real life networks. I lack sufficient knowledge about graph theory to suggest a credible, expansive reason but it essentially establishes that real life networks are incredibly intricate, which is great for tracking and searching reasons but makes privacy or a desire to be “unconnected” almost impossible in today’s information age.