Similarity-Based Indices or Metrics for Link Prediction

Introduction

The history of evolution of network structures had been studied by several mathematicians’ long back. Eulars theorem of graph theory was first of its kind which we can say solved initially the problem of seven bridges given by Konigsberg (Biggs et. al. 1986). Since then the field of graph theory and research in this area was handled by mathematicians quite effectively. Knowledge retrieval and processing techniques now a days are pretty useful in crunching voluminous data captured via internet (Khamparia & Pandey 2016, 2017). Rule extraction

A social network is a network of people connected with each other resembling some kind of relationships in between over the internet, in other words we can say it is typically represents a social structure consists of social actors having association between these actors. These social networks are represented through graphs where the actors referred as nodes (users/individuals/organizations/cities, etc.) and association in between referred as edges also known as links (relationships/interactions/associations/ties). Earlier before the inception of internet the communication and cooperation between people was not convenient and fast but due to rapid development since then it has become so and the social networks have evolved quite significantly. The social networks now transformed into online social networks such as Facebook, Twitter, and LinkdIn, are now became an integrated part of human life. These (OSNs) online social networks are providing platforms for exchanging formal and informal information with each other. As a result of that huge database or voluminous data is getting piled up exponentially. the data incurred has obvious characteristics and attributes if exploited can generate useful information for further use to create certain recommendation system, lot many researchers are now paying attention to social network analysis for extracting valuable knowledge for better services to the society. The nature of these kinds of networks is quite dynamic with new edges and nodes are adding to the graph over the period of time. Comprehending and understanding the evolution of OSN is typically a complex challenge due to range of parameters. An instance of social network evolution could be easier problem to understand and link prediction (Liben-Nowell and Kleinberg, 2003) is one such instance where association between nodes is to be predicted. For example the questions to be answered can be how does the relationship between nodes changes with respect to time? What could be the factors affecting this relationship? What kind of influence nearby nodes can put on the relationship of associated nodes? Ultimately the problem here in this chapter is an effort to trace out the metrics involved in prediction of likelihood of future links between nodes.

The Graph

Any problem which is imitated mathematically can be analyzed and solved using computing facilities even when the scale of the problem is significant and difficult to understand and comprehend. The size of social networks is increasing exponentially and so is exploiting the data and information captured directly and indirectly by these networks. These networks created online and can be represented through a mathematical structure known as graph. It has a structured representation having set of vertices (nodes) V and set of links (or edges) and typically written as G=(V,E). As discussed above vertices (nodes) represents people and edges or links between them as relationships between people. edge or link is designated with letter e such that e belongs to E connecting set of two nodes from V. for example V = {a, b,c,d,e} and E{e1,e2,e3,e4, where E = ({e1= a,b},{e2=c,d},{e4=a,e}). In order to illustrate it further it says the graph is collection of five distant people named as a,b,c,d and e. a and b are friendly with each other, similarly c-d and a-e. It is illustrated diagrammatically.

Figure 1.

Demonstration of nodes and links in graph

Sociologist usually call such diagrams as sociograms and in the field of research domain terms like network, social network, sociogram, graphs are interchangeable. The links in the network are undirected or bi-directed which means the exchange of information would be from both sides (ex: exchange of messages, emails, etc.) . In order to explore the graph theory is recommended in (Wilson, 1996).