Research On Link Prediction In Complex Networks

The primary task of link prediction in complex networks is to find out missing links in various real-world networks.Link prediction has a wide range of application scenarios.For example,in the biomedical field,link prediction can infer interactions among molecules and reduce the cost of biomedical experiments;In the socio-economic field,link prediction can recommend friends for users in social networks and objects for users in e-commerce platforms,to help users quickly find relevant information and increase revenues for platforms.In the field of techniques in data mining,link prediction can be used to remove noise and complete network structures.Meanwhile,it can also be utilized as a significant technique for problems such as community detection,knowledge graph construction and vital nodes identification to improve the performance of corresponding data mining tasks.In addition,link prediction can be used as a “touchstone” to verify the reliability of the network generation mechanism at the theoretical level.With the development of techniques of data acquisition and data storage,it is possible to study on a large number of real networks,which brings new opportunities and challenges to link prediction: firstly,are the existing link prediction algorithms still applicable to most networks from different domains? Can the well-known common neighbor(tradic closure or clustering,etc)mechanism still explain the link generation process of most networks? Secondly,different networks have different network topologies,which leads to unstable prediction performance of link prediction algorithms.Algorithms that perform well on some networks perform poorly on other networks.Finally,under the challenge of data sparsity and the opportunity brought by the relevance between different datasets,much more complex networks have been constructed,which can not be directly predicted by link prediction algorithms for simple networks.It is another challenge to improve the prediction performance of link algorithms by digging out the information of more complex networks.The dissertation will investigate the above issues from the possible limitation,robustness,accuracy and complexity levels.The main contents and major contributions are summarized as following:(1)To explore the possibility limitation of existing link prediction algorithms,the applicability of link prediction algorithms based on 2-hop-based framework in massive networks is studied.Based on the linear hypothesis,a link prediction algorithm based on linear optimization(LO for short)is proposed.Compared with corresponding benchmarks,it has high accuracy and can be applied to various types of networks,including weighted networks and directed networks.According to in-depth analysis of LO’s analytical solution,we find that a degenerated index based on 3-hop-path performs better than the common neighbor index.Furthermore,four groups of algorithms based on the 2-hoppath framework and the 3-hop-path framework,respectively,are compared in massive real networks.Results show that 3-hop-based link prediction algorithms are not always better than 2-hop-based algorithms,and 3-hop-based algorithms are more suitable for disassortative networks with lower densities and lower average clustering coefficients.In addition,we find that Cannistraci-Hebb theory plays an important role in link prediction in most considered networks.This work can help people reshape their understanding of the local connection paradigm of nodes in real networks.(2)To mitigate the instability of existing link prediction algorithms,both collaborative filtering and similarity theory are utilized to design a robust link prediction framework.Similarity theory shows that similar nodes tend to connect with each other,while collaborative filtering shows that similar nodes tend to connect the same or similar nodes.Considering this difference,the dissertation proposes an enhancement framework based on collaborative filtering(CF for short)and a self-included collaborative filtering enhancement framework(SCF for short).Results show that the CF framework can largely improve the performance of well-known local indices and the SCF framework can still significantly improve the performance of CF framework.Both of them always perform better than original indices subject to various data sparsity.In addition,SCF-enhanced indices can achieve competitive performance compared with state-of-the-art global algorithms and has advantages in time complexity.This work provides a simple,interpretable,robust and efficient algorithmic framework for link prediction.(3)To design a more accurate link prediction algorithm,two algorithms by controlling the contribution of the leading eigenvector are proposed.The dissertation shows that the common neighbor index(CN for short)can be linearly decomposed by eigenvectors of the adjacency matrix corresponding to the target network,and each eigenvector’s contribution is proportional to the square of the corresponding eigenvalue.Due to there exists a huge gap between the largest eigenvalue and the second largest eigenvalue,the CN index is dominated by the leading eigenvector and much useful information contained in other eigenvectors may be overlooked.Therefore,we design a parameter-free algorithm(named as CLE)and a parameter-dependent algorithm(named as CLE*)to control the contributions of eigenvectors.Compared with the original CN index,the prediction performance can be largely enhanced by CLE and CLE*.In addition,CLE and CLE* all outperform the corresponding benchmarks with lower time complexity than global algorithms.This work not only provides more accurate link prediction algorithms,but also shows a new view to understand the CN index mathematically.(4)To tackle the link prediction problem in complex types of networks,a social recommendation algorithm based on multi-layer networks is proposed.At first,the social recommendation problem is modeled as an inter-layer link prediction problem on a multilayer network composed of a user—user social network and a user—object bipartite network.It is assumed that there is a potential user interest similarity matrix,which can be used to infer both the user—user social network and the user—object bipartite network.By the mutual constraints of the two observation networks,a social recommendation algorithm via linear optimization(SLO for short)is proposed.Results show that SLO performs best compared with six benchmarks subject to four accuracy metrics and two diversity metrics in four scenarios including recommendation for all users,active users,inactive users and cold-start users.This work provides an effective recommendation algorithm to mitigate the accuracy-diversity dilemma,data sparsity challenge and cold-start challenge in recommendation systems.