Node matching between complex networks

How to reveal corresponding identities of an individual in different complex systems is an ongoing problem in various areas, which can be transferred to a node-matching problem between different complex networks. In this paper, a novel iterative node-matching algorithm and two appropriate revealed pairwise matched nodes ’ selection strategies are proposed. It is proven that the algorithm has the approximately linear time complexity, which is much lower than that of the traditional matching algorithms in graph theory. Besides it seems that a tiny error imported in the early stage of the iterative process will not be magnified as the algorithm further proceeds. Therefore, the iterative algorithm can produce surprisingly higher matching precision on interactional scale-free networks generated by the BA model, especially when there are only a small fraction of pairwise matched nodes revealed in advance. The algorithm is finally tested by a pair of real-world networks and a feasible result is obtained. PACS numbers: 89.75.Hc, 89.75.Da, 89.70.Eg (Some figures in this article are in colour only in the electronic version) 1