Sitting in the student center of our university, I am surrounded by hundreds of students enjoying their lunch and socializing. They’re strengthening (and in some cases weakening) their social ties. Given the ability to observe this social network over time, we would see that some relationships flourish, while others disappear altogether.

This situation is not unique to university students. In fact, whether we’re studying the spreading of an infectious disease, or the growth of an organized crime network, the reality is that the relationships in these social networks are dynamic. They change. Being able to describe the current state of a network is important. Our goal is to predict the future state of the network by forecasting who will connect to whom. If we could make these sorts of predictions, then we may be able to better recommend or warn of future probable links, as well as come to understand mechanisms which may be driving the evolution of the network.

This brings us to the link prediction problem. Liben-Nowell and Kleinberg defined it as follows:

The link prediction problem asks, "Given a snapshot of a network at time t, can we predict new links which will occur at time t+1?"

In our work, we explore how topological similarity indices of a network can be combined with node specific data to develop a link prediction tool. Rather than pre-supposing that all similarity indices are of equal importance, we employ an evolutionary algorithm to evolve coefficients to be used in a linear combination of these similarity indices. Our approach has the advantage of being able to detect which similarity indices are more salient predictors and doesn't require any knowledge of the type of network one may be working with.

To test our method, we begin by examining one of the largest social networks in existence, namely Twitter. Below, we visualize the network of reciprocal replies for users who interacted within a single week in late 2008.

Given information about interactions in a given week, we seek to predict links in a future week.

Our evolved predictors exhibit a thousand fold improvement over random link prediction, and a substantial improvement over individual indices used in isolation. The predictor also suggests possible factors which may be driving the evolution of Twitter reciprocal reply networks during the timespan of this study.

Our predictor reveals which topological or user specific indices are most important in link detection for a given a network. For example, index B is most often the top ranking index detected by the predictor, while indices E and I are also important. This type of output can be helpful in detecting the salient features which may be driving the network's evolution over time.

Returning to our original question, we ask: Given a snapshot of a Twitter reciprocal reply network, is it possible to predict the links which will occur in the future?

One approach is to predict a link between all of the people in the network, but clearly this is not the approach we wish to take. For example, in the case of a modestly sized network (say N=30,000 nodes), the number of potential links is roughly half a million! If we're trying to recommend books to a shopper or potential dates to a person using a dating service, we certainly would not want to suggest half a million people for potential dates. It would be nice if we could recommend 10 books (or dates) and have the majority of those suggested links be successful.

In the language of signal processing, we hope to have a true positive rate (e.g., the % of time you're actually right about the links that you predict) that is greater than the false positive rate (e.g., the % of time you've issued a false alarm). This relationship can be captured by the Receiver Operating Curve (ROC) shown below.

The Receiver Operating Curve (ROC) compares the true positive rate (TPR) and the false positive rate (FPR). The ROC curve shown here depicts a classifier (our link predictor) for which TPR>FPR.

The area under the curve (AUC) provides one way of measuring the relative success of one's method. An AUC of .50 suggests that the true positive rate is equal to the false positive rate, while an AUC > 0.50 indicates that the true positive rate is greater than the false positive rate. As shown in the picture above, our AUC is well above 0.50, in fact it is approximately 0.72, which is good!

These results are exciting! We've put together a research paper in which we describe our analysis and algorithm in more detail. Although we focused on Twitter in this investigation, our methodology is general and may apply to link prediction in many other types of time varying networks, such as disease networks or crime. It could also improve the "friends you may know" feature offered by many social networking services.

Here is a short video summarizing our work on link prediction: