Correlating votes on Digg with website traffic

Anonymous Prof has written a very nice post analyzing the amount of traffic that flows to websites from front page stories on Digg. S/he took website traffic data from Alexa and investigated the change in traffic that resulted from a page on each site making it onto the front page of Digg. For large websites, the effects were negligible, but for smaller sites (less than 0.0005% of pageviews on Alexa) the effects are quite apparent. The traffic increased by around 0.1% per vote on Digg, meaning that a story receiving 500 diggs (votes) would temporarily increase traffic to the site hosting the content by around 50%. The effect on very small sites (those not indexed by Alexa) would obviously be much bigger, and often causes the webserver to go down under load.

Anonymous Prof's post on visualizing the last.fm social network is also worth a look for the cool pictures.

Staying anonymous online: part 2

I wrote recently about the amount of personal information that each of us is making public and putting online, sometimes without even realizing it. In the post, I stated that it should be possible to link the various profiles of a particular user across different social networking sites, even if the user has completely different/anonymous user-ids on the different sites. Turns out that there already exists a company that does exactly that ....

The website is called Spokeo and their aim is to let you keep track of what (/everything) that your friends are up to on a bunch of different social networking sites, including: last.fm, Amazon, MySpace, LinkedIn, YouTube, Flickr, Digg, Facebook, etc. According to Phil Bradley, who tried it out, the system is able to link the profiles of your friends on different sites, even if they use different login names on each site.

What kind of information can you see? Well, anything that's public and anything else you have access to according to the website:

"All users can track information that is publicly available. Only users who have accesss to private content on a third party site can track that private content in Spokeo."

The thing is, there is quite a lot of publicly available data about pretty much everybody on the net. A service like this that aggregates the data and make it easier to find and search, means that the inherent anonymity that comes with there being so much data on the net and that data being distributed over so many websites doesn't apply any longer. Data about you can now be integrated, stored and archived. So what you did a number of years ago on some obscure website, may well come back to find (/haunt) you in the future.

Sound fanciful? Imagine for example that you are applying for a job and the prospective employer has a look at your profile on LinkedIn and then links to your Digg profile only to discover that you particularly like stories about some ultra-liberal political candidate ... or that you're into guns ... or maybe you've shown a passing interest in a certain religious sect. - All this information wouldn't be hard to find, but it's probably not the stuff you want on your CV!

Also, it looks like Spokeo isn't the only "social content aggregator" and that these sites are becoming quite common, according to this post on Techcrunch.

Most Popular Data Mining Algorithms

Just saw this post on the Data Mining Research blog about a summary paper on the top 10 data mining algorithms as voted by the program committees of KDD, ICDM and SDM. The paper gives a really nice introduction to and summary of a bunch of particularly useful algorithms. It is a great starting point for somebody interested in finding out more about data mining. Some of the sections are better written than others - I particularly liked the discussions regarding support vector machines (SVM) and k-nearest neighbor (kNN) classification.

Predicting Airfares using Machine Learning

Good research ideas can be turned into interesting and successful businesses. Case in point, a company called Farecast that provides an airfare search engine (similar to Orbitz). The website distinguishes itself by using machine learning techniques to predict the future price of airfares based on historical data. Thus it recommends whether a user should buy immediately (because the price is going up) or wait for a lower price (as the price is likely to fall).

I'm interested in the company in particular because it is based on technology developed by my thesis advisor Craig Knoblock (together with other researchers at USC and the University of Washington). The original idea was described in this paper "To buy or not to buy: Mining airline fare data to minimize ticket purchase price" by Oren Etzioni, Craig A. Knoblock, Rattapoom Tuchinda, and Alexander Yates. The paper was published at KDD back in 2003, but is still a very good read. - Needless to say, I am a big fan of Craig's research. He has a knack for discovering new research problems that are both interesting and practical (and sometimes even commercializable).

According to a post on TechCrunch, the company has just started predicting airfares on some international routes. This will be very useful for those of us not living in the US and who spend a significant portion of our incomes on airfares. - I might be able to travel home and see the family a bit more often.

Digging into the workings of social news aggregators

An ex-colleague of mine, Kristina Lerman, wrote a very interesting paper analyzing and modeling the process in which news items are discovered and make their way onto the front page of the social news aggregation site Digg. The paper is called "Social Information Processing in Social News Aggregation".

