Research On Algorithms For Identifying Missing Nodes In Complex Networks

In the real world,many systems are represented in the form of networks,such as social networks,scientist networks,the Internet,and protein networks.These networks are known as complex networks.In recent years,the structures and characteristics of complex networks have been fully studied.However,the identification and recovery of network information is still a long-term challenge in the field of modern information science,which has important theoretical and practical significance.Link prediction is an important solution to address these problems,and hence has been studied in many disciplines,such as Computer science,Physics and Biology.Link prediction aims to estimate the connection likelihood between two unconnected nodes in a network by using the known information of nodes and network structures.As a result,link prediction can recover the topology structure of the network,and reveal the evolution of the network.Similar with link prediction,missing nodes identification is of great significance for network information identifying and recovery,which can identify missing nodes and restore the network topology structures by using known network information.This thesis focuses on the research of identifying missing nodes in complex networks.In general,it is necessary to add some constraints for identifying missing nodes.Placeholder and fuzzy nodes are two frameworks to solve the problem of missing nodes identification.In this thesis,two corresponding algorithms for identifying missing nodes are proposed under these two different frameworks.Under the placeholder framework,the algorithm of GFEN is designed based on graph embedding.In GFEN,all nodes are represented as vectors by means of the graph embedding method node2 vec.Then,the SVM is used to evaluate the probability that two placeholders belong to the same missing node.Finally the missing nodes are identified by hierarchical clustering method.Under the fuzzy nodes framework,the algorithm of MIPS is presented based on the similarity of nodes.This algorithm employs the algorithm of PageSim to calculate the similarity of nodes,and uses the hierarchical clustering method to identify the missing nodes.Experimental results show that these two algorithms have good identifying accuracy for the problem of identifying missing nodes.