Commentary by Mark Wahl, CISA
Organizing principles for identity systems:
extracting data from links in social networks (20070619)
The paper "identifying multi-ID users in open forums" by H. Chen, M. Goldberg and M. Magdon-Ismail of RPI describes an algorithm for determining whether users are operating under multiple usernames (e.g., using sock puppets), based on timestamps and usernames of posts of messages to chat boards, which could link together multiple usernames of a single human user. In their simulation, the authors found that
"...an actor operating multiple IDs will give itself away by the fact that those IDs will have different posting statistics to the normal, single-ID actors. In particular the posts of these IDs will not be independent, nor as frequent. We see that introducing randomness into the time to compose a message does not have much effect on the algorithm, nor did changing the average time to compose a message..."
The paper "efficient identification of overlapping communities" (Googlecached) by Jeffrey Baumes (RPI), Mark Goldberg (RPI) and Malik Magdon-Ismail describes an algorithm to find overlapping communities based on history of communication between individuals. In their paper, individuals can be members of multiple communities, and the authors define a community as a group in which
"adding any new member to, or removing any current member from, the group decreases the average of the communication exchanges"
In the paper "inferring privacy information from social networks" by Jianming He (UCLA), Wesley Chu (UCLA) and Zhenyu (Victor) Liu (Google), the authors used Bayesian networks to model relationships in "homogeneous societies" (small closely related groups), and tested with data derived from a subset of LiveJournal users and their friend relationships. They found
"...even in a society where people hide their attributes, [private data] still could be inferred from Bayesian inference.
To protect privacy disclosure in social networks, we could either hide our friendship relations or ask our friends to hide their attributes. However, our analysis showed that randomly hiding friends' attributes and hiding people's attributes at multiple hops away have a small impact on privacy inference. Therefore, effective privacy protection should selectively hide friendship relations or friends' attributes."