The Online Network Systems Have Become Popular Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Online network systems have become popular in many social, biological and information system in recent year. Much research has been done in social network, which is increasingly growing and form a large complex network. Social network such as Facebook provides a platform for users to share their interest, photos & post etc with their friend. A social network can be well described by a network graph, in which node represents users and edges between nodes represent some association. In most social network links are dynamics and change over the time in network. To predict an association between two nodes in a graph, which is likely to be occur in near future and is termed as link prediction. Many approach and method have been used for predicting a link in past years, a significant interest of the methods uses local and global structure of the graph to make predictions. In this survey we are highlighting the impact of time in association (collaboration or interaction) & temporal behavior of the link between the nodes in link prediction. In this Survey we summarized link prediction without temporal features and Link prediction with time aware features, particularly the relationship between the time stamps of interactions or links and how link strength affects future link creation.

Keywords: Social Network, Link Prediction, Time stamps, Temporal feature, Global features, Local features.


Link prediction is the task of predicting the link in social network which will be formed in near future based on features associated with nodes and links in the social network graph. A social network can be viewed as directed or undirected graph, nodes represents user or entity in a graph and links or edges between them are represented as friendship or some kind of association. Social network such as Facebook, Twitter, Linkedin etc. attracted people to share the picture, send messages to the friends, comments on images and post of their friends, follows other user. Social networks change over the time due to addition of new links between the unconnected pair of node in the social network graph. Online social network provide recommendation of new friend on the basis of various technique of link prediction [2]. Previous techniques for link prediction are based on features of graph structure for social network such as nodes common attributes, shortest distance between two nodes etc. Link prediction is categories mainly under three types of approaches, a node similarity based approach, topological feature based approach and the probabilistic model based approach. Node similarity measure based approaches set their targets as seeking some similarity measurement for the pair of vertices. Topological feature based approach consider graph structure for feature evaluation which consist of local feature based methods such as Common Neighbor, Adamic-Adar, Jaccard's Coefficient etc and global based feature methods such as Katz status index, RWR algorithm, Sim-Rank algorithm, etc. Probabilistic model approach uses co-occurrence probability of two nodes of network which is then used to predict links among the nodes such as local probabilistic graphical model.

