Link Prediction in Complex Networks

1. Introduction

Link prediction has attracted the attention of many researchers from different research fields. It consists of estimating the likelihood of existence or appearance of an edge between two unlinked nodes, based on observed links and attributes that contain information about the nodes, edges or the entire graph. It has important applications in many fields including social, biological and information systems etc. Link prediction has been widely used in biological networks like protein interaction network, metabolic networks, food web. It is used for finding missing links and thereby helps in reducing the experimental cost if the predictions are accurate. In social interaction and academic or commercial collaboration networks they can play an important role to predict new associations (new edges). This further has utility in recommendation task: a service provided by almost all social networks and majorly used in e-commerce sites. Link prediction can also be helpful in finding hidden links in criminal networks, which is another critical field of research. Link prediction can be basically of two types: structural and temporal.

• •

  Structural link prediction refers to the problem of finding missing or hidden links which probably exist in a network (Liben-Nowell & Kleinberg, 2007; Menon & Eklan, 2011; Taskar et al., 2003; Yin et al., 2011). It focuses on inferring the existence of links that are not directly visible, by using observable data of the network. It has direct application to find unobserved patterns of genes, protein interactions for the medical studies on various diseases like cancer, HIV, Alzheimer etc. (Airoldi et al., 2006; Eronen & Toivonen, 2012). It can also help to find existing criminal links which often remain hidden in a network (Clauset et al., 2008; Fire et al., 2013).

• •

  Temporal link prediction refers to the problem of finding new links by studying the temporal history of a network (Benchettara, Kanawati, & Rouveirol, 2010; Hasan, Chaoji, Salem, & Zaki, 2006; Berlingerio et al., 2009; Hasan et al., 2006; Huang & Lin, 2008; Liben-Nowell & Kleinberg, 2007). So here we have information about the network till time t and the goal will be to predict a new link that may appear at some point of time in future say t+k. It has its application primarily in recommendation systems that are being used widely in e-commerce websites for product recommendations, in any search engines to help users with probably relevant terms they might be searching, for recommendation of tags in social resources sharing websites like Flickr¹, YouTube², De.li.ci.ous³ etc. and very commonly used for recommendation of friends in many social networks like Facebook⁴ and Twitter⁵. It has another significant use in predicting future collaborations between researchers for academic purposes (Benchettara et al., 2010a,b; Kunegis et al., 2010).