Social Media Research Blog

Mean Time to Update Feeds

tIn the State of the Blogosphere report posted by Technorati recently, they describe how the top bloggers update their blogs more frequently than the rest of the population. Given the data I have been gathering on the Bloglines subscriptions, I was curious to see what how most subscribed blogs behaved? For the top 100K feeds ranked by the number of subscribers, I fetched their RSS/ATOM files (some failed, some were filtered due to few posts etc). Using this handy PERL module, I parsed all the pubDates (sorry, RSS only for now) and converted them to their corresponding Unix timestamps. Now for each of these feeds, the Mean Time to Update (ie the avg of the number of days between consequent posts) can be obtained. Interestingly, some fraction of the posts were updated after they had been published (hence were out-of-sequence in the RSS feed). For this analysis, I do not consider these updates -- it would be interesting to dig further into it.

Following graph F(x) is defined as the proportion of X values less than or equal to x. Thus you can observe that for the top 10K feeds 40% of the feeds updated in a day or less. For the rest of the feeds it was 30%. I believe as we go lower in the ranking, this would keep decreasing even further. Interestingly, overall, for the highly subscribed feeds, almost 60% update at least once a week. 

For a feed reader keeping an index fresh and up-to-date is then a function of how many users subscribe to a feed, how often the feed is updated, when was the last time the feed was requested (by any user in the system) and perhaps even when the last ping was registered for a particular feed in the ping stream. I believe in Google reader's case, clicking "show details" displays the last time when the feed was refreshed -- which I have never found to be over 3 hours for any feed that I subscribe to.

ACK: The above plot was made in MATLAB using this script for cdfplot.

Obama vs. McCain

Frankly, as an outsider who can not vote, my opinion would not matter much but I am hoping Barack Obama wins!

This election calls for Americans to make a very important decision, one that impacts not just their lives but the World economy and political stability. This election is also important and interesting event from a different standpoint. Never before have there been so many people using the Web. Social Media tools, blogs, twitter, facebook and virtually every imaginable resource online is now a platform for political activism. In the coming months and years, researchers will be collecting, scrutinizing and analyzing these datasets (some folks already are!)d.

A more immediate feel for the current political pulse of the population can be obtained by looking at search results and online electronic prediction markets -- both of which seem to indicate a tight race with a slight lead by Obama in the recent few days. GOBAMA! check out the Google insight graphs below:

 

Note: The bump on 27th Sept due to the Presidential debate and 3rd Oct after the VP debate.

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.

When Did You Last Update Your Blog?

Think of all the blogs you have started till date. How many are still active? Yep! We have all been there: started a blog and never kept up with it, got busy with other interests or simply do not find enough time to keep up with blogging. 

I wanted to see what is the overall distribution of the date when a post was made. From a random sample of 50,000 feeds that were extracted from the Bloglines feed subscriptions, following is the distribution of the date when the post was made.

From the random sample of feeds downloaded (~42K successfully; approx between 10-15 posts per feed) , 66% of the posts were made in 2008. As for the rest, some even date back to 2001. This indicates that from a random sample, a sizable number of feeds have posts that have been updated within the last year.

This also comes back to my previous point about efficient feed crawling strategies. How do you dedicate resources for keeping a feed index fresh and ensure a good coverage/quality? It would be interesting to see how the following two metrics change as we move from most subscribed to least subscribed feeds:

1. Mean Time To Update Between Posts: Do highly subscribed feeds generally update more frequently?
2. lastBuildDate: When was the feed last (re)published?

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.

One Million Feed Strong

A couple of months back, I had mentioned about a recrawl of bloglines (publicly listed) subscriptions that I was running. Here is an excerpt from my previous post:

Bloglines is any indicator there are a lot more people using feed readers. A study conducted in 2005 found that there were about 32,415 public subscribers and their feeds accounted for 1,059,140 public feed subscriptions. In 2006, we conducted a similar study and found that there were 82,428 users and 1,833,913 listed feeds they subscribed to. This dataset was also used to build the site "Feeds That Matter". In a long overdue attempt to revise the list, I ran another crawl of the Bloglines public directories. This time around, I found that there were about 209,125 users who subscribed to 1,875,027 feeds.

