Social Media Research Blog

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?

Ranking Nodes via Random Walks

A few days ago, we were discussing a research problem in the lab. It reminded me of two papers I had recently read. The problem that we were talking about involved a graph where we knew certain nodes of interest and wanted to identify and rank other nodes that might be relevant. This is a classic example of a situation where random walks can be quite effective. Following are brief summaries of two papers on this topic:

The first paper titled "Ranking on Data Manifolds" is by Dr. Dengyong Zhou. It is discusses a neat interpretation of a random walk. Following excerpt from the paper describes the basic intuition:

"We firstly define a weighted network on the data and assign an authoritative score to every query. The query points act as source nodes that continually pump their authoritative scores to the remaining points via the weighted network, and the remaining points further spread the authoritative score they received to their neighbors. This spreading process is repeated until convergence, and the points are ranked according to the amounts of authoritative score they received."

Manifold is defined by Wikipedia as:

an abstract mathematical space in which every point has a neighborhood which resembles Euclidean space, but in which the global structure may be more complicated.

(rdfs:seeAlso Wolfram page on manifold)

So basically, one can think of a graph or a social network as data that lies on a manifold. In order to learn and capture the structure of the manifold a the Laplacian Matrix is used to represent the original graph. The advantage here is that the Laplacian is capable of capturing the long range relations between the nodes and ensures overall smoothness when propagating the scores on the manifold.

As the scores are iteratively spread from the nodes of interest to the neighbors (via the graph laplacian), the algorithm converges and corresponds to the random walks in the graph. The final scores provide the overall ranking of the nodes, with respect to the initial nodes of interest. The applications of this method range from image processing to web search and recommendation.

I really like this paper for its simplicity and clarity in explaining the connection between random walks and node ranking.

The second paper I would like to mention here is "Fast Random Walks with Restart and its Applications" by Hanghang Tong et al. It is a really nice paper that talks about how random walks can be used to identify how close two nodes are in a graph. Moreover, the paper discusses some really neat mathematical tricks that can be applied for efficient, "on the fly" computation of the random walks in large graphs.  The basic intuition is to use the Sherman-Morisson Lemma to avoid directly computing the inverse of a large graph (which is prohibitive). This is actually a superb trick to use, especially when doing rank one updates. A number of applications are discussed in this paper, including image retrieval and neighborhood formation etc.

There is a more recent work by Alekh Agarwal and Soumen Chakrabarti on this topic, "Learning Random Walks to Rank Nodes in Graphs". There are many more papers and I have probably not read them all -- these are just a few of my favorites on this subject.

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.

Query-log mining for detecting polysemy and spam

Live blogging from WebKDD, 2008:

Query-log mining for detecting polysemy and spam
Carlos Castillo, Claudio Corsi, Debora Donato, Paolo Ferragina, and Aristides Gionis

The paper presents an approach to identify spam from both query logs and usage. The queries are a way to obtain the wisdom of the crowds. This information is used to  tackle spam detection and identify polysemy.

The sources of information used by the authors were:

• Query graphs: query to matched documents
• click graph: query to clicked documents
• view graph : The set of matches that were viewed
• anti-click graph (if the user skipped one of the previous documents from the top 3). This can be thought of as negative feedback.

Further feature extraction  & topics are identified from web directory. The intuition is

"documents that attract queries on many topics and queries have the potential of being spam."

Syntactic features used were: degree of node; the top query terms a document attracts.

Topics are propagated in the click graph using categories from dmoz to queries in the bipartite graph. Two approaches are used for the propagation: weighted avg and topic specific pagerank.The query logs were obtained from Yahoo! and labeled spam collection is WEBSPAM-UK2006 collection.

It was interesting that many polysemous queries were actually country names. For spam detection content + link + usage obtained the best results which was almost same as link+content. 

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.

Where is a Company Located?

Geographic information is an important factor in social media analysis. In this post I used Google's super cool new service Google Insights to identify in which state a company is located. It indeed matches quite well with either where the company is headquartered or where it has its production facilities.

Let us look at the search popularity for a few companies:

General Motors

 

Intel

 

Dell

Home Depot

 

Berkshire Hathway

 

Moreover, this also applies pretty well to other named entities:

Joe Biden, Senator Delaware

Bill Richardson, Senator New Mexico

I hadn't expected that for company names this would work so well. I was thinking that most of the search volume for corporations would be biased towards NY due to the stock markets. 

This is pretty awesome and I hope that there is a Google Insights API to be released soon. :-)

Del.icio.us + Google Custom Search = Delizzy

In my April 9, 2008 blog post on "Social Tagging and Vertical Search" I had talked about exactly this idea:

For quite some time now I wanted to build a mashup using the social tagging information from del.icio.us and combine it with Google's Custom Search engine. This is a neat way to build high quality vertical search engines. (For example we could use all the URLs under the tag "astronomy" to build an astronomy vertical).

