Link Prediction Of Community Network

In real life, there are many complex systems which can be abstracted as complex networks and be studied with graph theory method. The research of complex network has an extraordinary position in today's society, and the two important directions of complex network research are link prediction and community dividing. On one hand, link prediction means estimating the likelihood of the connections of the nodes between which there are no edges observed in the network through using the known information of the network. Generally there are two main applications of link prediction, one is forecasting the links which already exists but has not yet been found, and the other one is predicting the edges which may arise in the future. Link prediction research not only has theoretical value, but also has important application value, so this is a very meaningful work. On the other hand, community dividing means to find a classification method of the nodes in the network, making the connection between nodes within the same set more closely, and the connection between different collections is sparser. Understanding the community structure of a network is of great significance on analyzing the topology structure of the network, and finding the function of the network, discovering the hidden rules of network and predicting the behavior of the network. The community structure of the complex network is so important that it is also a research hotspot to detect the network community structures fast and efficiently based on the existing network data.The work of this thesis is about these two directions. Firstly, we put forward a link prediction method based on community information and node similarity which takes advantage of community information and node similarity information of the network. Then, we found that the link prediction results of the complex network, to some extent, actually reflect the attributes of network evolution. Based on this thought, we gave one kind of community detection method based on the evolution of network which makes use of the information of network link prediction results. Finally, surprisingly, we found that the proposed community partition algorithm can work well in the symbol network after slightly adjusted, and can reach a good performance. In this paper, the main work is as follows:1. Prediction method based on community information and node similarity. To achieve the link prediction in this method we, on the basis of random block model, fuse the community structure information of the network and the similarity information of the nodes. Through the experiments in the real networks and the LFR benchmark networks, we have confirmed that the method not only has a high prediction accuracy but also has a relatively small time complexity. In particular, in the face of different size of network, we can implement this algorithm in different ways respectively, and at the same time guarantee the good performance.2. Community detection method based on network evolving. This community detection method is based on reappearing the process of the network evolving by using the link prediction results information. And we achieve the community detection at the same time of reappearing the evolving of the network. A large number of experiments have been completed, proving that the complexity of the proposed algorithm in this paper is low and the accuracy is high, the more important is the robustness of the algorithm is very high.3. Symbols network community detection method based on network evolving. On the basis of the previous work, we extend the community detection method into a more general case, that is the algorithm is applicable to the symbols networks after slightly adjusted. And through the experiments on real social network and simulation networks, we have verified the effectiveness of this approach.