Nonparametric Link Prediction in Large Scale Dynamic Networks

Many real-world problem domains generate data in the form of graphs or networks. Examples include social networks (e.g., Facebook), recommendation services (e.g., Netflix or Last.fm), biochemical networks, citation graphs and market analysis. The inferential problem in these settings is often one of link prediction. This problem can be formulated in a static setting where one assumes that a fixed but unknown graph is partially observed, and one wishes to assess whether a pair of nodes that are not known to be linked are in fact linked, given an observed linkage pattern among other nodes. Many real-world graphs are often best modeled, however, as dynamic entities, where links can arise and disappear over time. In the dynamic setting the link prediction problem involves assessing whether two nodes will be linked at time t given the linkage patterns at all previous times. Real-world graphs of current interest are often very large, involving many hundreds of thousands or millions of nodes. The dynamic setting involves sequences of such graphs.