Social Media Research Blog

SXSW Panel on Collaborative filters

I am at SXSW this weekend and wow what a conference this has been! Met a lot of cool people and been to a bunch of happening parties! I plan to post a few updates about the conference. In the mean time here is a quick post from notes I wrote during the panel discussion on Collaborative Filters.

Anton Kast from Digg.com gave a brief history of collaborative filtering from the research literature covering tapestry (from parc) grouplens (UMN) and a few other projects mostly from 1990s and draws comparisons to current systems used in spam filters, pagerank , tagging systems and applications in facebook ads etc. The talk wasnt very technical and meant to be a quick overview for the audience that might not be familiar with the research background. Kast described recommendation as the output of collaborative filtering that is personalized for a particular user in the system. For example  amazon (people who bought this also bought..), behavioral ad targets, google news etc. I wish Kast had spent more time discussing the last slide which covered practical problems: sparsity problem in recommendation systems, early rater problem/cold start, gray sheep (small group very popular).

Erik Frey from last.fm shared some interesting stats -- 25m unique users/month. The types of relations that last.fm derives: songs-users, users-users. He also shared some insights on what were described as lean forward and lean backward mode in music recommendation systems. The lean forward mode is when a user is feeling a little experimental and would like to discover new stuff. The lean backwards mode is when the emphasis is on continuity and the desire to listen to something familiar (i.e. radio experience). The two main data sources for last.fm are : scrobbles, social info like tags. Frey suggests that tags are quite useful to explain recos

The next speaker was the cto of baynote -- a recommendation system that is provided as service using javascripts that enables clients to customize their website in real time based on user behavior. They also apply it for reordering the search results.

Finally, Jon Sanders from Netflix gave a very good talk covering the history of netflix and its evolution. Today netflix has about 2 billion ratings and gets about 2 M ratings per day. 60% of movies watched are via personalized recos -- amazing!

Following were the steps in evolution of netflix:

step 1 At first netflix was a editorially managed site and the first evolution was that of adding a rating widget.

step 2 score and sort all movies using rating alone (top k list)

step 3 movie similarity by k-nearest

step 4 interest based recos (same actor director  etc)

step 5 ask ( get users to rate genre)

step 6 ask others (top 10 lists from users)

step 7 explain why (because you enjoyed)

step 8 $1M prize

step 9 develop a unique experience and customized website for each customer

future: streaming video specific recommendations, incorporating implicit and explicit metadata, discovery focus, let people drive and not be led.

Geolocating blogs

A quick note:

Clay Finkand colleagues from UMBC have a new paper on "Geolocating Blogs From Their Textual Content". From the abstract:

"Mashups showing the geographic location of the authors of social media content are popular. They generally depend on the authors reporting their own location. For blogs, auto-mated geolocation strategies using IP address and domain name are not adequate for determining an author’s location. Instead, we detail textual geolocation techniques suitable for tagging social media data, facilitating development of geo-graphic mashups and spatial reasoning tools."

As noted in this paper, trying to geolocate blogs from IP addresses or domain names does not work well due to many blogs mapping to various hosting services. To locate the named entities that refer to a potential location, the authors use GeoNames (This is a really great, free resource for those working with geographical analysis). The location of the blogger is disambiguated by clustering occurances of different geographical named entities in a region. From the paper:

For example, if “Maryland” has already been disambiguated as the U.S. state of Maryland, then the text “Laurel, Maryland” leads us to disambiguate “Laurel” as Laurel, Maryland.

Location is an important element in social media analysis and any results (for example, sentiment analysis or trends) that could be pivoted on this dimension are especially useful in providing an insight into what people in different regions think about a particular topic.

In context of this work, there are a few more related papers (in addition to references in this paper) one might want to check out. Although these papers dont address the same issue, they are interesting from the perspective of location analysis:

• Recent study of "Iran's online public" by Harvard researchers.
• "Spatial variation in search queries" by Backstrom et al.
• A study of blog commentsof persian bloggers by Noor Ali Hasan
• In our work with twitter analysis, we did some basic mapping of location names mentioned in user profiles to lat/long coordinates using Yahoo API.