Interesting points made in the article regarding the social nature of the system, include:

• People subscribe to feeds of news items that are posted or voted for ("dugg") by their friends, increasing greatly the probability of viewing (and thus voting on) news items that their friends found interesting.
  
• This "social filtering" phenomenon is necessary in order to deal with the huge number of stories that are posted to Digg each day.
  
• Stories propagate very fast through the system: anecdotal evidence suggests that they are faster than clustering-based approaches such as Google News, (which makes sense, as a story must break on multiple news sources before it will appear on a clustering-based news aggregator).
  
• According to mathematical model devised to explain the process by which news items are propagated to the front page, a highly relevant/interesting story (relevance=0.9) may not get onto the front page if the original poster is not well connected - i.e. doesn't have a large number of readers.
• And inversely, relatively uninteresting articles (relevance=0.1) may make it to the front page if the contributor is particularly well connected (i.e. famous).

Reading the article made me think of another article I read recently on using agent-modeling techniques to analyze human social behavior. This time the author was interested in the divergence of opinions rather than the consensus opinion (i.e. newsworthiness on Digg). In his article "Mobility and Social Network Effects on Extremist Opinions", André Martins created agent-based simulations of public opinion so as to analyze the emergence of extremist positions in society. The finding in that case was that more interaction between diverse groups could lower the overall amount of extremism.

(Thanks to the physics arXiv blog for bringing my attention to the second article. - They point out that in this age of terrorism fears, closing borders and restricting travel may well have a negative effect on curbing extremism.)

Gaming in the virtual real world

Google's 3D Warehouse is a repository of user-generated 3D models that can be viewed in Google Earth. Anybody can build models using Sketchup and contribute them to the collection. People have already modeled lots of buildings, bridges, and in some cases entire cities (see Adelaide for example). In true user-generated content style, users can vote on the quality of the models and the best of them are then included by default in Google Earth.

Since the modeling data is free to use/reuse and in an open format (KML), it looks particularly interesting from a data integration perspective. As this collection grows, it should provide a fun dataset for research in spatial data integration. One simple integration problem that comes to mind is:

"find me an office in downtown LA with price less than X and a view out to the ocean"

Answering this query would involve integrating data from different real estate websites along with the 3D building models. Another example integration problem, this time for terrorism defense:

"find all rooftops with a clear line of sight onto a convoy traveling along roads XYZ"

In this case, vector data (street maps) would need to be integrated with the 3D building models.

Anyway, the point of this post was to highlight something very cool (and not so research related) that I saw on the blog digital urban. In the post, the writers take the free content from the 3D Warehouse and add it to a video game, so that game play can take place in a real (virtual) city instead of an imagined one. There is a video of an attack helicopter flying around over London! Looks like you'll soon be able to defend (or invade) your favorite tourist destination.

Yahoo adds del.icio.us data to search results

I'm a big fan of the social bookmarking site del.icio.us. It contains a lot of really useful information on what's popular online. Users only tag webpages that they find interesting, so the fact that a page is bookmarked on del.icio.us is a pretty good indication of its quality, and the more individuals that have tagged the same page, the more likely it is to be interesting.

Yahoo bought del.icio.us a while back, and finally (according to this post on TechCrunch) are starting to incorporate this wealth of information into their own search results. Currently they are adding a line to each result page summary detailing the number of users that have bookmarked the page on del.icio.us. It is hard to tell whether they are also using the data internally to improve search results, i.e. by pushing highly tagged pages further up the list.

A recent and excellent paper by Paul Heymann, Georgia Koutrika and Hector Garcia-Molina called "Can Social Bookmarking Improve Web Search?" suggests that social bookmarking data may indeed (albeit in certain limited cases) be useful for improving search results.

They find that URLs in del.icio.us are disproportionately common in search results, given the relative size of del.icio.us compared to Yahoo's search engine index (which they estimate to be at least two orders of magnitude larger): Looking at the results for some 30000 popular queries, they found that 19% of the top 10 results and 9% of the top 100 results were present in del.icio.us. These statistics are hardly surprising given that users must first find a web page in order to add it to del.icio.us - and they do that using a search engine!