Link prediction is task of predicting future links, and the mostly commonly procedure of predicting the link is to consider the graph at two different time interval such as training graph g at time t0 and testing graph g` after some time interval δ i.e. at time t0+δ. Based on training graph the feature is evaluated for the linked node pairs and the for the pairs of node for which the link is to be predicted. After applying the predictors to the training data, the correctly predicted new link data is available. Now the evaluation of link predictor is performed in terms of their accuracy on the basis of testing data. The whole procedure is shown in figure 1.

Temporal Link Prediction

In link prediction various type of feature are used for the task of predicting the future link which solely based on graph structure of static network graph, but now a day's social network grows rapidly with the increasing interest of users which makes the structure of social network graph dynamic, because of the formation of new links and the addition of new users. The previous technique only considered the graph structure to evaluate the feature, but due to social network evolution and dynamic nature this features should be more feasible to predict the links accurately and efficiently. To overcome these feasibility new parameters has to be considered for predicting the links and one of the most significant features for link prediction is temporal feature. Temporal features are dynamic and their value changes as the network change because these features are based on the attribute of nodes and links, such as how long two users are in contact with each other with respect to the current timestamp. Also temporal feature are based on the occurrence of an event which is viewed by and commented by many other users. Time of interaction between the nodes of graph is useful information for constructing the temporal feature [15].

In this article a survey of link prediction technique is discussed based on the type of feature used. Firstly, the link prediction technique based on without temporal feature and secondly, the technique based on temporal feature.


Existing link prediction techniques predict association or link between two node in future using local and global features whereas temporal prediction is evolved as key concepts over time, suppose we have a social network graph in which the timestamp of interaction for node pairs from time t1 to tn is given, by considering this time in link prediction model we can predict the link at time tn+1. In section 2.1 survey on link prediction techniques without time aware based on basic features has being summarized and section 2.2 deals with the survey on the temporal aspect of link prediction.

2.1 Link prediction Without Time Aware Temporal Features

R. N. Lichtenwalter et. al 2012 [4] perform analysis on link and their prediction with newly introduce concept of a vertex collocation (VCP) profile drawn from the generalization and extension of triangle counting approach. A common membership for all the sub graphs on vertices and relations which is describe by the vector VCP.

In [5] presented a learning framework for the heterogeneous and reciprocal link prediction problem. Also addressed the link sign prediction problem in heterogeneous and reciprocal social networks. The experiments shows the method is able to make link predictions and outperforms the use of existing link prediction techniques.

In [3] provided friend recommendations, also known as the link prediction problem, by traversing all paths of a bounded length, based on the "algorithmic small world hypothesis". Experimental results show that our Friend Link algorithm outperforms other approaches in terms of effectiveness and efficiency in all data sets revealing more accurate faster friend recommendations

In [31] considered similarity-based measures, but supplemented the similarity calculations with community information. For many networks ,the inclusion of community information improves the accuracy of similarity-based link prediction methods. Results show that community information often boosts the performance of base metrics.

In [7] Adaptations of popular Link Prediction algorithms for recommending items in large-scale UGCs is shown. Three of the Link Prediction algorithms - Common Neighbour, Adamic/Adar and Katz Measure- performed consistently better than the item-based collaborative filtering technique. Neighbourhood-based methods outperform all other algorithms suggesting that users are mostly interested within a small proximity of their tastes in the user-item space. Rooted Page Rank, on the other hand, was very effective in recommending items that are beyond three hops from users in the user-item graph. Results suggest that Link Prediction algorithms are a more scalable and accurate alternative to classical collaborative filtering in the context of UGCs.

In [21] propose new weighted graph proximity measures for link prediction of social networks also showed that link prediction based on graph proximity measures is suitable for open and dynamic online social networks.

In [16] a Supervised Random Walk based algorithm which trained by an edge strength estimation function that naturally combines the information from the network structure. Random walk is guided by using the edge strength function by incorporating the edge level attribute. The formulation forms a supervised learning that assigns strength to an edge so that the random walk will reach the node for which a link will be created in future. Outcome of experimental result shows that the performance of our method outperforms than an unsupervised approaches and the approaches which is based on feature extraction.

A 2-phase bootstrap probabilistic method is introduced in [33], first phase generates a probabilistic graph and second phase produce final prediction by applying this probabilistic graph-based measures. A cold start link prediction is also introduce for predicting the structure of social network where a network itself missing some information while other nodes regarding information is available.

In [14] developed a supervised learning approach to predict link strength from transactional information. Formulating and investigating new task in social network mining: link strength prediction and compare the utility of attribute-based, topological, and transactional features evaluated the approach on public data from the Purdue Facebook network and show that we can accurately predict strong relationships also shown work on the task of predicting link existence. Results reveals overall performance, achieving 87% AUC.

In [29] an improved weighted proximity measure of link prediction is described. An assumption is made for better proximities for predicting the link that is based on both graph proximity measures and the weights of existing links in a social network. The result shows that in a dense social network this method outperforms as compare to previous approaches.

In [22] presents a supervised learning method that build the predictor which is based upon the structural attributes of the underlying network. In the research a co-authorship data is used in which researchers are nodes and link between them is collaboration. This predictor is test on this data and shows an encouraging accuracy.

In [6] a novel local probabilistic graphical method that can scale to large graphs to estimate the joint co-occurrence probability of two nodes. Topological structure of the network is used to identify the central neighbourhood set of two nodes, and then local MRF model is learned which is constrained on non-derivable frequent item sets. When used in combination with other two types of features - topological and semantic features, we find that the resulting classification performance improves.

In [34] the initial efforts to explore the connection between link prediction and graph topology is represented. They exclusively focused on the predictive value of the clustering coefficient measure. The proposed framework consists of a cycle formation link probability model, a procedure for estimating model parameters based on the generalized clustering coefficients, and model-based link prediction generation.

In [23] a citation prediction system is made using statistical learning that extended inductive logic programming. Their system learnt link prediction patterns from queries to a relational database, including joins, selections and aggregations.

Methods that quantifying the similarity of vertices in networks are consider in [17]. A measure of similarity is proposed based on the concept that two vertices are similar if their immediate neighbors in themselves similar. Which leads to a self-consistent matrix formulation of similarity that can be evaluated iteratively using only knowledge of the adjacency matrix of the network. Test was performed on computer-generated networks their measure is particularly good at discerning similarity between vertices connected by relatively long paths, an area in which more traditional similarity measures such as cosine similarity perform poorly.

In [24] Link prediction of author\document bipartite networks by using clustering is enhanced by the author, also clustered documents by topic and authors by research community in order to generate new entities that were used in logistic regression of features and relations. System tested the data consisting of an equal number of positive and negative cases. Experimental results shows increase in accuracy over models not using clustering by roughly four percent on average.

The predictive power of only proximity metrics are tested which includes common neighbours, the Katz measure and variants of Page Rank [18][19]. Also found some of these measures had a predictive accuracy of up to 16% (compared to a random prediction's accuracy of less than a percent). Liben-Nowell's doctoral thesis was a chapter on link prediction in social networks revealed his hypothesis, that link prediction could be performed from topology alone.

2.2. Link prediction With Time Aware Temporal Features

P. Sarkar et. al 2011 [1] focused on both static and dynamic graph for link prediction. A non-parametric time-series prediction is proposed in this framework, which incorporate the features not based on graph topology. Locality sensitive hashing [] is used for kernel function for fast and scalable implementation. We perform on real world datasets for all the state of the art measures on static and dynamic graphs.

The temporal behaviour, link over strength vary over time and effect of link strength on future link evolution is presented in [15].Also introduced a new method time score a new time aware index for link prediction in social network using supervised learning .The experimental result shows the comparison of performance metric for facebook and co author ship data based on with time score and without time score, revealing that average improvement in precision is 14% the results for recall and f-measure indicate consistent improvement in every year showing average improvement are 11% & 13% respectively.

In [8] considered the problem of temporal link prediction to predict link in T+1 when given data for times 1 through T is known. Matrix and tensor-based methods is used for predicting future links by considering the bipartite graphs that evolve over time, also Katz method for link prediction can be extended to bipartite graphs is shown. From the experimental results the proposed CANDECOMP/PARAFAC( CP method) is able to get an AUC score of 0.845 which is much better than the "Last Period" method's score of 0.686.

As real network traces raise a realization that large connection are inherently varying over time & exhibit more dimensionality than static analysis can capture. In [11] proposed new temporal distance based metrics to quantify and compare the speed (delay) of information in local and global view. Based on the temporal characterize such as delay, duration and time order of contacts (interactions), temporal distance metrics is formed. Result are analyzed based on the varying window size affects on the temporal metrics, observing a higher temporal path length as window size increases where temporal efficiency decreases as window size increases.

In [30] graph based link prediction is developed to incorporate the information on link of network, also elaborated the probabilistic model to include time awareness. The evaluation of temporal features from edge weights is also seen. Results shows that the time stamp of past interaction significantly improves prediction accuracy of new links.

In [32] introduced temporal graph, a representation that encodes temporal data into graphs while fully retaining the temporal information of the original data. Also presented a number of metrics used to study and explore temporal graphs results are analyzed based on the average temporal proximity P, average geodesic proximity G, and temporal availability V. showing all metrics helps the suitability of nodes for receiving or broadcasting the information overtime.

In [28] extended relational technique to temporally evolving domain and represent framework is develop to model temporal and relational dependencies in data. Dynamic relational data are modeled in two phase process, firstly summarizing the temporal-relational information with kernel smoothing, and secondly moderating attribute dependencies within relational information. From the results shown the temporal relational model outperforms the relational model and achieves significant reduction in error from 15% to 70%.

In [25] the problem in static link prediction is highlighted given by Liben Nowell [18][19] as it attempts to predict the evolution of a complex entity over time from a snapshot of the previous time step as the network grows increasingly due to this we need to examine more time step than just the previous one. Experimental results performed reveals that there exist a difference in link prediction and link detection, also it is seen that the static /local metric are not useful and effective for link prediction than the temporal variant of metrics and performs well in different social networks.

In [12] presented a methods for network analysis that explicitly incorporate time and sequence, the method focused on the temporal nature particular temporal link prediction problems, node ranking predicting future event co-participation of entities and rank evolution change in individual rank over time in response to participation in a series of events. An experimental result reveals that prediction of link from event data can be performed using time based method.

In [27] described a method for modelling the relationships that change over time. The historical data are used to develop an understanding for predicting the future interactions. The model can be used to study the behaviour of individual relationships but requires adaptation to model the behaviour of a group of people.

A. Potgieter et. al 2007 [2] found in the study of some network that the existing link prediction technique lowering the accuracy that uses the value of metric in graph and there is no use temporal information in link prediction. We perform an experiment with temporal metric using logistic regression in Weka data mining tool on the online dating network dataset and results are extremely good.

H. R. Sa et. al 2010 [3] present an analysis of supervised machine learning approach for weighted and un weighted network. An experiment is performed on different supervised machine learning technique available in Weka machine learning tool over some predictors, using both with and without weights on co-authorship network data. Previous work on link prediction considered only unweighted network, but if considering the weight of links in network graph a satisfactory results is found.


Social network has raised popularity over the past few years, an link prediction is emerging a fundamental task where various techniques or method are applied for predicting future link formed in the network. One of the main techniques evolved is considering time as key a key aspect named as time aware link prediction. In this survey, link prediction is presented in two categories. Firstly based on the feature for predicting the link uses structural properties of graph such as node degree. Most of previous work related to link prediction is based on local or global feature of the network where the association of the link is considered based on the local feature or small snapshot of the network, also based on the global aspect of network link prediction is performed. Supervised machine learning technique, bipartite networks and probabilistic model for predicting the link using these feature. Secondly, categorizing link prediction is performed on the basis of the time aware temporal feature used by the researcher, where time feature is evaluates the link strength varying over time, the bipartite graphs that evolve over time or probabilistic model to include time awareness etc. Since the single article cannot be a complete review of the research done in the mentioned area because of the wide variety of link prediction application in different research field so only survey based on local, global feature and time aware based temporal feature is used for link prediction is summarized here. In this paper, the contributions of research work done in recent years, in each method were summarized and existing research challenges are also defined. It is hoped that this survey can serve as a useful guide for the researchers interested in temporal based feature attribute that can be used in the recent research work of link prediction and provides a better accurate results as compare to the previous work done. In future work, we will trying to use time aware feature for link prediction framework with some real world data of social network having dynamic nature which change quickly.