Link Prediction In Complex Dynamic Networks

Link prediction in social networks has attracted increasing attention in various fields such as sociology, anthropology, information science, and computer science. Existing work on link prediction has been mostly formulated based on a static network setup, where a partial network structure is known and the objective is to predict the hidden links. In such a static network, link occurrence is typically modeled as a one-time event and the primary interest is on the existence of such event. In dynamic complex network, temporal topology information is one of the main sources to design the similarity function between entities. But the existing link prediction algorithms do not apply the temporal information sufficiently. Generally, link prediction methods based on the static graph representation cannot achieve satisfactory results when the repeated occurrences of the links are of central interest and temporal patterns are the primary feature of the application domain. Therefore, it is necessary to study effective methods for predicting links in dynamic networks. To the best of our knowledge, very few prior work in the literature deals with link prediction taking as input the link occurrence frequency time series. In this thesis, we focus on designing network-based approaches for effectively integrating temporal and topological information to predict future links in dynamic networks with node attributes and uncertain links. The main contribution of this thesis is as follows.(1) We present a method for link prediction in dynamic networks by integrating temporal information, community structure, and node centrality in the network. Information of all of these aspects is highly beneficial in predicting potential links in social networks. Temporal information offers link occurrence behavior in the dynamic network, while community clustering shows how strong the connection between two individual nodes is, which is based on whether they share the same community. The centrality of a node, which measures its relative importance within a network, is highly related with future links in social networks. We predict a node’s future importance by eigenvector centrality, and use this for link prediction. Merging the typological information, including community structure and centrality, with temporal information generates a more realistic model for link prediction in dynamic networks.(2) We present a method for link perdition in dynamic uncertain networks. Due to the inaccuracy, incompleteness and noise in data of real applications, uncertainty is a natural feature of real world networks. In such networks, each edge is associated with a probability value indicating its existence in the network. Predicting links in uncertain networks is computationally more challenging, and semantically differs from predicting connections in deterministic networks. We study link prediction problem under uncertain links, and present a method for link perdition in temporal uncertain networks. In this method, the predicting problem is formalized by designing a random walk in temporal uncertain networks. The algorithm first transforms the link prediction problem in uncertain networks to a random walk in a deterministic network. Then the similarity scores between a node and its neighbors are computed within a sub-graph around this node so as to reduce the computational time.(3) Many real-world networks contain rich information in node attributes. A non-negative matrix factorization (NMF) based method is proposed to solve the link prediction problem in dynamic graphs with node attributes. The method learns latent features from the dynamic and topological structure and the node attributes of a graph, and can obtain higher prediction results. We present new iterative rules to construct matrix factors that carry important features of the network, and prove the convergence and correctness of these algorithms. Finally, we show how latent features of NMF can express the graph dynamics efficiently rather than static representation, and can yield better performances than using static representation. The proposed method integrates temporal and global topological information in temporal networks, and can obtain more accurate results. Experimental results on real social networks show that our method can predict future links efficiently in dynamic networks with node attributes, and achieves higher quality results than other similar methods.(4) We propose a fast sampling based method to predict the links related to the nodes of interest in dynamic networks. In many real world applications of dynamic networks, we need to predict the similarity scores only between the pairs of vertices that the users are interested in, instead of predicting the scores of all pairs of vertices in the network. In this case, we do not need to make link prediction in the whole network. We propose a fast similarity-based method to predict the links related to the nodes of interest in dynamic networks. In the method, we first combine the dynamic networks to one weighted graph; a proper damping factor is used in the combination process to assign more importance for more recent networks. Second, we construct a sub-graph centered at the node of interest in the weighted graph. Such sub-graph is constructed by starting a random walk from the given node. A proper size of such a sub-graph is chosen so as to restrict the error of the estimated similarities within a given threshold. Since the similarity score is computed within a small sub-graph, the algorithm can reduce the computation time greatly. The method is also extended to predict the potential links in the whole network so as to achieve high process speed and accuracy. Moreover, the proposed method integrates temporal and global topological information in temporal networks, and can obtain more accurate results.All proposed methods mentioned above are tested on different real networks. The experimental parts investigate the performance of proposed methods, analyze their results under different parameter values, and also compare their performances with other similar methods. Our experimental results show that all the methods proposed can obtain higher quality results in less computation time than other similar methods.