Social Media Research Blog

Jon Kleinberg's Talk on Information Flow and Privacy in Social Networks

Yesterday, I had the opportunity to visit JHU to attend Dr. Jon Kleinberg's talk "Social process, Information Flow, Anonymized Network Data". Following are some running notes from this talk.

Dr. Kleinberg (aka the rebel king) talks about how the convergence of social and technological network now lets us observe information at a much larger scale. We have come a long way in social network analysis. From the initial days of 34 node karate club datasets to analysis of almost 240M users of Instant Messengers. But Dr. Kleinberg points out that it isn't just a matter of scale. Some phenomena that is not visible at smaller scales can become observable when you look at a large number of users. However, this also comes at a cost: often, we understand little about each node or link means. Compare the large scale studies to those of the karate club dataset where we know the roles of individuals in the two splits. 

Given the large, networked social data that we can observe, the question Dr. Kleinberg asks is "what can be said about the diffusion of information?". It has several implications like studies of epidemic propagation, information cascades, viral marketing, how rumors, opinions and fads diffuse in these networks. Recently, there has been a great deal of interest in these topics from both computer science and social sciences. One interesting and innovative approach by which Jon and his students study this is using chain letters -- those pesky emails that keep getting forwarded! And that is exactly what makes it possible to analyze how the information spreads.

D. Liben-Nowell, J. Kleinberg. Tracing Information Flow on a Global Scale Using Internet Chain-Letter Data. Proc. National Academy of Sciences, March 2008

They use two instances of widely circulated chain letter: petition against the Iraq war and a petition for increased funding for NPR. The neat trick they use is to mine the snippets from search engine results and crawl public mailing lists for these forwarded messages -- which gives them a clear picture of how the chain spreads in the network. I was really fascinated by this statement that Jon made:

Rather than thinking of it as people browsing through a network of documents, we should think of the chain letters as "documents blazing through a network of people".

Indeed, the analogy presented here was that of a document going through mutations as it was being forwarded by people. Some folks would append names to the list, some would delete them and some would change names to humorous variants like 'Donald Rumsfeld' or 'Karl Rove'. Dr. Kleinberg's slide containing the structure of this chain letter propagation was rather surprising. It consisted of long chains which is counter intuitive. One would normally have expected it to be a large number of short chains. Rather, it was like performing a depth first search traversal of the network.

There were two models suggested by the authors: one was based on temporal ideas and the other spatial homophily in networks:

• Temporal model: chain letters are like DFS and the model is based on timing. The basic idea is that people do not act at the same time. Unlike several epidemic models (which are based on the assumption of synchronization), in this model a node v participates in the chain with some probability and forwards the letter to her neighbors as some function f(t) = t^c (where c is typically -1.5 in human networks).
• Spatial model: is based on homophily, the idea that people tend to associate with similar individuals in networks. This similarity may be spatial, geographical or demographical. The cool insight that this model offers is that long range links create awareness but for participation it is the dense local structures that really motivate people to act.

The second part of this talk focused on privacy and anonymization in social networks. This is an important research problem. As computer scientists, we are always looking for more data but at the same time we have to take the privacy of a user very seriously. From personal experience, after the AOL search query log debacle, it has become almost impossible to get companies to release their datasets -- and for pretty good reasons. Given this deadlock, as researchers it becomes even more important for us to understand the type of attacks and what we can do to prevent these and ensure anonymity of the users when a dataset is released. Dr. Kleinberg points us to a few recent research papers in this direction:

• On anonymizing query logs via token-based hashing Ravi Kumar, Jasmine Novak, Bo Pang, Andrew Tomkins
• A. Narayanan, V. Shmatikov. How to Break Anonymity of the Netflix Prize Dataset. Oakland 2008. (online)

The basic attack strategy is that you can easily add yourself to the system. For example if you were to know that the email network would be released, you would signup for a new account and then add a few edges (by sending an email to known set of individuals). This way you can identify yourself in the 'anonymized' network by looking for these signatures or subgraph patters.

One would expect this problem to be NP-Hard and for very large graphs almost intractable, but in the following paper Dr. Kleinberg shows that under certain conditions this can be solved easily, thus breaching the network's privacy.

L. Backstrom, C. Dwork, J. Kleinberg. Wherefore Art Thou R3579X? Anonymized Social Networks, Hidden Patterns, and Structural Steganography. Proc. 16th Intl. World Wide Web Conference, 2007.

