Link Prediction in Social Networking


Many social, biological, and information systems can be well described by network. Where nodes represent individuals, biological elements (proteins, genes, etc.), computers, web users, and so on and links denote the relations or interactions between nodes.
A network is represented by a mathematical structure called a graph. Where a graph G is a structure consisting of a set of vertices V (also called nodes), and a set of edges E (also called arcs or links).Great efforts have been made to understand the evolution of networks (by R. Albert, A.-L. Barab ́asi). Social networks are very dynamic objects, since new edges and vertices are added to the graph over the time. Understanding the dynamics that drives the evolution of social network is a complex problem due to a large number of variables. But, a comparatively easier problem is to understand the association between two specific nodes. Hence we predict the likelihood of a future association between two nodes, knowing that there is no association between the nodes in the current state of the graph. Predicting certain changes to a social network is called the link prediction problem. Liben-Nowell & Kleinberg (2003) explain it as:

Given a snapshot of a social network at time t, we need to accurately predict the edges that will be added to the network during the interval from time t to a given future time t'  where  t < t' .

Link prediction has also many applications outside the domain of social networks. For example, in e-commerce it can help build recommendation systems; in the security domain link prediction identifying the structure of a criminal network (i.e., predicting missing links in a criminal network using incomplete data); in bioinformatics link prediction can be used to find interactions between proteins etc.

SpeakerKushal Veer Singh,
Research Scholar, SCIS, JNU

Venue:  Committee Room, Central Library, JNU

Date and Time: 18th February 2014 (Tuesday), 4:30 pm