Link Prediction in Social Networks

1. Introduction

Every kind of social group can be represented in terms of units or actors, composing this group and relations between these units. This kind of representation of a social structure is called Social Network. In a social network, every unit, usually called ``social units” like a person, an organization, a community, and so on, is represented as a node. A relation between two social actors is expressed by a link. So every social network can be represented by a graph. The recent research on networks, a huge amount of attention has been devoted to social networks and its structures whose vertices represent people or other organization in a social network, and whose edges represent influence between vertices or collaboration. Examples of social networks include the set of all researchers in a particular subject such that edges are joined who have co-authored papers; a collection of businesspersons such that edges are joined who have shared together on a board of directors. Social networks are highly data based objects; they increase and change rapidly over time through the addition of new vertices and edges. Understanding the pattern by which they are joined is an important question that is still not answered, and it creates the motivation for this chapter here. This chapter will discuss about link prediction problem in social network. Suppose, a snapshot of a social network is given at time, accurately prediction of the edges will be proposed such that the edges will be joined to the network during the interval from that time to a given future time. Suppose, a co-authorship network is considered among researchers. There are certainly many reasons, that why two researchers who have never written a paper together, will write a paper in the next years: they may be geographically close when any of them changes institutions. Such types of collaborations can be hard to predict. Our goal is to make this prediction precisely, and to compare which measures in a network solve to the most accurate link predictions. The problem of link prediction across associated networks include anchor link prediction problem and link transfer through associated heterogeneous networks. This chapter summarizes recent growth about link prediction and survey of all the prevailing link prediction techniques. There are many problems to predict accurate links. First of data sparse, missing data or relationship is one of the main obstacle of the system. Imbalance is another possibility for researchers. There are so many possibilities with few choices. Link prediction problem is referred as inaccurate problem due to low accuracy in practice. Another obstacle is accuracy with scalability. Appropriate modelling is required for good prediction.

As part of the recent survey of research on large, complex networks and their properties, some amount of attention has been devoted to the computational analysis of social network structures. The availability of large, detailed datasets encoding such networks has stimulated extensive study of their basic properties, and the identification of recurring structural features. Social networks are highly dynamic objects; they grow and change quickly over time through the addition of new edges, signifying the appearance of new interactions in the corresponding social structure. Understanding the mechanisms by which they evolve is a fundamental question that is still not well understood, and it forms the motivation for our work here. Some basic computational problem underlying social network evolution, the link prediction problem are studied here.

The motivation of this chapter is recommending new friends in online social networks, suggesting interactions between the members of a company/organization that are external to the hierarchical structure of the organization itself, predicting connections between members of terrorist organizations who have not been directly observed to work together, suggesting collaborations between researchers based on co-authorship. Given the links in a social network at time t or during a time interval, to predict the links that will be added to the network during the later time interval from time to some given future time. This chapter will discuss different types of methodology and techniques applied to find link prediction in a social network.