Random Walks on LastFM

By | October 31, 2012

Big social networks don’t often disclose their data to other interested individuals. Their data and users add value to their business. So in order to estimate certain parameters such as the average age or other user characteristics or interests, we need to access the nodes individually.

The way this nodes are accessed depends on the network. In the case of LastFM it is easy to pick a node and from there select one of its friends at random. This technique is called random walk and it generally consists of a path generated by randomly selecting nodes in a network.

As soon as this LastFM crawler travels through a significative amount of nodes, it is possible to estimate an average of the pretended metrics. The problem with this simple implementation is that, although one might think that picking uniformly at random the nodes from within the friends is enough  for them to have the same probability to be accessed, in the global scope, nodes with higher degrees (number of friends) will have higher probabilities to be visited. For example, if we are estimating the number of friends and during the process of picking a friend, the friends with higher degree have higher probabilities of being visited, then the estimated number of friends will be much higher than the real value.

To fix this problem we introduced another type of random walks called RWRW, which, in this case, gives different weights to each nodes metric based on their degree while calculating the average. In this way, while estimating the number of friends, although nodes with high values will be visited with higher probability, their impact on the estimated value will be lower. This technique proved to estimate more accurate results, check in the presentation the graphs and values that we obtained.

Also, I might add that it is very easy to experiment with LastFM using their API : http://www.last.fm/api


Leave a Reply