Far more interesting to me is the question as to whether the users are adding useful information by bookmarking a page once they've found it. The search engines record which search results users click on and can already use this information to improve their algorithms. Presumably, however, a user will often click on lots of different results and save only the very best (most relevant) ones to del.icio.us. Thus the fact that a page appears in del.icio.us should carry more meaning than a user clicking on a particular search engine result and therefore may be useful for reordering search results.

The authors don't deal directly with the question of whether a page's bookmark count is on its own a good indication of quality. They do however study the freshness of URLs on del.icio.us and conclude that the stream of URLs being added to del.icio.us are at least as new as search engine results. The authors also estimate that 12.5% of URLs posted to del.icio.us were not present in Yahoo's index at the time they were added, implying that del.icio.us could serve as a small source of highly relevant content for seeding Web crawls.

(Thanks to Greg Lindon for pointing out the paper on his blog.)

Staying anonymous online

In an online world is it possible to keep private data private?

I've been working for a while using data that is publicly available online. It has struck me recently how much information about themselves people are willing to put online - me included. I have a list of public bookmarks, photos, a web page, a blog ....

I'm posting about this because I read an interesting article by Arvind Narayanan and Vitaly Shmatikov on discovering the identity of users in anonymized datasets. The article is called "Robust De-anonymization of Large Datasets (How to Break Anonymity of the Netflix Prize Dataset)" .

Before continuing, I should say that I think it is great what Netflix is doing in releasing anonymized data and creating a prize for the best movie recommendation algorithm. It can be very difficult to find good data for doing research in information retrieval (especially personalization) if you work for a University and not for Google/Yahoo/Amazon/etc. Moreover, I think competitions are a really good approach for both motivating research and for advancing the state of the art by allowing truly objective comparisons between different approaches.

In the paper the authors show that if you have some public and (crucially) non-anonymous data (i.e. information that can be traced to known individuals) and that data contains some overlap with some public but anonymous data from another source then the natural sparsity in the data can be used to identify corresponding users in the anonymous data. Data integration researchers will note the similarity to the record linkage problem.

The example they use is to take movie ratings on the Internet Movie Database (IMDb), which the authors argue is not really anonymous (users often login with their real names), and use it to find corresponding users in the anonymized Netflix dataset. This technique for "de-anonymizing" data relies on the existence of a non-anonymous data source that overlaps with the anonymous source over sparse attributes. In this case, the sparsity in the data results from the fact that it is extremely unlikely that two users watch the same movies in the same order as one another. Thus the order is sufficient to de-annonymise data even in the case where the data is noisy or has been deliberately blurred in some way.

The fact that the two researchers manage to discover the "identity" (IMDb login) of some users on Netflix is of itself somewhat worrying. When a user rates a movie on IMDb they are aware that they are making information public, while on Netflix they may rightfully assume their individual ratings are private (and that only aggregate data is public). Presumably, one could imagine a user rating only "politically correct" movies on their public IMDb profile and films relating to their "personal fetishes" on the private Netflix one, (the latter being useful for receiving personalized film recommendations).

The lesson is, however, more general than the Netflix dataset. Using similar techniques, it should also be possible to link people's profiles on many different sites (not just movie ratings). For example, we could link somebody's del.icio.us bookmarks, to their ratings on amazon.com, to their photos on flickr (and their location through geotagging), to their emails in newsgroups, to their profile on LinkedIn and perhaps even their page on facebook. All this data is public and together it would give a somewhat detailed description of the individual.

None of this is really very alarming per se. We are out in public all the time - our actions, appearance, etc. can be observed when we walk down the street. In some sense, our (public) activities online shouldn't be any different. One should just take the lack of anonymity into account when posting information to del.icio.us/flickr/IMDb/etc. - As Narayanan and Shmatikov point out, it is possible to guess at personal details like political leanings, age and sexual orientation, based solely on the seemingly innocuous information contained in movie ratings.

Don't believe all claims you read in research

I stumbled upon a very interesting article today titled "Why Most Published Research Findings are False" by John Ioannidis. He's talking about empirical studies in Medicine and why so many articles in prestigious journals refute the claims of one another. His conclusion is that it should be expected given a number of contributing factors, such as:

