Xuan Qi, Wu Tie-Jun
Department of Control Science and Engineering, Zhejiang University, Hangzhou 310027, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Aug;80(2 Pt 2):026103. doi: 10.1103/PhysRevE.80.026103. Epub 2009 Aug 4.
Revealing corresponding identities of a dedicated individual in several different complex systems is a common task in many areas, and this task is transferred to a node matching problem among complex networks in this paper. A feasible node matching algorithm based on network structure is proposed. Through solving node matching problems on different types of networks by our algorithm, it is revealed that the structure of the networks under study may significantly influence the final matching results. For example, it is found that higher matching precision can be obtained on random networks with moderate density of links, and the results on small-world networks are always better than those on random or regular networks. Moreover, in scale-free networks, it seems that hub nodes play dominant roles, i.e., better matching results can be expected by selecting nodes with larger degrees as the revealed matched nodes. These findings will help us design more efficient node matching algorithm in the future.
在多个不同的复杂系统中揭示特定个体的对应身份是许多领域的常见任务，本文将该任务转化为复杂网络中的节点匹配问题。提出了一种基于网络结构的可行节点匹配算法。通过用我们的算法解决不同类型网络上的节点匹配问题，发现所研究网络的结构可能会显著影响最终的匹配结果。例如，发现在链路密度适中的随机网络上可以获得更高的匹配精度，并且小世界网络上的结果总是优于随机网络或规则网络上的结果。此外，在无标度网络中，似乎枢纽节点起着主导作用，即通过选择度数较大的节点作为揭示的匹配节点可以预期得到更好的匹配结果。这些发现将有助于我们未来设计更高效的节点匹配算法。
