Link Prediction

Given a snap shot of current network over a set of nodes, link prediction is method of identifying which new links that are likely to occur in the near future. In a graph with huge number of nodes, identifying the potential nodes that a given node gets attached to in near future is a non trivial task. Typically, these problems are solved by coming up with some kind of "proximity" measure (like Page-Rank score) for the nodes in the graph, and predicts that the links being formed with nodes having higher proximity measures. Seminal paper which describes the problem is here Kleinberg