Social Networks in the News at NYT

My colleague Scott Sargent at Telligent notes that there are two sections of the March 29th Sunday New York Times feature articles illustrated with network graphs.  The Business section runs an article “Is Facebook Growing Up Too Fast?“ (http://www.nytimes.com/2009/03/29/technology/internet/29face.html) and the Style Section has an article on The Celebrity Twitter Ecosystem.

My colleague Prof. Ben Shniederman is positively impressed by these images.  He writes, “Notice how the node layout remains stable as edges are removed, so by the 4th figure the edges can all be followed easily….”.  This is one of the themes he highlights in his paper and presentations about problems and improvements in network graph drawing (see: http://www.cs.umd.edu/hcil/nvss/and in particular http://www.cs.umd.edu/hcil/pubs/presentations/NVSS-3.ppt). Prof. Shniederman’s  5th edition of Designing the User Interface is now available with two full chapters on the website with wordles to open each chapter.

A somewhat related article ran the same day in the Style section on The Celebrity Twitter Ecosystem (http://www.nytimes.com/2009/03/29/fashion/29twitter.html). This image focused on the linkages between well known people using Twitter and, by extension, revealing who they follow and who follows them in the social network.

In the first image no names are associated with the nodes, in the second the names are the major point of the diagram.

The practice of “anonymization” of network graphs may be moot in light of a recent publication mentioned on the Social Network Analysis email list (SOCNET) by Mark Round from QinetiQ of a paper:

De–anonymizing Social Networks – Arvind Narayanan & Vitaly Shmatikov
(http://33bits.org/2009/03/19/de–anonymizing-social-networks/)

which suggests that just publishing the unique pattern of links around an individual is sufficient to identify them in an otherwise anonymized data base.

Abstract:
Operators of online social networks are increasingly sharing
potentially sensitive information about users and their relationships
with advertisers, application developers, and data-mining researchers.
Privacy is typically protected by anonymization, i.e., removing names,
addresses, etc.
We present a framework for analyzing privacy and anonymity in social
networks and develop a new re-identification algorithm targeting
anonymized social-network graphs. To demonstrate its effectiveness on
real-world networks, we show that a third of the users who can be
verified to have accounts on both Twitter, a popular microblogging
service, and Flickr, an online photo-sharing site, can be re-identified
in the anonymous Twitter graph with only a 12% error rate.
Our de-anonymization algorithm is based
purely on the network topology, does not require creation of a large
number of dummy “sybil” nodes, is robust to noise and all existing
defenses, and works even when the overlap between the target network
and the adversary’s auxiliary information is small.