Research And Design Of Node-Matching Algorithms Between Weighted Networks

Complex network is a new interdisciplinary, which is used to describe the structure of a complex system by integrating graph theory and statistics. With the rapid development of computer science and network technology, the study of complex networks has expanded towards many areas within the last ten years, i.e. economics, sociology, biology, physics, linguistics and so on. It attracts attentions from tremendous domestic and foreign experts of different areas and becomes a real hot topic.Node matching between complex networks has important practical significance in many areas such as homologous proteins revealing, ancient words translating, criminals inter-network tracking, and so on. Our research group has designed several node-matching algorithms to solve the problem, by using topology information of the network. However, since real-world networks tend to be highly symmetric, these methods may lose effect by using only local topology information. In this thesis, in order to overcome this shortage, we proposed a weighted iterative node matching algorithm, where we calculate the similarity between two nodes of different networks by utilizing both topological and link-weight information. The main contents of this thesis are summarized as follows:1. The basic concept of complex network is introduced, as well as the commonly used statistical parameters and classic network models.2. A weighted interactional network model is proposed. This model, as a theoretical basis, will be used to generate pairwise weighted interactional networks to test node-matching algorithms.3. A new method to calculate the similarity between nodes of different networks is proposed. The method takes network topology information and link weight information together into consideration, expanding the traditional definition of similarity.4. A new weighted node-matching algorithm is proposed, based on the new similarity, which is used to solve the node-matching problem between weighted networks. We test this new algorithm on pairwise artificial networks of high topological symmetry and a pair of real Chinese-English language networks, to verify the effectiveness of the algorithm.5. A complex network node-matching software system is designed. The system could be used to match nodes of both simulated networks and real networks.6. The whole thesis is summarized, and the next research direction is pointed out according to the problems found in the study of this thesis.