Identification Of Similarity Between Complex Network Systems And Its Application

Describing a complex system as a network consisting of numerous interacting individuals is an important approach to understand of a complex system. Within a single decade, research on complex networks has been expanded to many areas including information, control, phyisics, biology, social science, and so on. As more and more complex systems have been modeled as networks, data mining in complex networks emerges as an important task. One of the very recently proposed subject with high novelty is the identification of similarity between complex network systems that consists of two parts, i.e., individual level and system level similarity. Identification of individual level similarity is the key problem of this research, whose main purpose is to reveal the existent yet unknown correspondences between nodes from different interacted networks. In fact, it can be represented as the node matching problem between complex networks. Identification of similarity between complex network systems has its practical and theoretical significance in broad areas, such as large-scale interacted system analysis and optimization, multi-source information integration, inter-network searching, homogeneous proteins revealing and machine translation, just to name a few. This thesis systematically investigates the identification of similarity between complex network systems. The research of the thesis is organized in the form of problem modeling, algorithm design, and practice. More carefully, the algorithm design part is splited according to two specifications, i.e., node correspondecy constraint (one-to-one, one-to-many) and number of networks matched (parewise, mutiple). The main contents of this thesis are summarized as follows:1. Two interacted network models are proposed, i.e., homogeneous-evolution model and coevolution model, both of which can be adjusted regarding to interacting strengthness and network structure, and the former can easily generate multiple interacted networks simutaniously. In order to maintain the connectivity of the generated networks, an efficient method has been introduced. Then, by expanding the definition of similarity between nodes of the same network, three kinds of similarities between nodes from different networks are proposed. Moreover, a measurement of differentiability has been introduced to evaluate the effectiveness of the proposed similarity functions. On one hand, this part of research provides simulation platforms and sheds light on algorithm design for the identification of similarity between complex networks. On the other hand, it is also meaningful for generalizing other data mining techniques that tackle only single network to multiple networks.2. A node matching algorithm based on similarity propagation is proposed, which can be used to solve one-to-one node matching problem between small-scale networks and requires no special constrain for distribution of the revealed matching node pairs. The propagation process makes the initial similarity information propagate along the network topology globally, and consequently, information provided by the revealed pairewise matched nodes can be fully exploited. As a result, a relatively acceptable matching precision can be met even there are very limited numbers of revealed pairewise matched nodes.3. A novel iterative node matching algorithm with approximately linear complexity is proposed to sovle the one-to-one node matching problem between large-scale networks in real world. At the same time, a degree based revealed pairwise matched nodes selection strategy has been introduced to improve the matching results in the early period of the iteration and therefore improve the overall matching precision of the iterative matching algorithm. It is revealed that, as long as the revealed pairewise matched nodes are relatively centralized, the algorithm performs well both in time and matching precision.4. One-to-many node matching problem between networks is formulated, and we propose two one-to-many node matching algorithms based on local mapping and ensembling, respectively. The former overcomes the short sightedness of the one-to-one iterative node matching, and the later bears a close resemblance to Bagging ensemble, which is relatively robust to noise and can be easily parallelized. A pair of real-world interacted networks has been extracted from a large scale Instant Messaging system. With this pair of networks, empirical study of the proposed iterative one-to-one and one-to-many node matching algorithms has been carried out, respectively. It is revealed that the proposed one-to-many algorithm can quickly narrow down the searching range.5. The node matching among multiple networks is formulated and we propose an algorithm based on cluster extraction to solve it. The proposed algorithm exploits information provided by all of the networks involved as well as the revealed pairewise matched nodes. Matching experiments carried on four kinds of networks with different structure demonstrates the effectiveness of the proposed algorithm. 6. Identification of similarity between complex network systems has been successfully applied to the analysis of cascading failure in interdependent systems. It is revealed that the similarity between interdependent systems is helpful to avoid the cascading failure. According to this discovery, a node matching based cascading failure protection method is proposed, which optimizes the correspondences between adjustable nodes while keeping the structure of the interdependent networks unchanged. It is revealed that the node matching based design can significantly improves the resistance to cascading failures in interdependent networks. Due to the reason that many real-world critical infrastructures are indeed interdependent, the proposed optimal design method based on node matching has its practical significance.