One plus one makes three (for social networks)

Abstract

Members of social network platforms often choose to reveal private information, and thus sacrifice some of their privacy, in exchange for the manifold opportunities and amenities offered by such platforms. In this article, we show that the seemingly innocuous combination of knowledge of confirmed contacts between members on the one hand and their email contacts to non-members on the other hand provides enough information to deduce a substantial proportion of relationships between non-members. Using machine learning we achieve an area under the (receiver operating characteristic) curve (AUC) of at least 0.85 for predicting whether two non-members known by the same member are connected or not, even for conservative estimates of the overall proportion of members, and the proportion of members disclosing their contacts.

Figure 1. Definitions and examples.

Any social network platform divides society into two sets: the set of members (black nodes) and of non-members . In our toy example of individuals, i.e. a fraction of , are members. The relevant subset of non-members (red nodes) that are in contact with at least one member is distinguished from other non-members (gray nodes). of the members, i.e., a fraction of , have disclosed their outside social contacts. The knowledge of the set of edges between members (black, bi-directed) and the set of edges (green) to non-members is enough to infer a substantial fraction of edges between non-members (red edges).

Figure 2. Comparison of basic network analytic statistics of the five data sets obtained from Traud et al. .

Figure 3. Membership propagation in a toy example according to different propagation models.

Note that real social networks exhibit more long-range edges. Examples for the platform penetration value show the nodes from which the propagation started (black nodes with white core). Other members are marked black and relevant non-members red; for ease of reading arrows are not displayed, but black edges are bidirectional while green edges point from black to red nodes. With BFS and DFS the network is explored starting from one node (denoted by a white circle); with RW and EN there are more nodes from which the propagation is launched; and finally, for RS all selected nodes can be seen as starting nodes.

Figure 4. Features based on different edge sets between the exclusive, joint, and common neighborhoods of v and w.

All left-hand nodes belong to the joint neighborhood of and . is exclusive to , while are exclusive to , and are common neighbors of both. Our features comprise the absolute number of edges between common neighbors (black, dashed edges), exclusive neighbors (black, straight edge), joint neighborhood (all black edges between nodes ), and an exclusive and a common neighbor (black, dotted edges). For each of them we also added their normalized value. Normalization was done by the number of possible edges between the neighbors they have.

Figure 5. Prediction accuracy (AUC) of samples based on all member recruitment models in the cross-validation training scheme applied to UNC data.

The white square denotes a data point where there was not enough data to make the prediction.

Figure 6. 4 → 1 cross-prediction accuracy.

Minimal (lower triangle) and maximal (upper triangle) prediction accuracy for all five member recruitment models are shown as a function of platform penetration and the disclosure parameter . Upper row: ; lower row: ; black triangles denote data points where was smaller than the according fraction of positive samples among all samples.

Figure 7. 1 → 1 cross-prediction accuracy.

values for each of the five member recruitment models at . The and -axis show on which network the random forest was trained and tested, respectively. The white field indicates that there were too few edge samples to reasonably train the classifier.