Research Of Link Prediction Algorithms On Dynamic Network And Heterogeneous Information Network

With the development of the Internet and the explosive growth of data,people,computers and their relationships have built complex systems.Network science is one of the effective methods to study and describe complex systems.The network can be used to describe the structure of complex systems and capture effective information from complex data.Using the observed network structure information,link prediction can explore the potential relationships between network nodes,predict the possibility of unconnected nodes connecting edges in the future,and identify false edges in the network.In practical applications,link prediction can be used to predict user relationships in social networks,recommend products in recommendation systems,predict the combination relationship between drugs in biological networks,and so on.Therefore,the research of link prediction has great theoretical and application significance.However,most link prediction algorithms currently only target single-layer networks without time information,or homogeneous networks with a single type of nodes and edges.However,complex systems in the real world will dynamically change over time,and they are also composed of multiple types of nodes and multiple types of edges.The former network that changes dynamically over time is called a dynamic timing network,while the latter is a network composed of multiple types of nodes and edges called a heterogeneous information network.This thesis studies the link prediction based on non-negative matrix factorization embedding.The link prediction based on embedding believes that the closer the low-dimensional embedding of two nodes is,the more likely the two nodes will be connected.In this thesis,aiming at the problems existing in the current link prediction research,it studies link prediction algorithms on dynamic networks and heterogeneous networks,and builds a model that can accurately predict the relationship between network connections.The main emphasis on content and innovation are summarized as follows:(1)Dynamic network link prediction algorithm design.Real networks often change dynamically over time.In order to design a more effective link prediction algorithm,it is necessary to mine the network’s timing change information while mining the network topology.This thesis proposes a time series link prediction model combining multi-label learning and Deep Walk embedding.First,use the matrix factorization algorithm equivalent to Deep Walk to extract the network topology information;then,based on the timing smoothing idea and multi-label learning to predict the network connection in the next time period;finally,through joint learning,the two modules promote each other,affect each other.Experimental studies on a large number of dynamic networks show that the link prediction accuracy of this algorithm is higher than other advanced algorithms,and it also verifies that joint learning is the main reason that makes this algorithm superior.(2)Design of link prediction algorithm for heterogeneous network.Complex systems are often heterogeneous,that is,the network nodes and the relationship between nodes are of multiple types,so when mining the information of heterogeneous networks,the importance of different types(semantic information)needs to be considered.This thesis proposes a heterogeneous network link prediction model combining non-negative matrix factorization and support vector machines.First use the prior knowledge to select the appropriate metapath,construct the corresponding adjacency matrix according to the different meta-paths,and extract the semantic information;then use the non-negative matrix decomposition to extract the topological structure information of each semantic sub-network,and then aggregate the topological information of each semantic For node embedding;finally,joint support vector machine is used for link prediction.In the experiment of drug combination prediction,the link prediction accuracy of this algorithm is higher than other drug combination prediction algorithms.