Link prediction in evolving homogeneous and heterogeneous networks

Complex Evolving Networks are described as networks whose topology change dynamically over time. These networks structures have examples in various areas extending from biochemical to ecological systems. Temporal changes in complex networks can actualize in three different ways including "addition and removal/disappearance of nodes", "addition and removal of links between node pairs" and "modification of node properties/attributes". In complex networks which have a complex organization, the analysis of variance information of nodes and links over time provides vital information compare to the analysis of the static networks. Complex networks delineate various systems existing in nature and society. Protein networks, Internet, scientific collaboration networks, and social/friendship networks can be given as examples for these type of networks. Complex Networks are an area which have still many unknowns and have been frequently studied in recent years. Nodes represent elements in social area and links among these nodes represent interaction between the elements in Social Networks which is a subfield of Complex Networks. Social networks are divided into two substantial categories: homogeneous and heterogeneous social networks. Homogeneous networks include same type of nodes and same type of links between nodes. On the other hand, heterogeneous networks consist of different type of nodes and links, and for this reason; they contain much more rich data compare to the homogeneous networks. Thus, modeling heterogeneous networks is more difficult than modeling the homogeneous networks because of their complex nature. The problem of the link prediction aims to predict the existence probability of a links between node pairs by using network topology, various proximity (similarity) measures and node content information. In the literature, two related types of link prediction problems are considered: missing (static) and temporal (dynamic). In the case of the link prediction problem, it is necessary to estimate the prediction of both new links and repeated links. Although there are several link prediction studies in homogeneous networks using temporal information, there are very few methods available that employ time effect. The main reasons are representation difficulties of the complex structure, rich heterogeneous information, effective usage of influences between multi-typed relationships and the time effect. These characteristics of the evolving heterogeneous networks make link prediction a more challenging task. To overcome these difficulties, link prediction in such networks must model temporal evolution of the multi-typed topological features and link occurrences information of the network structure simultaneously. Consequently, link prediction in evolving heterogeneous networks must be modeled by simultaneous multivariate equations models instead of univariate models. Studies on evolving homogeneous and heterogeneous networks do not mature to a desired level yet. Due to the dynamicity of the network structure and multi-typed topological features, the usage of network evolution for link prediction contains crucial information. Thus taking into account of the changes of topological features over time is very important. In this thesis, we examine models for analysis of time varying information and link prediction models that combine the time information for evolving homogeneous and heterogeneous networks are implemented. Link Prediction method in evolving homogeneous network based on a VAR (Vector Autoregression) Model for Multivariate Time Series forecasting: The first major contribution of the Thesis is the utilization of the network temporal evolution for predicting links between node pairs. The novelty of our approach lies in the method by which we apply Multivariate Time Series model to combine topological similarity measures and temporal evolutions of link occurrences information simultaneously. That enables us to predict repeated link occurrences as well as to identify new link occurrences. A multivariate time series, which involves observation and analysis of more than one statistical variable, is observed in time order. The node similarities and node connectivity information for each pair of nodes in certain time periods are utilized as input to Multivariate Time Series and future similarity measure scores are forecasted. First of all, the network is split into several time-sliced snapshots in experiments, where each snapshot represents the states of the network at different times. Then, unweighted and weighted similarity measure scores between pairs of nodes are calculated for all time-sliced snapshots. A multivariate time series model (VAR) is built for each pair of nodes in consecutive snapshots. Finally, the combination of similarity measures scores and the link occurrences information for each pair are employed as an input to the VAR model then future scores are forecasted. As a second proposed approach, the combination of all similarity measures scores and the link occurrences information between node pairs are used simultaneously and future score values are estimated. VAR is a multiple time series model in which each variable is expressed as a linear function of its own past values. The past values of the remaining variables and each equation coefficients may be estimated separately by ordinary least squares. This superior model provides a systematic way to capture rich dynamics and inter dependencies among multiple time series. In the last stage, the prediction performance in terms of AUC is evaluated on the test set by using the estimated similarity scores. The proposed models outperform the baseline static and univariate time series methods according to the comparison result. Link Prediction method in evolving heterogeneous network based on a VAR Model for Multivariate Time Series forecasting: The second contribution of the Thesis is the proposal of a novel method to solve the problem of link prediction in evolving heterogeneous networks composed of multiple types of nodes and links that change over time and investigate the dynamics of multi-typed links in a heterogeneous social networks. The proposed model based on Multivariate Time Series (VAR) in evolving heterogeneous networks integrates the unweighted and weighted similarity measures scores and link occurrences information and future score values are estimated for all link types. Our implemented model employs the network temporal information, removes the assumption of past existence of a connection which is to be estimated and uses the correlations between multi-typed relationships and similarity measures. Thus, proposed method resolves drawbacks of the existing heterogeneous link prediction methods. The calculated node similarity scores and node connectivity information of node pairs for multi-typed relationships are used as input to Multivariate Time Series and the variation of similarity scores and temporal evolutions of link occurrences are analyzed simultaneously. As a second proposed approach, the combination of all best local (neighborhood-based) and global (path-based) similarity measures and link occurrence information for all link types are employed simultaneously and the model using dynamic relationships of multi-typed relationships is implemented. According to the comparison of the proposed models and temporal link predictors based on univariate time series methods, the proposed approaches outperform the baseline models. Link Prediction method in evolving heterogeneous network based on a multivariate model using the NARX Neural Network: The last contribution of the Thesis is the proposal of a novel method based on Nonlinear Autoregressive Neural Network with External Inputs (NARX) to integrate the temporal changes information for multi-typed links and the similarity measures between multi-typed links in evolving heterogeneous networks. Unlike the multivariate time series model (VAR), the calculated node similarity scores and the frequency of changes (e.g., the creation, preservation or removal of the link between node pairs) in the occurrence of links over consecutive time steps are used as input to NARX simultaneously. The frequency of changes in the occurrence of links include "Link Removal score" that demonstrates the decrease of weight value between the node pairs in the next time period, "Link Creation score" that represents the increase of weight value (increase in number of connections value) between the node pairs in the next time period and "Link Preservation score" that shows the weight value between the node pairs remaining unchanged in the consecutive time period. NARX is an implementation of recurrent dynamic networks with a two-layer feedforward network and is commonly used in time-series modeling. Due to the recurrent dynamic neural network models have feedback connections and the next value of the time series is regressed on previous values of the time series, these models are important for the forecasting of time series. Traditional time series methods require that the series to be stationary which means that the mean, variance and autocorrelation do not change over time. The other significant limitation is that traditional time series methods are only appropriate under the assumption that the time series are generated from linear processes, which is generally not accurate. NARX is a promising alternative to handle these major restrictions. NARX can reveal patterns adaptively from the time series data without prior assumption about the process from which a particular time series has generated. Hence, NARX efficiently models both linear and non-linear processes, stationary as well as non-stationary time series. Also, the proposed model determines the relative importance of each input variable based on connection weights for the corresponding link type in heterogeneous network. Our implemented model employs the network temporal information, removes the presumption of past occurrence of a connection which is to be estimated, and distinguish the nonlinear temporal evolution mechanisms of each link type simultaneously. Thus, proposed method resolves drawbacks of the existing heterogeneous link prediction methods. Proposed methods are evaluated on two longitudinal real-world heterogeneous datasets. These data sets are; bibliographic dataset DBLP and a social bookmarking dataset Delicious. Each dataset is split into training and test sets such that training set contains time-sliced snapshots of the network that are used to create time series models and test set contains the actual links in the future. Due to the The Area Under Curve (AUC) is a commonly used performance measure in imbalanced datasets, our link prediction models are evaluated in terms of AUC. Distinct AUC measures are defined for comparing the performance of link prediction. AUCdisconn is defined for only non-connected pairs in the most recent three previous time periods in the training set, AUCconn is defined for only connected pairs in the most recent three previous time periods, AUClastDisconn is defined for only non-connected pairs in the last time period, AUClastConn is defined for only connected pairs in the last time period. Additionally, AUCchange is defined for only the pairs whose state (connected or non-connected) are altered to another state after the last time period which is one of the hardest task in link prediction. The proposed methods may be extended by designing the parallel computation methods in distributed environments to decrease the complexity and can be used in huge networks. Additionally, the proposed methods may be enhanced by using various types of node similarities and different types of network datasets.