The basic intuition was to build a subgraph and attach it to the network. If the subgraph is small and randomly generated, it will be likely that it is unique and thus efficiently findable. Furthermore, they show that in real networks, these types of subgraphs are often quite readily available in the form of small networks or cliques. The paper presents interesting bounds on the problem and proves that you indeed need a subgraph H of the size sqrt(log n) which is reasonably small.

I thoroughly enjoyed the talk, especially since the last conference I attended, Dr. Kleinberg's talk was jam packed and I was hardly able to enter the room. It is always inspiring to hear such speakers and learn from their talks.

This post is from my running notes during the talk and hopefully benefits folks who were unable to attend.

Distinguished Speaker: Jiawei Han on "Research Challenges in Data Mining"

It was an honor to have Dr. Jiawei Han on our campus today. He was hosted by the Information Systems (IS) department as part of the distinguished speaker series. Dr. Han is a pioneer in the field of data mining and has written a book that I had used for the Data Mining class I took with Dr. Kargupta.  In fact,  Dr. Han even obliged to autograph the copy for me :-D. (I know thats geeky but is'nt that cool?)

Here is a summary of his talk on "Research Challenges in Data Mining".

Dr. Han narrates and interesting episode where Dr. Jim Gray brought in a hard disk and asked his students to guess the capacity... this was perhaps just 10 years back and a 2G disk evoked a jaw dropping response from the audience. According to Dr. Jim Gray, "We are in the era of Data Science". Science used to be
experimental (observe the stars) then it moved to computational (run simulations) but now we are really moving towards  "Data Science" (Gigabytes, Terabytes and Petabytes of data all around us).

The main themes of the talk were:

1) Pattern Mining: Classification by finding frequent, discriminative patterns.

Dr. Han described an interesting experiment in which they analyzed the feature length vs information gain. What they found was that you get more information by combining features (2,3,4), while single features dont give you much information. On the other hand too long pattern, and it is not too informative either. This has an important implication, especially in text mining where using NGrams (bigrams and trigrams) has generally been found to be useful but if you use too long a pattern, it is not that helpful.

Another analysis presented was of information gain vs pattern freq: Frequent patterns have more information gain than less frequent ones. On the other hand extremely frequent patterns have little gain (for example stop words).

The implication of these results is in using SVMs and C4.5,  classification accuracy can be improved by using discriminative patters/feature selection.  Dr. Han suggests that "It is not the number of patterns its the quality of patterns. Its Not the more the better ......instead, the better the better." A few selected discriminative patterns are more useful than a lot of features in case of classification.

2) Streams Data Mining Classification for rare events.

When you have multiple streams of information and you can not store all the data, but need to remember some of the history, (in order to do classification of a new stream) it is helpful to use sampling techniques. Dr. Han discusses results from one of their recent papers on using biased sampling. The idea here is that you dont toss off positive data (all of it is stored since there are very few samples). Now, by selective sampling of negative data one can use equal amount of positive and negative data for training a classifier. In case of multiple streams, using an ensemble approach to classification is suggested.

3) Information network analysis. Distinguishing objects with identical names. (eg author names, song names)

Name disambiguation is a very difficult problem. For eg there are 14 Wei Wang on DBLP -- some with even same co-authors, same conferences, etc. in such cases, textual similarity can not be used, since they are all basically in the same field. Dr. Han discusses how using only information from DBLP, they make links powerful. The basic idea is to group references according to their similarity. By performing a random walks along different join paths, they can group the authors and determine the different name ambiguities in the graph. Often, in computer science and other fields, Collaboration behavior within the same community share some similarity and this can be helpful in disambiguation.

Another research paper that Dr. Han highlights is on "Truth discovery with multiple conflicting information providers on the web". The goal here is to algorithmically determine what piece on the Web is more trustworthy. The proposed approach is to model it as a tripartite graph of (website,facts,object).

Assumption is that there is just one true fact and that false 'facts' are introduced due to random factors (and not malicious intent). The domain was restricted to identifying the right book title, which is slightly easier than something like political opinions. The basic idea behind their approach is that a site is trustworthy if it provides many facts with high confidence and once again this can be modeled as a matrix computation problem of identifying trustworthiness.

Some of the other areas that were very briefly mentioned by Dr. Han were:

4) Mining moving objects - unrestricted, restricted (cars) scattered (Cell phone and rfid)
5) Spatio temporal multimedia clustering with obstacles
6) blog mining, etc.
7) data cubes.
8) Visual data mining
9) Biological data mining
10) DM for software engineering/bug mining

This was a great talk and very informative. I really liked how the Dr. Han gave the basic intuition behind their methods and yet managed to give a broad overview of some of the challenges in the field.