Theory Tuesdays -- What do Wikipedia, car-pooling, couch surfing, and social bookmarking have in common?

Last fall, I worked for four months in Google, Zürich. It was a fun and enriching experience, indeed. The opportunity to learn and contribute to the technology that is used by millions of people daily is quite exciting.

Besides enjoying the Google-life, during my days in Zürich, I was invited by two artist friends, Silvan Käelin [1,2,3] and Philip Matesic [4,5,6]), to give a talk about my PhD thesis research at Perla Mode -- as part of the Theory Tuesdays project.

Philip organizes a weekly event at Perla Mode named Theory Tuesdays. The goal is to bring together artists, researchers (of multiple disciplines), and the public to discuss a variety of topics such as art, technology, society, and their intersection.

I received the invitation with surprise and interest. It was a new experience to talk to an audience completely outside my field of research. Also, it was a chance to receive feedback (from such non-technical group) about what I think it is a relevant topic of study.

The idea was to have a middle ground between what I have been investigating (i.e., techniques to assess the value of contributions in peer production systems [pdf]) and a the broader topic that could interest the attendance.

Therefore, it seemed appropriate to introduce the notion of peer production systems [7], hint the questions I am interested in answering in this context, and asking the participants related questions such as: how do they perceive the value of information they consume online? do they often perceive themselves contributing to others by producing information online? what is the main incentive to do so? What are the aspects they take into account to decided whether an information provider produces value to them?

I am glad that the "talk" turned into a lively conversation about about all these questions and other aspects related to online peer production. We covered topics from the basic notion of social production (and why it works so well in certain scenarios), passed through specifics about the utility of tagging (e.g., classification languages may emerge through collaboration), and talked about the intuition behind the techniques I am designing to assess the value of contributions in social tagging systems.

Although anecdotal, it was possible to observe from the discussion two explicit trends on the perception of value of online peer-produced information: novelty and trust on the information producer. These aspects came up in the discussions as crucial to the users to assess the value of peer-produced information. It is important to note that the information consumer's interest is an implicitly aspect considered in the value assessment.

The observations are somehow intuitive, but for me it was quite important and helpful to have a first-hand discussion with the real users of the systems I study. It does help one to tune the questions to ask and where the relevancy of one's research. I hope to have more opportunities like this. Thanks to Silvan and Philip for the first one.

References:

[1] One Man
[2] Lagoa do Ouro
[3] Temps de Poussiére (Time of Dust)
[4] An Bonus
[5] Mau Series
[6] To Don Pedro with Mr. Gonzalez
[7] Y. Benkler. "The Wealth of Networks: How Social Production Transforms Markets and Freedom"

The Small World of File Sharing

The IEEE TPDS has recently published a preprint of an interesting piece of work that I had the pleasure to collaborate with.

Adriana Iamnitchi, Matei Ripeanu, Elizeu Santos-Neto, Ian Foster, "The Small World of File Sharing," IEEE Transactions on Parallel and Distributed Systems, 28 Sept. 2010. IEEE computer Society Digital Library. IEEE Computer Society.

Abstract:

Web caches, content distribution networks, peer-to-peer file sharing networks, distributed file systems, and data grids all have in common that they involve a community of users who use shared data. In each case, overall system performance can be improved significantly by first identifying and then exploiting the structure of community's data access patterns. We propose a novel perspective for analyzing data access workloads that considers the implicit relationships that form among users based on the data they access. We propose a new structure —the interest-sharing graph— that captures common user interests in data and justify its utility with studies on four data-sharing systems: a high-energy physics collaboration, the Web, the Kazaa peer-to-peer network, and a BitTorrent file-sharing community. We find small-world patterns in the interest-sharing graphs of all four communities. We investigate analytically and experimentally some of the potential causes that lead to this pattern and conclude that user preferences play a major role. The significance of small-world patterns is twofold: it provides a rigorous support to intuition and it suggests the potential to exploit these naturally emerging patterns. As a proof of concept, we design and evaluate an information dissemination system that exploits the small-world interest-sharing graphs by building an interest-aware network overlay. We show that this approach leads to improved information dissemination performance.

Object-to-Object Similarity

Recently, I read a paper published at VLDB'2008 titled: Accuracy Estimates and Optimization Techniques for SimRank Computation by Lizorkin et al. [1].

In summary, the paper studies a specific algorithm -- SimRank -- that determines similarity scores between objects by augmenting an available link structure that connects the objects (e.g., hyperlinks between pages, friendship links in online social networks, similar tags between photos in Flickr). The intuition behind SimRank is that "two objects are similar if they are referred to by similar objects".

As the title indicates, the work contributions can be divided into two parts: 1) it provides accuracy estimates for the iterative computation of SimRank scores; and, 2) it proposes and analysis three optimization techniques that reduces the computational complexity of the original algorithm from O(n^4) to O(n^3).

One point, which seems to need a deeper investigation, is whether the similarity scores produced by SimRank have high quality (by quality I mean they do capture the true similarity between objects). Indeed, the original SimRank work by Jeh & Widom [2] and Lizorkin's paper lack a discussion (and experiments) on the quality of scores.

