The Link Prediction Problem

Posted by

Today we are going to discuss an old but very important problem known as The Link Prediction Problem. The link prediction problem was introduced back in 2004 but its applications are still widely used that we encounter in our day-to-day lives without noticing. In this post, I’ll try to cover the basics of this problem but if someone needs additional topics on this problem please feel free to drop a comment about the same.

Problem Statement: Given a snapshot of a social network at time t, can we predict which new interactions are likely to occur during the interval from time t to a given future time t’.

The problem of predicting the existence of hidden links or of creating new ones is commonly known as Link Prediction Problem. 

Online social networking sites have become increasingly popular over the last few years. As a result of the enormous growth of these networks has resulted in several research directions that examine the structural and behavioral properties of large-scale networks.Social networks are highly dynamic, they grow and change quickly over time through the addition of new edges, signifying the appearance of new interactions in the underlying social infrastructure.

Hence, Social networks are a popular way to model the interactions among the people in a group or community.They can be visualized as graphs, where a vertex corresponds to a person in some group and an edge represents some form of association between the corresponding persons.

The specific problem instance is to predict the likelihood of a future connection between two nodes, knowing that there is no association between the nodes in the current state of the graph. This problem is commonly known as the Link Prediction problem.

Natural examples of social networks include:

  1. the set of all scientists in a particular discipline, with edges joining pairs who have co-authored papers
  2. the set of all employees in a large company, with edges joining pairs working on a common project
  3. a collection of business leaders, with edges joining pairs who have served together on a corporate board of directors.

Applications of Link prediction:

  1. In bioinformatics, link prediction is used to find interactions between proteins.
  2. In the area of Internet and web science, it can be used in tasks like automatic web
    hyperlink creation[3] and web site hyper-link prediction.
  3. In security-related applications, it can be used to identify hidden groups of terrorists and criminals.
  4. In e-commerce, one of the most prominent usages of link prediction is to build recommendation systems.
  5. In bibliography and library science, it can be used for de-duplication and record linkage.
  6. Researchers in artificial intelligence and data mining have argued that a large organization, such as a company, can benefit from the interactions within the informal social network among its members.
  7. Detection of hidden links is also very practical in friend suggestion mechanisms used by online social networks.

Methods of link prediction:

  • Methods based on node neighborhoods:

  1. Graph Distance
  2. Common neighbors
  3. Jaccard’s coefficient
  4. Adamic/Adar
  5. preferential attachment
  • Methods based on the ensemble of all paths:

  1. Katz
  2. Hitting time, PageRank, and variants.
  3. SimRank

One of the main challenges of link prediction concerns the evolution of Internet-scale social networks like Facebook, mySpace, Flickr, and so on.

Since the Link Prediction problem is relevant to different scenarios, several algorithms have been proposed in recent years to solve it.Most of the solutions are generally based on supervised machine learning and selecting relevant features, Bayesian probabilistic models, relational Bayesian networks, or linear algebraic methods.

The existing link prediction techniques lack the scalability required for full application on a continuously growing social network. The primary bottleneck in link prediction techniques is extracting structural features required for classifying links.

If you are interested in studying the topic further with the help of research papers, then please visit our EazyProjectz blog for other information.

 

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s