Live Labs Social Streams

Very cool! Live Labs releases the Political Streams project. It is a lense into the people and places that are receiving a lot of attention on blogs and news.

You can read the post snippet and see neat graphs of how the attention changes over time:

Also browse through the related names and places as you explore different topics and blog posts/news stories. Furthermore there are profiles of people and places in news that are generated using Freebase.

 

This is really cool! If you looked at search trends, many of the search terms are in fact about places and people in News. Users go to a search engine to find out both why they are in news? and often who the person is? Social streams (right now, for political streams) let you explore this in a real time, interactive manner. 

Nice!

Social Network Visualization Eyecandy

Visualization of graph data is incredibly challenging, particularly when it comes to extremely large, scale-free graphs and social networks. A few simple searches on the Web and you will find some mesmerizing and very cool images. Perhaps the most cited and fascinating of these are Matt's "Mapping the Blogosphere" series.

Some of my favorite tools for graph visualization are LGL (see Twitter visualization using LGL), Prefuse, Guess and UCINet (no specific ranked order). I have also been waiting to get a chance to try out AT&T's large network visualization software. Two other promising tools that I have not played with yet are Tulip (TOTH Eytan!) and yWorks.  Following is an image I had generated a year ago (more here) using UCINet. This is a community of political blogs discovered using an implementation of Dr. Mark Newman's community detection algorithm:

One thing that I think would be exciting is visualizing evolving networks. Current tools force you to map blogs, social networks etc. into static graphs. This is a serious limitation. Their real meaning and value comes from seeing the temporal interactions between members, evolution of community structures,  changes in strength of ties over a period and detecting bursts. As far as my knowledge goes, this feature is not supported by any of the open source/freely available tools that I have explored. I would love to hear about other graph visualization tools that I may be unaware of.

We the Numerati