From this new crawl that I have, the roughly 200K public users have about 4,289,988 distinct items in their collective OPML files. These correspond to about roughly over a Million distinct feeds that have at least one subscriber. The following graph shows the distribution of these feed subscriptions, showing the hallmark power-law distribution.

According to Technorati there are 133 Million blogs that they are tracking with about 1.5 Million that have updated in the last 7 days. This is HUGE!

In comparison, it looks like there are about 1 Million feeds that really matter (in the sense that people actually subscribe to them). A few points:

• Here is a list of top feeds from this collection.
• Roughly 11% of all feeds subscribed are served via feedburner. I am a bit surprised by this as I expected this fraction to be much higher.
• The number of feeds that have at least one subscriber has remained relatively stable since last year as far as bloglines is any indicator.

Looking at this data, I wondered what is the best way to index millions of feeds? Crawling is a very heavy duty job requiring huge bandwidth and disk writes. It isn't that easy to implement and I have in the past written my own crawlers for a few projects, indexing tens of thousands of feeds. But to scale it up much further you need a good deal of resources -- which doesn't come cheap either. Ping servers were supposed to be the critical component in the blogosphere infrastructure, unfortunately they are inundated with spam right now. That is why tools like Tailrank's Spinn3r are a great alternative for small startups who want to index blogs. They take the heavy lifting off your shoulders and allow you to build and focus on the main product.

There are a number of research challenges that come up with crawling and ensuring that the index is fresh. Recently, Greg points to a paper at WWW that is pretty remarkable. They crawled 6 Billion pages on a commodity server. (This paper also won the best paper award). I believe that crawling feeds and blog data is quite different from crawling the Web. Ensuring freshness of the index means indexing new posts within minutes of publishing. Given the inundation of ping servers with spam, one option is to poll the feeds and the other approach is to ignore all pings other than those from the feeds of interest.

From Greg's post:

On the question of what content is useful, both in terms of crawling and recrawling, I always find myself wondering how much we should care about pages that never get visited by anyone. Shouldn't our focus in broadening a crawl beyond 6B pages and in recrawling pages in our index depend on how much users seem to be interested in the new content?

This made me think -- how about feeds? If there are only 1Million feeds that are subscribed, perhaps most of the resources should be dedicated to keeping this core set as fresh as possible. In context of this question there is some recent work by Richard Sia on this topic: Efficient Monitoring Algorithm for Fast News Alert, with Junghoo Cho and Hyun-Kyu Cho, in IEEE Transaction of Knowledge and Data Engineering (PDF). They model the posting patterns of the RSS feeds and optimize multiple fetches to minimize the delay in indexing.

But one question that comes to my mind is that of the tradeoffs between index freshness and quality. One could index very few feeds and ensure freshness at the cost of quality. On the other hand one could index a large number of feeds and increase the delays in indexing. What is the optimum balance between these two? How do you incorporate the number of users who subscribe to the feed in the (re-)crawl prioritization algorithm? Can recent link activity prioritize recrawl of feeds?

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.

I/O efficient computation of First Order Markov Measures for Large and Evolving Graphs

Live blogging from WebKDD 08:
I/O efficient computation of First Order Markov Measures for Large and Evolving Graphs
Prasanna K Desikan and Jaideep Srivastava

This paper addresses

• Disk IO for single iteration
• Num of iterations to converge

in pagerank computation.

Typical method is to do binning of the vectors so that the vectors are accessed as blocks in the graph. This requires more IO but low memory. The approach presented in this paper is to make used of the structure of the graph in a divide and conquer like fashion (sort of like community detection).

A related paper I recalled during this talk is:

Local Approximation of PageRank and Reverse PageRank

 Further the paper presents an approach for dynamic, evolving graphs that takes advantage of the fact that subgraphs can have a faster convergence rate. Their approach provides about 20% improvement in time efficiency. 

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.