Well, it was just waiting to happen. Delizzy (via Techcrunch), is a wonderfully simple idea but it is a super cool site built using del.icio.us and Google Custom Search. It lets you do what del.ico.us has surprisingly, still not yet provided -- A full text search over your bookmarked items. I believe this could be taken a step further and built into custom search engines or verticals for different topics. Imagine searching over only highly bookmarked sites for a particular topic like "AJAX" or "Ruby on Rails" or "Artificial Intelligence".

In any case Delizzy is pretty cool. Go check it out!

Wikimatix: Wikify and Disqus Hot Search Keywords

Introducing WIkimatix.com: A mashup for wikifying Google Trend's top search keywords. Moreover you can "disqus" and comment on recent hot topics being searched for right now!

Yesterday, while taking a break from writing my dissertation I was looking at the top search terms over at Google Trends. Few things immediately came to my mind:

1. I am a Wikipedia and News junkie -- no surprise there! Sometimes, I do not know a whole lot about the top search trerms and have to look up the wikipedia entry to refresh my mind about the topic or person. BTW, have you noticed that so many of the top terms are named entities? I also spoke about this in my earlier post on Intrestingness and Feshness in Search.
2. Google trends does not have an ability to discuss. I wanted something where I could comment on the terms in a digg like fashion? Perhaps talk to everyone about what I think of this whole "Big foot thing in the news". (Tip of the hat to the awesome widgets powered by Disqus)
3.  Finally, I would like to know exactly why something is in the News or has made it to a top 100 list. I just want a one or two line snippet/summary and a pointer to the most authoritative blog post/news piece about this keyword. While Wikimatix currently does not provide this -- it is something that can be easily extended.

Well, this was a quick hack ( ~150-200 lines of code; ~2 hours) and is meant to be a prototype/proof of concept idea. I think there can be a lot one can do with the idea of capturing the buzz using query logs and having discussions around the search terms and the latest news.

Note: Wikimatix updates itself every two hours. The disqus pages are associated with the individual search term and thus can be accessed even after the term is no longer buzzy.

Some possible improvements that might be good:

• Group related search terms like "big foot", "big foot discovery" etc
• Name disambiguation can be a problem. Sometimes the right person's Wikipedia entry is hard to determine without the context of the story.
• Simple heuristics might work rather well to identify the top categories that are in the news. For instance, today it is all about "Big foot", "Olympics" and a few other major events.
• For search terms, there might be a good video, photograph associated with it. It would be cool to display that as well.

DERI/NUI boards.ie SIOC Data Competition

Following Announcement is Via Dr. John Breslin spotted on W3C's Semantic Web Mailing List:

The Digital Enterprise Research Institute (DERI) at NUI Galway is running a unique competition from 1st August to 30th September 2008 in conjunction with
boards.ie, Ireland’s largest discussion forum site. The competition is an open contest in which entrants can win over €4000 in Amazon.com vouchers by submitting an interesting creation based on an RDF data set of discussion posts from boards.ie over the past ten years:

* The first prize is an Amazon voucher for $4000 (~€2500)
* The second prize is a voucher for $2000 (~€1250)
* The third prize is a voucher for $1000 (~€625)

Read the rules and find out more information on the contest at:

http://data.sioc-project.org/

The data set (approximately 9 million documents) has been represented in the Semantically-Interlinked Online Communities (SIOC) RDF format developed by DERI, NUI Galway for expressing the information contained in social websites (forums, mailing lists, blogs, etc.). Entrants may create whatever they feel is interesting based on this data: it could be a novel web application that makes use of the data set, a report on analyses performed on the data, a tool that allows one to visualise or browse the semantic structure, or whatever else the imagination can come up with!

This event is duly noted in the Social Media Events Calendar.

Clustering Triples from Social Data

By far, the most prevalent data available in social media is tagging information. For example, in del.icio.us a user may tag a URL or in Flickr she may tag an image. One of the questions that comes up is how to then cluster social data that is rich in tags. Some techniques available ignore the user information and use only a bipartite graph consisting of tags and URLs. Another method is to represent two pieces of evidence (user-tag;tag-blog) in a tripartite graph (where nodes are of three different types: users, tags and urls). However, even this type of structure actually  misses the higher order relation between the three nodes. Note that the information available is really in triples of the type <user, tag, url>. This information is not captured by the tripartite graph model. In particular, two users may be connected via a common tag even if the actual URL they bookmarked is vastly different.

There are some techniques using Tensor Matrix Factorization that can handle such data. However, the question of how to deal with triple (or higher) information from social data is quite interesting. Moreover, being able to do so efficiently and in an online fashion would also be important. I believe that this topic may be of significant interest in the upcoming social media and data mining conferences. The implications of these techniques would be in building better recommendation systems and personalization algorithms.

[Thanks Vlad Korolev for some of the discussions related to this post]