A quick post: I am almost finished reading "the Numerati" by Stephen Baker. I must say that I had very high expectations from this book and it seems to have come slightly short of it. Dont get me wrong, it is certainly a good book but, it wasn't a very technical book. So many of the topics and ideas presented here might sound quite familiar to someone who is wading in data and algorithms every waking hour. What I really like about the author is the way he treads a fine line between dismissing some of the myths about data miners and highlighting some legitimate concerns in the field. It is a great compilation of interviews and summarizes a number of research topics. A few interesting points/quotes from the book: Be watchful of the fact that in some fields (like analyzing terrorist networks) where lives are at stake, we need to be very very careful. False positives doesnt necessarily mean that it is a non-event. On the other hand, innocent folks can find themselves on terrorist watch lists. Failure can cost lives. From David Sifry's interview in the book -- be cautious of "mistaking correlation for causation". Don't think of privacy filters as add-ons that we can worry about after coming up with the data mining techniques. In Jeff Jonas's words sometimes "repurposing" data can lead to unintended uses. Watch out! Stephen Baker touches upon many different applications and profiles a number of scientists, companies and startups that make up the Numerati. My favorite chapter ofcourse was the "Blogger" and "Terrorist" for its social media and social network related discussions (OK I admit there is a slight bias here :-). And Pranam too is eagerly looking forward to reading the pages that talk about splogs. (I am rather surprised that he wasn't interviewed for this!) Overall, its a good book that caters to a wide audience. But most importantly does a great job at demystifying the Numerati and showing a balanced, informed picture about what we do.

Invited Talk KDD 2008: Internet Advertising and Optimal Auction Design

Following are a few running notes from the KDD invited talk "Internet Advertising and Optimal Auction Design" by Dr. Michael Schwarz from Yahoo! Research:

Dr. Schwarz  explains that the original advertising models were quite simple but now new tweaks and optimizations are being added to, for example, estimate click probabilities, match ads for long tail of queries, etc. So there is a "Fudge" factor in online advertising algorithms, and the question now is how to combine these correctly?

In sponsored search options space, Overture was really the pioneer of pay-per-click. In such a scheme, the bidder would pay whatever price that was fixed during the auction of an advertising position. However, soon people realized that generalized first auction is unstable. This is because if advertisers can keep changing their bids and the minimum bid keeps fluctuating. The situation is illustrated in the following paper and as shown in the image below:

This system was also prone to manipulation by automated robots quite easily.

Next, in 2002 Google came up with the Generalized Second-Price option (GSP): here the advertiser pays for the price fixed by the next highest bidder (plus a minor amount like a cent), upon winning an auction. Later Yahoo! followed. In this mechanism the assumption is that for the ad position i, clicks are almost independent of the advertisement. A clock shows the current price that keeps increasing, a bid price is fixed only at the time of dropping out and the final payments are computed according to GSP.  Dr. Schwarz presents how this is related to "Generalized English Auctions".  The intuition is that the advertisers values the price just at the point where the advertiser drops out of the game. If we think about it, at each point the advertiser is making a decision to go closer to the point where he values the position enough but not to a point where he/she would have regrets if the next highest bidder would drop out of the auction, causing a win. The GSP approach has been shown to have a unique equilibrium. For more details you can read the paper: "Internet advertising, generalized second price options".

Finally, the talk discusses an optimal matching problem. If you know the probability distribution from which the values for the bidders are drawn, in theory, the highest probable match (ie optimal auction) is deterministic. According to further studies in these advertising models, Dr. Schwarz suggests that despite multiple units the value for a slot, the auction is not dependent on the number of slots! This is great from a search engine's perspective. Although I guess this hold to a certain number of slots -- or else search results would have looked rather different! Further, the decline in CTR from one slot to another also does not have any influence on the auction. This is perhaps where clever data mining techniques can be applied to help estimate the probability distribution of bidder's values for each slot and  ultimately, lead to setting optimal reserve price. I guess this is perhaps the point where search engines start guarding their trade secrets closely.

Finally, during discussions with many people at the conference, on theme that kept coming up is that of social advertising and monetization of social networks -- which has been a typically difficult problem. Personally, the way I see this (more of my 2 cents here) is three fold:

• One, are you advertising for the purpose of targeting an individual (based on the profile information)?
• Two, are you targeting an individual based on the actions of her friends and neighbors in the social graph?
• Three, are you targeting a group or a community in the network?

KDD is an exciting venue precisely because it is at the confluence of data mining, social media, large scale text and graph analysis and monetization-- all the themes that have made it a great learning experience for me.

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach

Liveblogging from WebKDD 08

Learning Preferences of New Users in Recommender Systems: An Information Theoretic Approach
Al M. Rashid, George Karypis, and John Riedl

[Update: This was the winner for the best paper award]

This paper is addresses the cold start problem in collaborative filtering, i.e. for new users since the system does not know of the user's preferences, the system cannot recommend items. This paper looks at a few different heuristics:

• Popularity of an item. The system picks most popular items and presents the new user with these. If the user rates these items, it constitutes the initial profile. The interesting point they note is that a good strategy is to pick popular items that have a varied rating distribution. The downside is unpopular items are harder to predict.
• Entropy: identify informative items. Downside is that entropy does not pick the right item when the ratings are few.
• Entropy0: treat missing ratings as separate rating items. However, this favors popular items more.
• HELF: combines entropy with popularity.
• ICGN: Information gain through clustered neighbors. Use ratings so far to determine what is informative next.

Evaluation was done on the MovieLens recommendation system.Overall ICGN and Entropy0 perform the best.

An Empirical Study of Dynamic Pari-mutuel Markets: Evidence from the Tech Buzz Game

Live Blogging from WebKDD 2008
An Empirical Study of Dynamic Pari-mutuel Markets: Evidence from the Tech Buzz Game
Yiling Chen, David Pennock, and Tejaswi Kasturi

Presented by Dr. Dave Pennock

Tech buzz game uses the wisdom of the crowds and people can 'bet' on events like: "Bird flu outbreak in UK in 2008" etc. An example of a prediction market that David talks about is InTrade and there are tons of other clones out there: Hollywood stock exchange etc. Pretty amazing some of the prediction accuracies that are shown in some of the examples.

Parimutuel markets: All the money goes into one pool and there is a (Zero sum) wagering game in play an winnings are shared equally. In dynamic parimutuel markets (DPM) the entry price changes as more people purchase the share (for either outcomes) in the pie. There is a cost function associated with each purchase price. C(q1,q) = sqrt(q1^2+q2^2). It has a nice property that the ratio of prices is same as ratio of shares.

This idea was used behind the Yahoo! Tech buzz game which was an amazingly cool site, if you remember. It still amazes me how much folks would do for fake money or points! Some research strategies presented for DPM as a prediction mechanism:

• Baseline: Implemented using robot traders buying and selling at random. Ofcourse the robot lost a lot of 'fake money'.
• Sophisticated vs. naive traders: myopic trading -- just decide based on immediate situation and not future.
• Crime pays: people open false accounts and move money from one account to another to add up the signup money.
• For 352 stocks prediction converges to the actual value/outcome closer to the cash out event.
• Markets were pretty accurate in determining the actual buzz (as measured using query logs)

Very cool! Watchout for a new prediction game called Yoopick, a sports prediction game! Here you can predict not just the outcome but the actual score ranges.

Only 10 Cherry Picked? Thats not Enough!

Sixapart re-launced Blogs.com as a blog directory... yawn! (Wow! A Yawn is really contagious... via techcrunch's coverage -- the Yawn cascade initiator).

Seriously.. Sixapart? I am sure you could do a lot better than having an expensive team of editors cherry pick their favorite blogs in a handful of categories. You guys have a ton of good, high quality blogs and the interesting thing is that you can use some of the tag information to cluster these blogs into the different communities they belong to. For example blogs that talk about business are likely to use tags like marketing, advertising, finance etc. Algorithmic approaches can be effectively used to mine blog graphs to find high quality feeds.

At eBiquity, we have looked at this problem from two different approaches:

• Using readership information from Bloglines, we can cluster the blogs based on how people subscribe and categorize their feeds. Although typepad probably does not have access to subscription information it has other sources (like what tags are used by the blogger, and the number of people visiting and commenting on the blogs) to come up with a much better directory. Something on the lines of "Feeds That Matter" (see site here, bit outdated though).
• More recently, I have looked at how we can combine the graph structure and folksonomy information to identify communities in social media. This was an Idea that I first shared on this blog and subsequently submitted a paper, which I would be presenting at this year's WebKDD workshop.

The point is, I beleive that the top 10 offered by sixapart and bloglines are not really that interesting anymore. In the era of hundreds of thousands of potentially good blog (of the millions that exist), we can rely on algorithmic approaches to find (more than just 10) high quality blogs. This is also related to the "Feed Distillation Task" that TREC ran for 2007. If you are interested in feed distillation... check out CMU's submission by Elsas et al. and the follow up papers by Jon at other venues.

Another challenge is being able to find not just popular blogs but also that cool blog that probably be down there somewhere in the long tail.

Structure of Information Pathways in Social Networks

One of the papers I am looking forward to at KDD 2008 is "The Structure of Information Pathways in a Social Communication Network"  by Kossinets, Kleinberg and Watts (PDF). This paper analyzes the communication graph of an email network. The authors present two important and novel concepts to social networks research: Temporal distance and Network backbone. They beautifully incorporate a rather Operating Systems textbook technique of vector clocks into the analysis of social networks. Following is an excerpt from the abstract:

....We formulate a temporal notion of “distance” in the underlying social network by measuring the minimum time required for information to spread from one node to another — a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges—a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

The authors use vector clocks to determine the nodes that are up-to date with respect to each other and describe a network backbone as

the subset of edges in the social network that are not bypassed by a faster alternate path.

Thus a network backbone is the set of edges that are critical in ensuring the flow of information within the network and thereby responsible for keeping the nodes 'in sync' with respect to each other. The idea of a backbone is not new and many real world networks like the internet are known to have some such equivalent. Traditionally, in social networks most of the attention so far has been on the "strength of weak links".  In this paper, the authors not only validate this phenomena, but also show that these links are critical in the network backbone structure. This is a paper that offers some deep insights and fundamentally advances our knowledge of how information flows in social networks.