复杂网络结构比对算法研究进展
第１０卷第４期 智 能 系 统 学 报 Ｖｏｌ．１０№．４２０１５年８月 ＣＡＡＩＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓ Ａｕｇ．２０１５ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３－４７８５．２０１４０８００６网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｃｍｓ／ｄｅｔａｉｌ／２３．１５３８．ＴＰ．２０１５０３０２．１１０６．００５．ｈｔｍｌ
复杂网络结构比对算法研究进展
刘富１，姜奕含１，邹青宇２
（１．吉林大学通信工程学院，吉林长春１３００２２；２．北华大学电气信息工程学院，吉林吉林１３２０００）
摘 要：复杂网络的结构比对问题在生物科学、计算机科学和社会科学等多个领域都具有很重要的现实意义。近年来涌现出了很多针对不同类型复杂网络的结构对比算法，对现有的网络结构比对算法进行梳理，重点分析了基于图的网络结构比对方法和基于数学框架网络结构比对方法。对这２种方法的特点进行了总结与比较，重点阐述了网络结构比对研究中的关键问题，分析和总结了现有的网络结构比对算法，阐述了网络结构比对中优势和不足。以此为基础提出了复杂网络结构比对问题未来的研究方向。
关键词：复杂网络；二次规划；拓扑结构识别；图论；比对；网络分析；结点集群性；动态分析
中图分类号：ＴＰ３９１；Ｏ２１２ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１５）０４－０５０８－１０
中文引用格式：刘富，姜奕含，邹青宇．复杂网络结构比对算法研究进展［Ｊ］．智能系统学报，２０１５，１０（４）：５０８－５１７．
英文引用格式：ＬＩＵＦｕ，ＪＩＡＮＧＹｉｈａｎ，ＺＯＵＱｉｎｇｙｕ．Ａｄｖａｎｃｅｓｉｎａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｒｅ－ｓｅａｒｃｈ［Ｊ］．ＣＡＡＩＴｒａｎｓａｃｔｉｏｎｓｏｎＩｎｔｅｌｌｉｇｅｎｔＳｙｓｔｅｍｓ，２０１５，１０（４）：５０８－５１７．
Ａｄｖａｎｃｅｓｉｎａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｒｅｓｅａｒｃｈ
ＬＩＵＦｕ１，ＪＩＡＮＧＹｉｈａｎ１，ＺＯＵＱｉｎｇｙｕ２
（１．ＣｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００２２Ｃｈｉｎａ；２．Ｅｌｅｃｔｒｉｃ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＢｅｉｈｕａＵｎｉｖｅｒｓｉｔｙ，ｊｉｌｉｎ，１３２０００Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｈｅｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｐｒｏｂｌｅｍｓｉｎｂｉｏｌｏｇｉｃａｌｓｃｉｅｎｃｅ、ｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ、ｓｏｃｉａｌｓｃｉｅｎｃｅａｎｄｏｔｈｅｒｆｉｅｌｄｓｈａｖｅｐｒａｃｔｉｃａｌｓｉｇｎｉｆｉｃａｔｉｏｎ．Ｉｎｒｅｃｅｎｔｙｅａｒｓ，ｄｉｆｆｅｒｅｎｔｔｙｐｅｓｏｆｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓｈａｖｅｂｅｅｎｓｐｒｕｎｇｕｐ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｍａｉｎｌｙａｎａｌｙｓｅｄｔｈｅｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｓｂａｓｅｄｏｎｇｒａｐｈａｎｄｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｓａｎｄｍａｔｈｅｍａｔｉｃａｌｆｒａｍｅｗｏｒｋ．Ｉｌｌｕｓｔｒａｔｉｎｇｔｈｅｋｅｙｐｒｏｂｌｅｍｉｎｔｈｅｓｔｕｄｙｏｆｔｈｅｎｅｔｗｏｒｋｓａｌｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｉｓａｎａｌｙｚｅｄａｎｄｃｏｍｐａｒｅｄｔｈｅａｌｇｏｒｉｔｈｍｓｏｆｃｏｎｓｔｒｕｃｔｉｏｎａｌｉｇｎｍｅｎｔ．Ｗｅｅｘｐｌａｉｎｅｄｔｈｅｉｒａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓ，ａｔｌａｓｔｗｅｆｏｒｅｃａｓｔｔｈｅｆｕｔｕｒｅｐｒｏｇｒｅｓｓｏｆａｌｇｏｒｉｔｈｍｓｆｏｒｃｏｎｓｔｒｕｃ－ｔｉｏｎａｌｉｇｎｍｅｎｔｏｆｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ；ｑｕａｄｒａｔｉｃｐｒｏｇｒａｍｍｉｎｇ；ｔｏｐｏｌｏｇｙｉｄｅｎｔｉｆｉｃａｔｉｏｎ；ｇｒａｐｈｔｈｅｏｒｙ；ａｌｉｇｎｍｅｎｔ；ｎｅｔｗｏｒｋａ－ｎａｌｙｓｉｓ；ｎｏｄｅｃｌｕｓｔｅｒ；ｄｙｎａｍｉｃａｎａｌｙｓｉｓ
收稿日期：２０１４－１２－２５． 网络出版日期：２０１５－０３－０２．
基金项目：吉林省重点科技攻关项目（２０１４０２０４０４６）；生物芯片自动识
别系统（２０１００５０５）．
通信作者：：刘富．Ｅ－ｍａｉｌ：ｌｉｕｆｕ＠ｊｌｕ．ｅｄｕ．ｃｎ 在自然界和社会中的复杂网络代表实体在非均
匀系统之间的相互作用，随着复杂网络和图形数据
的增长，网络结构比对的应用在过去１０年呈爆炸式
增长。尤其是随着化学实验测定技术［１－２］和文献挖掘技术［３］的发展产生了大量的生物网络数据。现实世界复杂网络主要包括社会网络、信息网络、技术网络和生物网络。从宏观方面分析，复杂的网络可以从度分布、特征路径长度以及聚集系数上来分析；从微观方面分析，复杂网络包括网络模体，例如小子图更可能表现出网络的重要性质；中级的子图更容