Nevertheless, the beauty of Lizorkin's paper resides on the fact that the proposed optimization techniques may be helpful in other contexts, though they originate from a specific context -- improving SimRank. In the following, I briefly describe the intuition behind each optimization.

Essential nodes -- by exploiting the graph structure, the authors are able to define the set of essential nodes of a particular node v, and more importantly, to prove that if a given node b is outside the set of essential nodes of v, the similarity score between them is zero. It turns out, that computing the set of essential nodes is much cheaper than computing the similarity score. Hence, it leads to the first optimization.

Partial sums -- SimRank similarity is recursive by definition. This implies that the similarity score of between some pairs may be reused (without recomputation) to compute the similarity between several other pairs of nodes. The idea applied here was to use memoization to reduce the cost of computing parts of the sum in the computation of a final score. It occurs to me that memoization may be good even in a dynamic graph (i.e., a graph that changes over time), depending, of course, on the trade off between accuracy of the scores and the computational cost implied by the recomputation.

Threshold-sieved similarity -- here, the idea relies on the fact that setting a minimum threshold on the similarity that should be considered enables a reduction in the number of node pairs that the similarity have to be computed. The interesting point is that the threshold does not break the relative ranking between similarity scores, as one could expect due to the fact that some nodes are discarded.

Currently, I am investigating the applicability of one or two of the techniques above in a problem that I have in hands now. More about it soon.

References:

[1] http://www.citeulike.org/user/elsantosneto/article/6509946
[2] http://www.citeulike.org/user/ldietz/article/349900

Relationship between cross-field citations and work impact

A recent work by Shi, Adamic , Tseng and Clarkson has an interesting analysis on the relationship between works that draw from different areas (i.e., cite papers outside their fields) and their subsequent impact. [1]

One of the interesting bits:

[...]
Intuitively, any individual citation will at most have a very weak impact on the success of a citing paper. It will only be one of possibly dozens of references made in an article or patent. Other factors, such as the publication venue and the reputation of the authors, are more likely to contribute to the impact of the article than any individual citation the authors include. We nevertheless see a significant relationship between the interdisciplinarity of citations and the impact of the publication.
[...]

This reminds me of previous results on the relationship between network constraint and value of ideas [2]. The intuition is that a person who is in a bridge position in her social network (i.e., connecting two distinct groups) is more exposed to different ways of thinking, which may lead to that person having more valuable ideas. Here, the social network is the citation network, and the bridges are papers that cite otherwise unconnected clusters (i.e., fields).

A recipe for higher impact research?

[1] Shi et al. 2009. The Impact of Boundary Spanning Scholarly Publications and Patents. PLoS ONE.
[2] Burt, R., 2003. Structural Holes and Good Ideas. American Journal of Sociology.

Scientific Data For All!

The Wired Blog is running a brief article about yet another Google's initiative. The idea is to provide storage, and as far as I understood, free access to scientific data sets.

One interesting point of the article is the following:

(Google people) are providing a 3TB drive array (Linux RAID5). The array is provided in "suitcase" and shipped to anyone who wants to send they data to Google. Anyone interested gives Google the file tree, and they SLURP the data off the drive. I believe they can extend this to a larger array (my memory says 20TB).

It sounds exciting that in the near feature, we might have access to a long list of data sets. Perhaps, under a standard API. If you like buzzwords, this might be named (if it is not the case already) -- Science in the Cloud. Despite the name they will give to this, this initiative can bring a long list of advantages for the the scientific community, I think.

Finally, I wonder when the RFC for the "suitcase-based transport protocol" will be available (similar to RFC 1149). :-)

On The Repeatability of Experiments

As someone with an experimental background, I have found this initiative by the organizers of PODS/SIGMOD quite interesting.

In their page about guidelines for research papers, the program committee not only present the format guideline, but also a set of steps to help the committee to assess the "repeatability level" of an experimental research.

From their page:

...
we attempt to establish that the code developed by the 
authors exists, runs correctly on well-defined inputs, 
and performs in a manner compatible with that presented 
in the paper.
...

Happy 1st of July

For many reasons, my interest over virtual worlds is increasing everyday. Currently, the attention relies on the characterization of large scale distributed systems perspective, than from a business perspective (which is may be very interesting too!).

In the Scientific American's blog, Christopher Mins comments on a talk delivered by Mitch Kapor (among a list of activities, he is also investor and chair of Second Life).

The most interesting aspect of this talk, which seems natural to me, is the suggestion that Kapor (also as a chair of the Mozilla Foundation) defends the creation of open standards for virtual worlds.

It would be cool to think of a protocol design to allow interoperability among virtual worlds. Although this seems to be a classical software engineering problem, the requirements posed by virtual worlds (including the demand for monetary transactions) may be unique enough to create new research opportunities.

By the way, happy 1st of July. :-)

Rethinking your role...


The BBC has published this article about a petition by European institutions requesting a that all government funded research should be easily available to the public - you can read the article here http://news.bbc.co.uk/2/hi/technology/6404429.stm.

Particularly, the idea of providing open access to government funded research publications seems a sensible move. However, the whole picture is a bit more complex, I guess. The article nicely points out what it may be the fundamental question regarding the discussion on "To Open or Not To Open", which is the role of researchers in disseminating information.