This paper presents an extremely interesting informal review of recent work on discovering graph structures in social networks. The principal theme is that information about members in a social network can be obtained with relatively little computation and in a covert fashion. A social network is an example of a data-centric network where the message is based on message content and choices are made by those sending and receiving them rather than by network address-based routing. Assumptions about the nodes (members) are minimal in the paper, so the results should have a wide range of applicability. Although the motivation of the paper is a better understanding of attacks on member identity or, at least, member interests or preferences, thematically, the graph theoretical results can be viewed in the wider context of discovering structures in very large graphs solely via local data.
In order to state the main results, I must first mention some technical matters. The social network is modeled by an undirected n node graph whose nodes are the members and whose links represent traffic of some kind (for example, email, Facebook associations, and common interests such as downloads of similar music). It can be assumed that the attackers are already in the graph. The identification of links in a data-centric network is not straightforward since the links cannot be completely specified as pairs of Internet protocol (IP) addresses. The paper describes three types of attack.
The first attack is the walk-based attack. Construct a k node graph H. The nodes x1, ..., xk are attackers. H is designed to have a Hamiltonian circuit on the attacker nodes and additional edges to b nodes w1, ..., wb in G (targets). Edges between nodes xi and wj are constructed using a random protocol with parameters controlling degrees b and k. The basic idea is that k = (2 + δ) log n, where δ > 0 but otherwise unspecified in the paper and b = O(log2 n). The following objectives are needed so that the attackers can identify H in the modified social network:
- (1) No subset of nodes in G exists whose induced subgraph is isomorphic with H;
- (2) H is computationally easy to find in the network; and
- (3) H has no nontrivial automorphisms.
Random construction is used as a way to make the attack hard to detect. The paper gives some details on the analysis and efficiency of the attack, but most details are left to other cited papers.
Next is the cut-based attack. A lower bound on k of O(√log n) is stated, but no explicit reference for this is given. In the cut-based attack, H is constructed with only O(√log n) nodes, but the construction is deterministic so that the claim of undetectability is weakened. The links generated for H satisfy somewhat different properties from those of the walk-based attack, and the recovery of H in the network incurs a greater computational cost.
Finally, the paper discusses passive attacks. A passive attack is a variant of the walk attack based on normal activity among a coalition of k members of G. One of the most interesting points raised in the paper is that, in walk attacks, the activity of the attacker may be typical of any member’s activity.
The paper provides some simulation studies that support the analysis, but the precise role of the free parameters, such as δ, and the exact specification of constants embedded in O notation will require further experimental research.