Gamers provide heuristic support for complex problem solving

It has occurred to me in the past that it would be nice to harness the inherent abstraction and problem solving skills of humans to better guide heuristics for solving complex problems (such as NP-complete ones). Indeed it would be really cool to let people play some sort of online computer game that acts as a metaphor for an underlying heuristic combinatorial search problem. I was never really sure though, how one could map a combinatorial problem into a visual form that makes the game both engaging and challenging.

Well, according to this post on the nature blog, the bioinformatics researchers at fold.it have done just that by creating a video game in which users help computer to perform the task of protein structure prediction. Interestingly, the game developers didn't set off with the idea of developing a game, but of distributing the workload of search across the idle computing cycles of internet users (like in the SETI@home project). It was only when those users told the researchers that they would like to help/guide the program toward better solutions, that they have the idea to turn it into a game.

In general, I like approaches to harnessing the power of so-called human computation as is done for example in the far less complicated Google Image Labeler.

Everything you ever wanted to know about graph mining for social networks

A colleague of mine Mostafa Keikha pointed me to a very nice survey paper on graph mining and in particular its applications to the Web and social networks. The paper is called "Graph Mining: Laws, Generators and Algorithms" by D. Chakrabarti and C. Faloutsos. It really is very well written and a good read for those interested in partitioning graphs into communities, generating synthetic graphs that look like real ones, analyzing different properties of social networks, etc.