Mining The Information Of Networks Using Local Structures

Complex network is one of research hotspots in recent years. In the study of complex network, how to mine useful information from networks is an important problem. As links may contain some underlying information among nodes, this thesis mainly study the link prediction problem. Based on the previous studies, this thesis attempts to use local structures to do the link prediction. This thesis studies the local community structure and local link structure, and proposes three link prediction algorithms. The main work of this thesis is as follows:(1) For the link prediction in undirected networks, this thesis proposes the LocalCross-Communities-Link(LCCL) algorithm. Based on the theory of local community,LCCL defines the neighbors of a single node as its local community, and do the link prediction through the link between local communities.(2) For the link direction prediction problem in directed networks, this thesis proposes the Local Directed Path(LDP) algorithm. LDP mainly considers the local link structure,and tries to predict link direction through the number of local paths. By importing a specific ground node, LDP considers three kinds of different local short paths(simple link,normal link and special link) to predict link direction. In the empirical analysis, it shows that by considering local link structure, LDP can greatly improve the performance, which provides reference to the design of network models and algorithms.(3) Study a special kind of link prediction algorithm(the algorithm based on randomized structures), and propose Degree Corrected Stochastic Block Model(DCSBM).DCSBM can be seen as weighting all the possible local community structures according to their likelihood functions. The main purpose of this research is to see whether nodes are different in local structures. Though the empirical analysis, this thesis finds that the position of different nodes in local community structure should not be considered equally.When the network is small, the differences of their status may be not obvious, while they become significant when the size of network increases, which provides some idea for the study of the local structures.