• the natural tendency of researchers to investigate those hypotheses, which support their own prior research;
• time pressure to publish in "hot topic" areas causing researchers to publish whatever results appear statistically significant;
• small and insufficient sample sizes;
• flexibility in the way experiments are conducted including (bias in) the way the data is collected;
  
• financial incentives causing researchers to investigate certain hypotheses over others.
  

While Ioannidis is talking about experiments in Medicine, I think his analysis applies equally to research in Computer Science, where the pressure to publish new research results quickly can be very high and many results (especially in fields like Information Retrieval) can be best explained by biases in the data set.

Regarding the dangers of searching for statistical significance in data, I particularly like the warning given in Moore and McCabe's handbook "Introduction to the Practice of Statistics, Volume 3":

"We will state it as a law that any large set of data - even several pages of a table of random digits - contains some unusual pattern, and when you test specifically for the pattern that turned up, the result will be significant. It will also mean exactly nothing."

They also give an intuitive example of a psychiatry study in which 77 variables (features) were measured and not surprisingly 2 were found to be statistically significant at the 5% level, (which was to be expected by chance). - Obviously one cannot publish results regarding freshly discovered significant features before running a new experiment (with different data) to test the hypothesis that these features are indeed important.

In Computer Science the use of standard test collections (like TREC) can go some way to remove errors due to the flexibility in the way experiments are devised. Of crucial importance in Computer Science, however, is the sample size (aka the data set size).

Peter Norvig gave a very interesting presentation on research at Google in which he emphasized the importance of dataset size. He cited work on word sense disambiguation by Banko and Brill in 2001 that showed that algorithms which performed well at one order of magnitude of training data didn't necessarily perform well at the next. Moreover, the worst performing algorithm with an order of magnitude more data often outperformed the best performing algorithm with less data. - In short, unless you are using the largest amount of data possible (or there is a rationale for limiting your data) it is hard to draw useful/lasting conclusions from your experiments.

Anyway, the point of this post was to say: when reading research papers its best to keep in mind that the claims made by the authors may be influenced (often unintentionally) by biases in their own experiments.

Life during and after a PhD

I gave a quick talk today (along with Giovanni Toffetti and Monica Landoni) to the new PhD students at the University of Lugano on life during and after a PhD. - Finally my chance to tell the new students all the stuff I wish somebody had told me when I started! I'm posting my advice/musings online in case somebody else finds it useful.

Lecture slides on Web 2.0

Today I gave a lecture on Web 2.0 to 3rd year undergraduate students in Informatics at the University of Lugano.

I concentrated on the themes of user-generated content (wikis, blogging, tagging), applications (mash-ups), social networks and personalization. For each area I gave an overview of current techniques and described some examples, before discussing some research areas (and providing pointers to further information).

The slides of the presentation are available online. - Being a presentation on Web 2.0 I thought that using an online office suite was appropriate....

JAIR Article

Craig Knoblock and I published an article "Learning Semantic Definitions of Online Information Sources" in the Journal of Artificial Intelligence Research (JAIR). The article provides a more detailed description of our work on inducing service descriptions that we presented at IJCAI.

Archived News

6 Aug, 2007:
I have just taken up a PostDoc position in the Informatics Faculty of the University of Lugano, Switzerland. I will be working with Fabio Crestani on the problem of discovering, modeling and providing personalized access to news feeds, blogs, and other online data sources. I am very excited about the work and see a great opportunity for combining Data Integration, Personalization and Distributed Information Retrieval techniques.

14 Feb, 2007:
The software I wrote for my thesis for learning definitions of web sources has just been made available on the ISI website! The package is royalty-free for research purposes and comes with all the source code. Documentation is "in progress", so feel free to contact me with installation questions.

9 Jan, 2007:
Here are the slides that I presented today at IJCAI-07.

18 Sep, 2006:
A paper I submitted with Craig Knoblock to IJCAI-07 entitled "Learning Semantic Descriptions of Web Information Sources" was accepted for presentation at the conference.

15 Sep, 2006:
I just gave a talk at ISI on the work I did in my thesis. Be sure to check out the video of the talk! (Unfortunately it's missing the first 4 minutes of audio.)

31 Jul, 2006:
I graduated! My defense was in Trento, Italy. I am now (finally!) a Ph.D. graduate. You can read all about my thesis here.