复杂网络结构比对算法研究进展

第１０卷第４期　２０１５年８月　智能系统学报　Ｖｏ１．１０№．４　Ａｕｇ．２０１５　ＣＡＡＩ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｓｙｓｔｅｍｓ　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３—４７８５．２０１４０８００６　网络出版地址：ｈｔｔｐ：／／ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ｋｅｍｓ／ｄｅｔａｉＬ／２３．１５３８．ＴＰ．２０１５０３０２．１１０６．００５．ｈｔｍｌ　复杂网络结构比对算法研究进展　刘富　，姜奕含　，邹青宇　（１．吉林大学通信工程学院，吉林长春１３００２２；２．北华大学电气信息工程学院，吉林吉林１３２０００）　摘要：复杂网络的结构比对问题在生物科学、计算机科学和社会科学等多个领域都具有很重要的现实意义。近年　来涌现出了很多针对不同类型复杂网络的结构对比算法，对现有的网络结构比对算法进行梳理，重点分析了基于图　的网络结构比对方法和基于数学框架网络结构比对方法。对这２种方法的特点进行了总结与比较，重点阐述了网　络结构比对研究中的关键问题，分析和总结了现有的网络结构比对算法，阐述了网络结构比对中优势和不足。以此　为基础提出了复杂网络结构比对问题未来的研究方向。　关键词：复杂网络；二次规划；拓扑结构识别；图论；比对；网络分析；结点集群性；动态分析　中图分类号：ＴＰ３９１；Ｏ２１２文献标志码：Ａ文章编号：１６７３—４７８５（２０１５）０４—０５０８—１０　中文引用格式：刘富。姜奕含，邹青字．复杂网络结构比对算法研究进展［Ｊ］．智能系统学报，２０１５，１０（４）：５０８．５１７．　英文引用格式：ＬＩＵ　Ｆｕ，ＪＩＡＮＧ　Ｙｉｈａｎ。ＺＯＵ　Ｑｉｎｇｙｕ．Ａｄｖａｎｃｅｓ　ｉｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｒｅ・　ｓｅａｒｃｈ［Ｊ］．ＣＡＡＩ　Ｔｒａｎｓａｃｔｉｏｎｓ　Ｏｉｌ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｓｙｓｔｅｍｓ，２０１５。１０（４）：５０８－５１７．　Ａｄｖａｎｃｅｓ　ｉｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｒｅｓｅａｒｃｈ　ＬＩＵ　Ｆｕ　，ＪＩＡＮＧ　Ｙｉｈａｎ　，ＺＯＵ　Ｑｉｎｇｙｕ　（１．Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｅｈｕｎ　１３００２２　Ｃｈｉｎａ；２．Ｅｌｅｃｔｒｉｃ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ，　ｊｉｌｉｎ，１３２０００　Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｂｉｏｌｏｇｉｃａｌ　ｓｃｉｅｎｃｅ、ｃｏｍｐｕｔｅｒ　ｓｃｉｅｎｃｅ、ｓｏｃｉａｌ　ｓｃｉｅｎｃｅ　ａｎｄ　ｏｔｈｅｒ　ｆｉｅｌｄｓ　ｈａｖｅ　ｐｒａｃｔｉｃａｌ　ｓｉｇｎｉｆｉｃａｔｉｏｎ．Ｉｎ　ｒｅｃｅｎｔ　ｙｅａｒｓ，ｄｉｆｆｅｒｅｎｔ　ｔｙｐｅｓ　ｏｆ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｈａｖｅ　ｂｅｅｎ　ｓｐｒｕｎｇ　ｕｐ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｍａｉｎｌｙ　ａｎａｌｙｓｅｄ　ｔｈｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ｂａｓｅｄ　ｏｎ　ｇｒａｐｈ　ａｎｄ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｍａｔｈｅｍａｔｉｃａｌ　ｆｒａｍｅｗｏｒｋ．Ｉｌｌｕｓｔｒａｔｉｎｇ　ｔｈｅ　ｋｅｙ　ｐｒｏｂｌｅｍ　ｉｎ　ｔｈｅ　ｓｔｕｄｙ　ｏｆ　ｔｈｅ　ｎｅｔｗｏｒｋｓ　ａｌｉｇｎｍｅｎｔ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｎａｌｙｚｅｄ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　ｏｆ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ．　Ｗｅ　ｅｘｐｌａｉｎｅｄ　ｔｈｅｉｒ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｄｉｓａｄｖａｎｔａｇｅｓ，ａｔ　ｌａｓｔ　ｗｅ　ｆｏｒｅｃａｓｔ　ｔｈｅ　ｆｕｔｕｒｅ　ｐｒｏｇｒｅｓｓ　ｏｆ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｃｏｎｓｔｒｕｃ—　ｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ．　Ｋｅｙｗｏｒｄｓ：ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ；ｑｕａｄｒａｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ；ｔｏｐｏｌｏｇｙ　ｉｄｅｎｔｉｆｉｃａｔｉｏｎ；ｇｒａｐｈ　ｔｈｅｏｒｙ；ａｌｉｇｎｍｅｎｔ；ｎｅｔｗｏｒｋ　ａ—　ｎａｌｙｓｉｓ；ｎｏｄｅ　ｃｌｕｓｔｅｒ；ｄｙｎａｍｉｃ　ａｎａｌｙｓｉｓ　在自然界和社会中的复杂网络代表实体在非均　匀系统之间的相互作用，随着复杂网络和图形数据　的增长，网络结构比对的应用在过去ｌ０年呈爆炸式　收稿日期：２０１４—１２—２５．　网络出版日期：２０１５—０３．０２．　基金项目：吉林省重点科技攻关项目（２０１４０２０４０４６）；生物芯片自动识　别系统（２０１００５０５）．　通信作者：：刘富．Ｅ－ｍａｉｌ：ｌｉｕｆｕ＠ｊｌｕ．ｅｄｕ．ｃｎ　增长。尤其是随着化学实验测定技术¨。　和文献挖　掘技术　的发展产生了大量的生物网络数据。现　实世界复杂网络主要包括社会网络、信息网络、技术　网络和生物网络。从宏观方面分析，复杂的网络可　以从度分布、特征路径长度以及聚集系数上来分析；　从微观方面分析，复杂网络包括网络模体，例如小子　图更可能表现出网络的重要性质；中级的子图更容　第４期　刘富，等：复杂网络结构比对算法研究进展　・５０９・　易表现出网络的社区性和模块性　关于复杂网络　的研究是从欧拉的七桥问题研究开始的，复杂网络　通过结点之间的相互作用关系来表示，所以复杂的　网络关系可以用图Ｇ＝（　，　）表示，其中　代表结　点的集合，Ｅ代表边缘的集合。分析复杂网络的数　学理论基础是Ｅｒｄｏｓ＿４　提出的关于随机网络的生成　及演化的理论。复杂网络结构比对问题是在２个网　络或者多个网络中找到最佳匹配的结点之间映射关　系的优化问题，是一种放松的图同构问题　并且它　与子图同构问题　密切相关。网络结构比对问题　最先应用在模式识别和计算机视觉。。　上。在模式　识别上的应用主要是在大的模块中识别小的模块，　在计算机视觉的应用主要是进行图片的比较。在本　体定位应用程序　。。。和生物信息学上也有非常广泛　的应用，例如在数据库中找到匹配的数据　；在蛋　白质相互作用网络、代谢网络、基因表达网络、基因　调控网络和信号传导网络等都有实际的应用。对于　生物网络的比对问题，有着实际的意义，通过已知生　物网络比对未知生物网络，可以发现更多的生物网　络结构，对研究未知的生物领域有着很重要的作用。　在现实生活中同样存在着大量的复杂网络，例如信　息网络、交通网络、电力网络、社交网络、生物网络、　Ｐ２Ｐ网络、语言网络、公交网络等等，这些网络与人　们日常生活密切相关，因此这就需要深入研究复杂　网络的拓扑结构动力学行为和演化机制等，以便更　好地设计这些复杂网络和控制他们的行为。　１　复杂网络的比对问题　１）复杂网络结构比对问题的定义：２个已知的　复杂网络，网络Ｇ＝（Ｖ，Ｅ）和网络Ｈ＝（Ｕ，Ｆ），结　点　∈Ｇ，结点　∈Ｈ，存在一个映射关系０，映射　关系满足下面要求：　ｆ　１ｌ　Ｆ　Ｕ　Ⅱ（　）　ｉ一空隙　（　）　网络结构比对问题就是要找到不同网络顶点之　间的映射关系，使得网络结点的相似性得分最高，如　图１所示。　以　图１　。映射下的结点比对图　Ｆｉｇ．１　Ｎｏｔｅ　ａｌｉｇｎｍｅｎｔ　ｕｎｄｅｒ　ｎ　ｍａｐｐｉｎｇ　虚线箭头表示结点　∈Ｇ到结点“∈Ｈ的映射　关系：口（　）＝　，其中没有被标记的结点表示映射到　一个空隙。　２）网络结构比对中相似度函数的定义　相似度函数是２个网络结构比对的相似性得分　的计算公式，其形式化定义如下：　ｓ（０）＝　∑盯（　，ｎ（　））＋　∈Ｖ　。‘　’　。　ｆ　２１　∑　Ｅ　∑　（Ｅ　Ｖ　　，　（　），　，ｎ（　））　ｄ（　）≠一ｄｆ　１≠一“　式中：　是定义在被匹配顶点对的相似度函数，　ｒ　是定义在被匹配边的相似度函数，其中　，　∈Ｇ，这　是一个非常灵活的打分模型，它可以用来表示失配　和间隙。　３）复杂网络的比对图概念：复杂网络的比对问　题可以看作图的比对问题。复杂网络中的结点对应　于图的顶点，复杂网络中结点之间的相互作用对应　图的边。　比对图　ｕ　是一个加权的完全比对二分图，　是　ｕ　的结点集合。边缘权重ｅ＝（　，　）是　（ｅ）－－ｏ－（　，ｕ）。网络结构比对图如图２。　Ｇ　图２网络结构比对实例　Ｆｉｇ．２　Ｔｈｅ　ｃａｓｅ　ｏｆ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　这是一对一映射的网络结构比对图。在比对口　之间建立连接，结点的顺序对比对结果没有影响，这　个比对图具有图匹配的理论概念的特点，比对的图　是不会有２个被选择的边缘分享一个结点的子集的　情况。它提供了一种替代的方式来表示网络中结点　的比对。　２　复杂网络比对方法的分类　复杂网络的比对模型和算法是复杂网络比对方　法核心内容：复杂网络的比对模型是对复杂网络比　对问题的抽象和数学建模，主要通过复杂网络本身　的特性和具体问题的特点来进行比对模型的构建；　智能系统学报　第１０卷　网络的比对算法指的是比对模型上的可计算步骤，　用来计算网络的比对模型。本节主要从复杂网络的　比对模型方面对复杂网络比对方法进行分类探讨。　通过对近年来的网络结构比对方法进行总结，本文　主要把网络的比对方法归结为基于图的网络结构比　对方法、基于数学框架网络结构比对方法。　基于数学框架网络结构比对方法是一类优化问　题，具有一般优化问题的特征，这种方法将网络的比　对问题转化为常规的优化问题，采用已知的求解方　法进行求解；将网络比对问题中的匹配准则转化为　优化问题的约束条件。　基于图的网络结构比对算法是目前研究网络结　构比对算法中应用最多的一种算法。它是一种将网　络的比对问题转化为图的比对问题的算法。首先要　在进行比对的２个网络中构建一种映射关系，然后　建立模型进行网络结构比对。　２．１　基于数学框架网络结构比对方法　基于数学编程框架网络结构比对方法是一种目标　函数的约束优化方法。基于数学编程框架网络结构比　对方法主要分为整数二次规划法和矩阵特征值法。其　中整数二次规划法的代表方法是Ｋｌａｕ　Ｓ的简单的启发　式算法　和置信传播（ＢＰ）快速启发式的算法，矩阵特　征值法的代表方法是Ｉｓｏｒａｎｋｌｌ　方法。　２．１．１整数二次规划法　对于整数二次规划法，首先规范定义网络结构比　对的数学问题，对整数二次规划的问题进行求解；然　后使用简单的启发式算法释放整数二次规划问题的　完整约束，解决已有的线性规划问题，计算网络中边　缘权重得分；最后在网络结构比对中使用最大权重二　分图进行比对。整数二次规划定义规范¨　如下。　是权重二分图，Ｌ＝（　ｕ　Ｕ，Ｅ　，Ｗ），　和／３　是正常数，Ｇ、日、　和ＯＬ．／３是输入数据，把这些数据　设为已知量，其中Ｌ中的匹配集合　是Ｅ　的子集，　如果（　，“）和（　，ｆ）在匹配集合　中，称之为网络　Ｇ中边缘（　，Ｕ）与网络Ｈ中的边缘（ｋ，ｆ）是重叠　的。这个网络结构比对问题就是在　中找到最大　的匹配Ｍ。ＯＬ是匹配集合　的权重值，／３是网络Ｇ　和网络日重叠的边缘数。Ｗ是任意结点的边缘权向　量，Ｗ　表示边缘的向量，边缘（　，Ｕ）在Ｍ中　＝　１时，也就是说　＝１时结点　，Ｕ完全匹配，当矩　阵Ｓ是对应Ｅ　的边。　表示２个比对网络中对应的　结点比对关系。　线性匹配约束条件为　ｕ　∈Ａ．∑　　．ＭＥＥＬ　≤１，Ｍ∈日　（３）　个权重向量Ａ，　和一个权重矩阵Ｃ。。　。这２　个权重向量分别为在网络结构比对过程中网络Ｇ中　结点到网络日中结点的权重二分图　中每个边的对　数似然函数和网络日中结点到网络Ｇ中结点的权重　二分图　中每个边的对数似然函数和；权重矩阵是指　比对结果中边缘重叠的对数似然函数。这些权重值　被叫做消息。在每次更新消息后，都要在二分图比对　过程中循环消息，之后重新评价目标函数。　置信传播算法方法　是一种很有效的求解　条件边缘概率的方法。通过局部的消息传递，网络　中的每个结点通过和邻近结点交换信息对自身的概　率状况进行评估，更新准则由已知变量推理未知变　量。通过这种方式，使得计算量从指数增长变成近　似的线性增长，从而使得统计推断能在复杂系统中　被应用。置信传播方法（ＢＰ）可以正确的找到优化　问题的最优解，当然也包括最大权重的匹配问题。　２．１．２并行网络一致性的实现　网络结构比对的并行运算是使用ＯｐｅｎＭＰ　共　享内存并行系统的多线程程序。所有需要的内存是　在第１次迭代之前设定的。没有动态内存的分配并　且要避免计算中间结果，并行比对的矩阵都是系数　矩阵并且以压缩的稀疏行数组的形式保存。考虑到　矩阵　的不确定性，使用动态的ＯｐｅｎＭＰｌ３　的并行　算法会比静态的算法有更好的效果。　在更新矩阵的时需要额外的并行运算，Ｋｌａｕ　Ｓ　算法的迭代过程不依赖于二分图的比对过程，但是　置信传播（ＢＰ）算法需要解决二分图比对问题，因为　、Ｃ迭代的质量会随着它的迭代而变化。由于最　后跌迭代的结果往往不如中间迭代的结果，所以需　要保存最后几步迭代的结果，同时对这些结果的质　量进行评估。要对不好的结果进行成批的舍去，提　高代码的伸缩性。　以上算法主要应用在生物网络结构比对方　面　和本体比对方面　，　引。　２．１．３矩阵特征值法　矩阵特征值法是一种基于谱的比对方法。它通　过矩阵建立网络结构比对模型，使用矩阵的特征值　计算比对网络的结点相似性，最后使用搜索算法得　到网络结构比对的结果。以矩阵的特征值计算结点　相似的方法是由ＰａｇｅＲａｎｋ算法　首先提出来的，　Ｉｓｏｒａｎｋ方法把这种算法应用到网络结构比对的计　算中。结点对比对的基本思想是只有结点对的相邻　结点对相似它们才可能有相似关系。这个思想阐述　了结点与邻居结点紧密相连的关系。ＩｓｏｒａｎｋＮ算　法　同样是应用此种思想，不同的是ＩｓｏｒａｎｋＮ算法　使用在　部图上运行。通过谱聚类算法ＰａｇｅＲａｎｋ　第４期　刘富，等：复杂网络结构比对算法研究进展　Ｎｉｂｂｌｅ　Ｅ　比对相似功能模块。算法ＳＰＩＮＡＬ［。　也是　秉承Ｉｓｏｒａｎｋ算法中结点对的比对的思想，但是它在　此基础上提出了结点相邻结点的集合（Ｎ（Ｖ），　』】、，（Ｕ））的概念。　２．１．４　Ｉｓｏｒａｎｋ算法的基本思想　由图３所示口、ｂ、ｃ、ｄ、ｅ是网络Ｇ中的结　点；ｎ　、ｂ　、Ｃ　、ｄ　、ｅ　是网络日中的结点。结点对　（０，口　）的相似得分是由它们的相邻结点（ｂ，ｂ　）的　相似性决定。因为结点０和结点ｃ都与结点ｂ相邻，　所以结点ｂ对０的贡献是１／２，同理结点ｂ　对结点的　贡献也是１／２。所以可以得到结点对（０，ｒｚ　）和结　点对（ｂ，ｂ　）的关系式Ｒ…＝Ｒ　／４依次关系可以得　到如下结点的关系：　，＝　＋　。，　。，＋　，　Ｒ以，＝Ｒ　，／９　１　Ｒｃｃ，＝　Ｒ　＋丢尺　＋÷尺　＋扣　＋　１　－４　－Ｒ幽，＋Ｒ　，＋Ｒ　＋Ｒ　，＋Ｒｄｄ，　（４）　（ａ）Ｊ网络Ｇ　（ｂ）网络Ｈ　图３结点比对图　Ｆｉｇ．３　Ｎｅｔｗｏｒｋ　ｏｆ　ｎｏｔｅ　ａｌｉｇｎｍｅｎｔ　２．１．５　网络结构比对问题的矩阵定义规范　Ｎ（Ｖ）和Ⅳ（　）表示结点　和结点１２，的相邻结　点，　（ｅ）表示边缘权重值，　表示结点对ｉ，　的相　似得分。依据结点得分方法可得到结点比对的矩　阵定义公式：　Ｒ＝ＡＲ　（５）　是Ａ矩阵特征值所对应的特征向量。由随　机矩阵Ａ的性质可知，１是矩阵Ａ的模最大的特征　值，Ｒ是Ａ矩阵模最大的特征值对应的特征向量。　通过使用幂方法　求解Ｒ。幂方法是按照更新法　则（６）不断更新只得到的，其中Ｒ（ｋ）表示对Ｒ的ｋ　次迭代。　Ｒ（ｋ＋１）一ＡＲ（ｋ）ｌＡＲ（ｋ）ｌ　（６）　通过上述步骤构建比对问题的模型。把比对问　题转化为通过幂方法求解求矩阵的特征值问题，得　到结点相似得分　。最后使用贪婪算法提取出结　点对的映射关系。　２．１．６基于数学框架网络结构比对方法的特点　１）构建复杂网络结构比对的规范数学公式。　例如整数二次规划问题和矩阵特征值问题。　２）规范数学公式求解问题。例如采用拉格朗　日松弛法＼置信传播算法以及幂方法求解。　３）解的映射关系的提取。在得出结点对的相　似得分之后，需要把比对的结果还原到原来的网络　中，对最大相似区域的进行比对。　２．２基于图的网络结构比对方法　基于图的网络结构比对方法从比对范围可分为　全局网络结构比对方法、局部网络结构比对方法。　全局网络结构比对方法对结点的映射关系有一定的　限制，结点之间的映射关系必须是一一对应的关系。　局部网络结构比对方法是在２个网络中找到局部的　同构区域，其中局部的区域是独立的映射关系。与　全局网络结构比对不同的是，局部网络结构比对的　结点的映射关系可以是多对一或者一对多的关系。　从比对结果上来说，全局比对可以得到唯一精确的　最大的公共子图的比对结果，局部比对得到的是局　部最优的比对结果。但是当使用不同的局部比对算　法常常会得到不同的比对结果。所以从实际应用上　来分析，２种方法有各自的优缺点。局部蛋白质比　对的研究算法已经相对成熟，全局蛋白质网络结构　比对算法还在深入探索中。　ＰａｔｈＢＬＡＳＴ　驯算法通过考虑被比对的结点的同　源性和结点数据在路径上正确概率上来搜索高分途　径的局部网络结构比对方法。ＮｅｔｗｏｒｋＢＬＡＳＴ　算　法是通过发现保守的结点集群进行比对的方法，它　的特点是通过建立ｌｉｋｅｌｉｈｏｏｄ—ｂａｓｅｄ模型得到结点权　重值和边缘权重值的比对图，把网络结构比对问题　转化通过启发式算法搜索权重最大子图问题。权衡　子网络的密集程度和类似随机子网络结构的密集程　度，有利于提高比对结果的统计显著性，它能够同时　比对多个网络。ＭａＷＩＳｈ　算法通过ｅｖｏｌｕｔｉｏｎ．　ｂａｓｅｄ分数表来确定保守集群。它延伸了在序列比　较中的进化事件的概念，把序列比对中的空隔、匹配　和失配扩展为网络结构比对中的复制、匹配和失配，　并通过记分函数评估网络结构的相似结构。Ｇｒａｅｍ．　１ｉｎ　４　算法是第１个能够识别任意结构的保守子　网的密度的算法。它是一种基于“ｓｅｅｄ—ａｎｄ—ｅｘｔｅｎｄ”　的贪婪算法。它可以识别不同物种的进化保存功能　模块。通过计算模块受进化约束比率的ｌｏｇ—ｒａｔｉｏ给　模块打分，并且在比对中模块是不受限制的。这种　方法既可以进行全局比对，也可以局部比对。ＭＨＡ　智能系统学报　第１０卷　方法　通过ＰｒｏｐｏｒｔｉｏｎａｌＨｉｌｌ＿４４　算法定义结点成员　性的概念。结点成员性概念可以确定在什么范围内　结点可以参与到功能模块上，从而确保提取到完整　的不受破坏的功能模块。ＨｏｐｅＭａｐ算法　提出一　个通用的评分系统，用来寻找最高得分的子图。在　考虑结果的应用性时，在比对过程中就把要求的比　用到各种类型的网络结构比对中，包括生物网络结　构比对，社交网络结构比对等。在文献［４７］中首次　在网络结构比对问题中提出标签相似（ｓｉｇｎａｔｕｒｅ　１　Ｉ　ｓｉｍｉｌａｒｉｔｙ）概念。　◇＿．王　１）标签相似　６　７　（　诱导子图的结点　∈　并且结点　在网络Ｇ中　对结果的相关信息融人算法中。　下面主要介绍一种可以应用于任何网络的基于　图拓扑结构网络结构比对算法。　２．２．１　基于图拓扑结构网络结构比对算法　相连的边缘也都在诱导子图中。对于所有的２～５　个结点的诱导子图，在考虑结点在诱导子图的对称　性时，２—５个结点的诱导子图会有７３种不同的轨　迹。如图４～７所示。２～５个结点的７３个轨道是描　ＧＲＡＡＬ算法ｌ４　是典型的基于拓扑结构的网　络结构比对算法，ＧＲＡＡＬ算法只需要网络的拓扑结　述结点的相邻拓扑关系的一种标签并且可以确定到　与这个结点的距离的相互联系。　构信息，不需要其他的网络的先验信息。它可以应　（ｂ）Ｇ　。　（ｃ）Ｃ．．　（ｄ）Ｇ　：　（ｅ）Ｇ　象　（ｋ）Ｇ　６　＇３８一　（ｍ）Ｇ：　（ｎ）Ｇ：：　Ｘ　４（ｏ）Ｇ：　６４　５　（ｐ）Ｇ　（ｑ）Ｇ　（ｒ）Ｇ：。　（ｓ）Ｇ　（ｔ）Ｇ　（ｕ）Ｇ　。　图７　５节点诱导子图的轨迹　Ｆｉｇ．７　Ｔｒａｃｋ　ｏｆ　ｉｎｄｕｃｅｄ　ｓｕｂｇｒａｐｈ　ｏｆ　５　ｎｏｔｅｓ　在ｉ方向上的结点对（　，Ｕ）的距离如式（７）所示：结　点Ｕ∈Ｇ，Ｕ　表示结点在ｉ方向上的标签向量，即结　点“在ｉ这个方向上出现的次数。　　Ｉｌｏｇ（ｕ　＋１）一ｌ０ｇ（　＋１）ｌ　Ｄｉ（ｖ，ｕ）　Ｗｉ×—　１０　ｇｌ　ｍａ　ｘ　ｕ　．　．｝十　Ｊ　向量相差几个数量级，在对数函数中加１是为了防　止产生无限大的结果。由此可以算出结点对　（　，“）的整体距离：　∑Ｄ　（７）　Ｄ（　，ｕ）＝　（８）　式中：Ｗ　表示ｉ方向的路径与其他路径的权重值。　用对数计算距离是因为在ｉ方向上２个结点的特征　式中：Ｄ（　，　）∈［０，１）。当Ｄ（ｖ，“）＝０时，就认定　第４期　刘富，等：复杂网络结构比对算法研究进展　・５１３・　和ｕ是相同的结点。　把结点对Ｄ（　，“）标签相似得分Ｓ（　，　）公式　如式（９）所示：　Ｓ（　，Ｍ）＝１一Ｄ（　，　）　（９）　Ｄ（　，“）的值越大，表示在ｕ，　这２个结点上　有更相似的拓扑结构。　２）结点对得分公式　结点对的相似得分随着结点的度的变化而改　变，结点的度越大，结点的相似性就越低，在相同的　标签相似中它的结构更紧凑。　结点对的相似得分公式如式（１０）：　Ｃ（　，∽＝　２一（（１一　）×　：　ｄ　ｅｉｇ　（云ｕ　）—　＋　ｄ　ｅ　ｇ　（＝ｖ＝　）　＋　ｍａｘ—ＣＩｅｇｌ　Ｌｒ　Ｊ　十ｍａｘ－ＣＩｅｇＩ　ｆｌ　Ｊ　Ｘ　Ｓ（Ｖ，∽　（１０）　式中：Ｃ（Ｖ，Ｕ）∈［０，２】中；ｄｅｇ（Ｍ）表示结点“　的度，结点的度是指其他结点于此结点相连的个　数，通过结点的度的关系确定结点的相似的思路　是求解结点相似性的通用做法。ｍａｘ—ｄｅｇ（Ｇ）是　在网络Ｇ中的存在的最大的度，公式的前部分是　通过网络中结点的度来区分结点问的相互作用　关系，公式的后半部分是通过节点在网络中的拓　扑结构来区分结点间的相互作用关系的。　是一　个参数，控制结点标签相似（ｎｏｄｅ　ｓｉｇｎａｔｕｒｅ）与代　价函数的比率。这个公式的Ｃ（Ｖ，Ｕ）值表示同　一网络中不同结点间的相似程度。通过结点的　度的关系确定结点的相似的思路是求解结点相　似性的通用做法。Ｃ（Ｖ，Ｕ）的值越小表示结点　和结点ｕ的结点越相似，如果Ｃ（Ｖ，Ｕ）的值为０　表示节点　、　是同一结点，如果Ｃ（Ｖ，Ｕ）的值　为２表示节点　、　是完全不同的结点。　３）网络结构比对算法　首先选择最小值的Ｃ（　，Ｕ）为种子结点。然　后以种子结点为中心向外扩展，进行搜索，搜索时遵　循一定的规则，可假设存在一个球体，这个球体的圆　心分别为种子结点　和ｕ，半径为任何可能的一个　定值，之后通过ｇｒｅｅｄ算法找到结点（ｕ　，　）对集合　其中　∈ＳＧ（　，ｒ）＝｛　∈　：ｄ（　，　）：ｒ），其中公式　中Ｍ　∈Ｓ　（　，ｒ）。最后将结点对集合（　，　）中所　有的结点进行比对，找出最小Ｃ值的结点对。　Ｈ—ＧＲＡＡＬ算法是ＧＲＡＡＬ算法的改进算法。　这种算法得到一个最优的网络结构比对集合。Ｈ－　ＧＲＡＡＬ算法进行比对的时候采用了动态的匈牙利　算法　。对于动态匈牙利算法只需要改变匈牙利　算法　返回的最优结点对（　，“）的Ｃ值。　Ｃ—ＧＲＡＡＬ算法　提出了在网络结构比对结点　相邻结点的共同结点的概念。Ｃ．ＧＲＡＡＬ算法是在　ＧＲＡＡＬ算法的基础上加入相邻结点的共同结点的　比对。如果具有最大值的共同结点的结点相似得分　很高，就将结点保留，否则，将结点从比对结果中删　除，反之，如果已经比对的结点对的相似得分很大，　但是却没有共同相邻结点，同样删除。　ＧＲＡＡＬ算法和Ｈ—ＧＲＡＡＬ算法属于基于集群　的算法。与其他算法通过密集的相互连接的区域定　义集群不同，ＧＲＡＡＬ算法把具有相同拓扑特征的结　点集或者属于相同网络区域定位集群，属于相同的　拓扑结点不需要相互连接。ＧＲＡＡＬ算法通过蛋白　质网络的拓扑性质推算出２个网络中结点对的相似　得分。在得到比对结点对的相似得分后，使用贪婪　算法或者匈牙利算法进行搜索。　２．２．２基于图拓扑结构网络结构比对方法的特点　１）建立比对图，通过整合网络中结点和结点之　间的相互作用的相关数据，构造出网络结构比对的　二分图。　２）定义结点相似得分函数，依据复杂网络的特　性，设计出网络的结点的相似得分比较方法，将网络　结构比对问题转化为求解比对图的问题。　３）设计搜索算法，在众多启发式算法中选择一　种适合待比对图特性的搜索算法。完成结点对的比　对问题。与基于数学框架网络结构比对方法不同，　不需要把比对结果还原到原来的网络中。这种方法　得到的对比对结果会直接的反映到比对图上。直接　得到最大权重比对子图　。　２．３　网络结构比对的其他算法　ＮＳＤ算法　是一种结合相似得分计算的“拆　开”（输入数据的独立的预处理）和“分解”的排名的　网络结构比对问题。ＤＮＳ方法优点是可以快速计　算网络拓扑中的结点相似性，并且这种方法可以比　对任何拓扑网络。它的参数和输出处理都可以为特　定的比对问题而变化。腔算法　是一种分布式算　法。他可以有效地处理全局拓扑约束下优化问题。　交互概率　网络结构比对方法是通过概率生成函　数来有效地在复杂网络中计算结点度分布。Ｃｏｒｂｉ　算法　通过采取迭代的双向映射的方法进行网络　结构比对。它在比对过程中考虑进化事件，包括结　点的插入与删除、边缘的连接与分离。并且这种方　法从匹配的结点数目、边缘正确率、边缘覆盖率和最　大的共同的连通子图的大小等方面分析网络比较结　果的好坏。文献［５４］介绍了一种通过ｅ　模型　进　行网络结构比对的一种方法。ｅ　算法的目标是在有　智能系统学报　第１０卷　限的时间步数内收敛到一个近似最优结果。该文献　介绍了ｅ。模型在比对ｂｕｓｉｎｅｓｓ—ＩＣＴ网络上的应用，　ｅ　模型算法创造了在组织比对情况下使用多种结点　进行比对，不仅仅限制在一种结点比对上。离散的　粒子群优化算法　是一种可以部署目标函数的一　种优化启发。　３　复杂网络结构比对存在的问题　复杂网络结构比对问题是对数学、信息学、计算　机科学和真实网络的相关知识的综合交叉领域的研　究。例如，近几年在网络结构比对问题上热门的生　物网络结构比对问题，就需要有相关的生物知识作　为重要的理论支撑，需要清楚在生物网络结构比对　过程中哪些信息对比对的结果至关重要，研究哪些　组合优化算法和生物网络中的哪些特殊性会对这个　特定的网络有更好的比对结果。当然在对这些信息　研究的同时，需要有数学方法、信息学的基础理论和　计算机等相关的学科知识作为基础。需要数学的思　想方法和工具为各种学科做基础，需要信息学的理　论对相关数据进行信息分析和处理，需要用计算机　科学作为数据承载、处理和呈现的介质。在此，在复　杂网络结构比对研究中对数据的预处理、结点相似　性、结果评估问题这３个亟需解决的问题进行分析。　１）复杂网络数据的预处理问题　随着各种网络数据的快速增长，对数据的提取　和处理也就成了一个既重要又困难的事情。对于生　物网络这种特殊的网络来说，数据的提取就是一件　复杂的事情，因为生物网络数据的来源是生物数据　库，但这些数据库不仅仅有结点和相互作用关系的　数据，还存在数据的来源、实验的方法等具体的信　息，如何从数据库中提取感兴趣的数据是很重要的。　也可以将网络数据抽象为图，将实验数据中的网络　数据信息转换成图中顶点和边上的属性。　数据的预处理就更加困难，由于数据本身的具　有的大量性和噪声性。如何建立高可信度的模型是　需要解决的问题。对于网络数据的处理来说，现在　主要有２个处理方向，一个方向是通过计算分析技　术来评估和排名　网络数据中相互作用关系的　可靠性。这种方法主要是通过对相互作用的网络数　据的局部分析和全局分析来监测数据。局部分析通　过是否有共同的定位数据或有共同作用的数据的这　２个条件判断这组数据是否可靠。文献［５８—５９］通　过对数据来源可靠性的判断微调局部分析的结果。　经典网络比对方法　∞　通过给复杂网络中的相互　作用数据赋一个权重来说明数据的可信度。文献　［６０］使用多种数据源建模可信数据。这种方法的　不足是在处理稀疏矩阵　的时候，它的效果会急剧　下降。　据建模成欧几里得空间的点集合　，这种方法　主要是先设定距离参数￡，如果２点之间的距离小　于ｓ，就可以表示这２点之间的相互作用是可靠的。　这种方法也是近几年的一种趋势。文献［６３—６４］介　绍了一种非凸语义嵌入的方法，在相互作用数据中　使用自适应欧几里得嵌入方法，这种在欧几里得空　间中求距离的方法适用于紧密相连的数据库和系数　的数据库。但是以上的方法对假阴性数据的检测是　十分困难的，因为检测假阴性数据可靠性等同于对　预测新的相互作用关系。处理后的数据依然存在一　定比例的假阴性与假阳性，如何提高处理数据的能　力也是接下来要着重解决的问题。　２）结点的相似性范围计算问题　结点的相似性计算是网络结构比对的基础，在　基于数学框架网络结构比对方法中，相似性是定义　整数二次规划和矩阵特征值公式的基础，在基于图　拓扑结构网络结构比对算法中，结点的相似性计算，　是网络结构比对的核心问题，只有在结点的相似性　已知的前提才可进行启发式的搜索算法寻找最大公　共子图。经典算法Ｇｒａｅｍｌｉｎ２．０　在网络数据的序　列数据和拓扑结构相似数据的基础上将功能相似性　引入到相似度函数定义中。但是在得到结点的相似　得分之后，如何确定匹配结点的相似得分范围是一　个需要深入分析的问题。ＭＨＡ　方法通过Ｐｒｏｐｏｒ—　ｔｉｏｎａｌＨｉｌｌ＿４４　算法预测功能模块的范围，但是这种方　法获得数据的准确率不是很高，其次确定相似得分　范围的方法都通过对特定的网络进行大量的实验，　验证什么范围内的结点会有更好的比对结果。这种　方法需要大量的工作量，因为就算是对同一种类型　网络的进行比对，不同的网络结点匹配的相似性范　围也是不同的。如何使网络的比对算法自动地确定　匹配的相似得分范围是当前要解决的问题之一。　３）复杂网络结构比对结果评估问题　现在没有一种标准规范来评价网络结构比对的　结果。现在对网络结构比对结果的评估主要是在比　对算法的执行效率方面和运行结果方面估。对网络　结构比对的结果评估首先建立一组和原有网络一致　的随机网络并在上面运行比对算法，基于随机网络　上的比对结果和真实网络上的比对结果设定评价标　准，得到评价函数，解释算法统计的显著性。但是对　网络结构比对结果的实际应用性方面分析，却没有　统一的标准。例如在生物网络结构比对结果的中得　第４期　刘富，等：复杂网络结构比对算法研究进展　到了相对应的结点，但最终匹配的结点的正确率却　没有被实际的统计过。算法Ｇｒａｅｍｌｉｎ２．０　是第１　个方法提出网络比对评价的基准，它将自己的方法　与ＮｅｔｗｏｒｋＢＬＡＳＴ［３８］、ＭａＷＩＳＨ［　、ＩｓｏＲａｎｋ［１３］以及　Ｇｒｚｅｍｌｉｎｌ４　等４种方法进行了量化评测。　ＨｏｐｅＭａｐ¨２　算法提出一个通用的评分系统，这个方　法提出将网络比对的结果和多种数据注释方法进行　比较，得到一个较为通用的正确率。从网络匹配的　正确率这方面来说这就需要生物相关的技术与计算　机技术相协作，最终提高网络结构比对的实用性。　复杂的网络结构比对方法还在进一步研究中，但是　增大比对网络的范围和设计更有效的结果分析方案　是必要的　４　结束语　通过改进和完善复杂网络比对方法，把这种方　法应用到各种规模各种形式上的网络数据中，比对　具体的网络数据来解决实际问题。除了现在普遍使　用的启发式方法和线性规划方法，其他的解决方案　可能也会有更好的比对效果，例如结合参数化方法，　值得人们深入研究。　复杂网络结构比对是近年来研究热点之一，考　虑到复杂网络的模块性和实际网络的动态性，复杂　网络结构比对算法发展的主要发展趋向３个方面：　１）识别重叠的网络结构比对部分。现在算法　对于结点映射关系是一一对应的，但在现实的很多　网络中结点是具有重叠性，例如生物网络中的进化　模块，很多结点都是重叠的。所以在未来的网络结　构比对算法要释放网络结点比对一对的一映射的限　制。模糊聚类法　舶　和中心发现法　都可以用来　识别重叠模块　２）构建动态的网络结构比对模型。随着对复　杂网络的深入研究，现在已经有很多算法对复杂网　络进行动态性研究　引。动态性研究提高了对复杂　网络的认识，把网络的动态研究扩展到构建动态网　络结构比对模型的应用上是十分重要的，现在已经　有一些动态网络研究的成果　ｍ　Ｊ。　３）联系具体网络的属性，进行具有特定性的网　络结构比对研究。例如对生物网络的比对，就需要　在生物网络中结点以及相互作用所具有的生物属　性　，例如生物网络的结点具有保守性和进化性。　今后需要面对的挑战是，如何对这些数据进行　预处理，把它们变成高质量的网络；如何集成并归集　多个信息源将数据；如何提高网络结构比对的精度；　如何依据具体的网络数据的不同性质的网络结构的　比对来解决实际问题。　参考文献：　１　ｌ　ＳＴＥＬＺＬ　Ｕ，ＷＯＲＭ　Ｕ，ＬＡＬＯＷＳＫＩ　Ｍ，ｅｔ　ａ１．Ａ　ｈｕｍａｎ　ｐｒｏｔｅｉｎ—ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋ：ａ　ｒｅｓｏｕｒｃｅ　ｆｏｒ　ａｎｎｏｔａ—　ｉｒｎｇ　ｔｈｅ　ｐｒｏｔｅｏｍｅ［Ｊ］．Ｃｅｌｌ，２００５，１２２（６）：９５７—９６８．　［２］ＲＥＮ　Ｂ，ＲＯＢＥＲＴ　Ｆ，ＷＹＲＩＣＫ　Ｊ　Ｊ，ｅｔ　ａ１．Ｇｅｎｏｍｅ—ｗｉｄｅ　ｌｏ—　ｃａｔｉｏｎ　ａｎｄ　ｆｕｎｃｔｉｏｎ　ｏｆ　ＤＮＡ　ｂｉｎｄｉｎｇ　ｐｒｏｔｅｉｎｓ［Ｊ］．Ｓｃｉｅｎｃｅ，　２０００，２９０（５５００）：２３０６—２３０９．　［３］ＭＩＣＨＯＥＬ　Ｔ，ＮＡＣＨＴＥＲＧＡＥＬＥ　Ｂ．Ａｌｉｇｎｍｅｎｔ　ａｎｄ　ｉｎｔｅｇｒａ—　ｔｉｏｎ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｂｙ　ｈｙｐｅｒｇｒａｐｈ・－ｂａｓｅｄ　ｓｐｅｃｔｒａｌ　ｅｌｕｓ－－　ｔｅｒｉｎｇ［Ｊ］．Ｐｈｙｓｉｃａｌ　Ｒｅｖｉｅｗ　Ｅ，２０１２，８６（５）：０５６１１１．　［４］ＥＲＤＯ　Ｓ　Ｐ，Ｒ　ＮＹＩ　Ａ．Ｏｎ　ｔｈｅ　ｅｖｏｌｕｔｉｏｎ　ｏｆ　ｒａｎｄｏｍ　ｇｒａｐｈｓ　Ｊ　１．Ａｍｅｒｉｃａｎ　Ｍａｔｈｅｍａｔｉｃａｌ　Ｓｏｃｉｅｔｙ，１９６０，５　１７—５６１．　Ｉ　５　ｌ　ＢＯＮＮＩＣＩ　Ｖ，ＧＩＵＧＮＯ　Ｒ，ＰＵＬＶＩＲＥＮＴＩ　Ａ，ｅｔ　ａ１．Ａ　ｓｕｂ—　ｇｒａｐｈ　ｉｓｏｍｏｒｐｈｉｓｍ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｂｉｏｃｈｅｍｉ—　ｃａｌ　ｄａｔａ［Ｊ］．ＢＭＣ　ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２０１３，１４（Ｓｕｐｐｌ　７）：　Ｓ１３．　［６］ＫＨＡＮ　Ａ　Ｍ，ＧＬＥＩＣＨ　Ｄ　Ｆ，ＰＯＴＨＥＮ　Ａ，ｅｔ　ａ１．Ａ　ｍｕｌ—　ｔｉｔｈｒｅａｄｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ　ｖｉａ　ａｐｐｒｏｘｉｍａｔｅ　ｍａｔｃｈｉｎｇ［Ｃ］／／２０１２　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｐｒｏｃｅｅｄ—　ｉｎｇｓ　ｏｆ　ｔｈｅ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｉｎｇ，Ｎｅｔｗｏｒｋｉｎｇ，Ｓｔｏｒ—　ａｇｅ　ａｎｄ　Ａｎａｌｙｓｉｓ（ＳＣ）．２０１２．　［７］ＴＯＤＯＲ　Ａ，ＤＯＢＲＡ　Ａ，ＫＡＨＶＥＣＩ　Ｔ．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｂｉｏｌｏｇｉ—　ｃａｌ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ『Ｊ　１．ＩＥＥＥ／ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｂｉｏｌｏｇｙ　ａｎｄ　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ（ＴＣＢＢ），２０１３，　ｌ０（１）：１０９—１２１．　［８］ＳＨＶＡＩＫＯ　Ｐ，ＥＵＺＥＮＡＴ　Ｊ．Ｏｎｔｏｌｏｙｇ　ｍａｔｃｈｉｎｇ：ｓｔａｔｅ　ｏｆ　ｔｈｅ　ａｒｔ　ａｎｄ　ｆｕｔｕｒｅ　ｃｈａｌｌｅｎｇｅｓ『Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｋｎｏｗｌ　ｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１３，２５（１）：１５８－１７６．　［９］ＢＯＣＫ　Ｊ，ＨＥＴＴＥＮＨＡＵＳＥＮ　Ｊ．Ｄｉｓｃｒｅｔｅ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐ—　ｔｉｍｉｓａｔｉｏｎ　ｏｆｒ　ｏｎｔｏｌｏｇｙ　ａｌｉｇｎｍｅｎｔ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，　２０１２，１９２：１５２—１７３．　［１Ｏ　３ＨＵ　Ｗ，ＪＩＡＮ　Ｎ，ＱＵ　Ｙ，ｅｔ　ａ１．Ｇｍｏ：ａ　ｇｒａｐｈ　ｍａｔｃｈｉｎｇｆｏｒ　ｏｎｔｏｌｏｇｉｅｓ［Ｃ］／／ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｋ—ＣＡＰ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｉｎｔｅｇｒａｔｉｎｇ　Ｏｎｔｏｌｏｇｉｅｓ．２００５：４２—４８．　［１　１］ＭＥＬＮＩＫ　Ｓ，ＧＡＲＣＩＡ—ＭＯＬＩＮＡ　Ｈ，ＲＡＨＭ　Ｅ．Ｓｉｍｉｌａｒｉｔｖ　ｌｆｏｏｄｉｎｇ：ａ　ｖｅｒｓａｔｉｌｅ　ｇｒａｐｈ　ｍａｔｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔｓ　ｐ—　ｐｌｉｃａｔｉｏｎ　ｔｏ　ｓｃｈｅｍａ　ｍａｔｃｈｉｎｇ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｐｒｏｃ　１　８ｔｈ　ＩＣＤＥ　Ｃｏｎｆ（Ｂｅｓｔ　Ｓｔｕｄｅｎｔ　Ｐａｐｅｒ　ａｗａｒｄ）．２００２．　［１２］ＫＬＡＵ　Ｇ　Ｗ．Ａ　ｎｅｗ　ｇｒａｐｈ—ｂａｓｅｄ　ｍｅｔｈｏｄ　ｏｆｒ　ｐａｉｒｗｉｓｅ　ｇｌｏｂａｌ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ［Ｊ］．ＢＭＣ　ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２００９，１０　（Ｓｎｐｐｌ　１）：￥５９．　［１３］ＳＩＮＧＨ　Ｒ，ＸＵ　Ｊ，ＢＥＲＧＥＲ　Ｂ．Ｐａｉｒｗｉｓｅ　ｇｌｏｂａｌ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｂｙ　ｍａｔｃｈｉｎｇ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｔｏｐｏｌｏｇｙ［Ｊ］．２００７：１６—３１．　［１４］ＳＩＮＧＨ　Ｒ，ＸＵ　Ｊ，ＢＥＲＧＥＲ　Ｂ．Ｇｌｏｂａｌ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｍｕｌｔｉ—　ｐｌｅ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｆｕｎｃ—　ｔｉｏｎａｌ　ｏｒｔｈｏｌｏｇｙ　ｄｅｔｅｃｔｉｏｎ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，２００８，１０５（３５）：１２７６３—１２７６８．　［１５］ＬＡＷＬＥＲ　Ｅ　Ｌ．Ｔｈｅ　ｑｕａｄｒａｔｉｃ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ［Ｊ］．　Ｍａｎａｇｅｍｅｎｔ　Ｓｃｉｅｎｃｅ，１９６３，９（４）：５８６—５９９．　［１６］ＭＩＳＥＮＥＲ　Ｒ，ＦＬＯＵＤＡＳ　Ｃ　Ａ．ＧｌｏＭＩＱＯ：Ｇ１ｏｂａｌ　ｍｉｘｅｄ—　ｉｎｔｅｇｅｒ　ｑｕａｄｒａｔｉｃ　ｏｐｔｉｍｉｚｅｒ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｇｌｏｂａｌ　Ｏｐｔｉｍｉｚａ—　・５１６・　智能系统学报　第１０卷　ｔｉｏｎ，２０１２，５７（１）：　［１　７］ＲＩＥＣＫ　Ｊ，ＺＩＭＭＥＲＭＡＮＮ　Ｊ，ＧＡＴＨＥＲ　Ｔ．Ｍｉｘｅｄ—ｉｎｔｅｇｅｒ　ｌｉｎｅａｒ　ｐｒｏｇｒａｍｍｉｎｇ　ｆｏｒ　ｒｅｓｏｕｒｃｅ　ｌｅｖｅｌｉｎｇ　ｐｒｏｂｌｅｍｓ［Ｊ］．Ｅｕ—　ｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，２０１２，２２１（１）：　２７—３７．　［１８］ＢＲＡＤＤＥ　Ｓ，ＢＲＡＵＮＳＴＥＩＮ　Ａ，ＭＡＨＭＯＵＤＩ　Ｈ，ｅｔ　ａ１．Ａ—　ｌｉｇｎｉｎｇ　ｇｒａｐｈｓ　ａｎｄ　ｆｉｎｄｉｎｇ　ｓｕｂｓｔｒｕｃｔｕｒｅｓ　ｂｙ　ａ　ｃａｖｉｔｙ　ａｐ—　ｐｒｏａｃｈ［Ｊ］．ＥＰＬ（Ｅｕｒｏｐｈｙｓｉｃｓ　Ｌｅｔｔｅｒｓ），２０１０，８９（３）：　３７００９．　［１９］ＢＡＹＡＴＩ　Ｍ，ＧＥＲＲＩＴＳＥＮ　Ｍ，ＧＬＥＩＣＨ　Ｄ　Ｆ，ｅｔ　ａ１．Ａｌｇｏ—　ｒｉｔｈｍｓ　ｏｆｒ　ｌａｒｇｅ，ｓｐａｒｓｅ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍｓ［Ｊ］．　２００９，７０５—７１０．　［２０］ＥＬ—ＫＥＢＩＲ　Ｍ，ＨＥＲＩＮＧＡ　Ｊ，ＫＬＡＵ　Ｇ　Ｗ．Ｌａｇｒａｎｇｉａｎ　ｒｅ—　ｌａｘａｔｉｏｎ　ａｐｐｌｉｅｄ　ｔｏ　ｓｐａｒｓｅ　ｇｌｏｂａｌ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ［Ｍ］．　Ｓｐｒｉｎｇｅｒ．２０１　１：２２５—２３６．　［２　１］ＧＵＩＧＮＡＲＤ　Ｍ，ＫＩＭ　Ｓ．Ｌａｇｒａｎｇｅａｎ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ：ａ　ｍｏｄｅｌ　ｙｉｅｌｄｉｎｇ　ｓｔｒｏｎｇｅｒ　Ｌａｇｒａｎｇｅａｎ　ｂｏｕｎｄｓ［Ｊ］．Ｍａｔｈｅ—　ｍａｔｉｃａｌ　Ｐｒｏｇｒａｍｍｉｎｇ，１９８７，３９（２）：２１５—２２８．　［２２］ＳＩＮＧＨ　Ｒ，ＸＵ　Ｊ，ＢＥＲＧＥＲ　Ｂ．Ｇｌｏｂａｌ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｍｕｌｔｉ—　ｐｌｅ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｆｕｎｃ—　ｔｉｏｎａｌ　ｏｒｔｈｏｌｏｇｙ　ｄｅｔｅｃｔｉｏｎ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ　ｏｆ　ｔｈｅ　Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ　ｏｆ　Ａｍｅｒｉｃａ，　２００８，１０５（３５）：１２７６３—１２７６８．　［２３］ＫＥＣＥＣＩＯＧＬＵ　Ｊ．Ｔｈｅ　ｍａｘｉｍｕｍ　ｗｅｉｇｈｔ　ｔｒａｃｅ　ｐｒｏｂｌｅｍ　ｉｎ　ｍｕｌｔｉｐｌｅ　ｓｅｑｕｅｎｃｅ　ａｌｉｇｎｍｅｎｔ［Ｃ］／／ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｃｏｍｂｉｎａｔｏｒｉａｌ　ｐａｔｔｅｒｎ　ｍａｔｃｈｉｎｇ．Ｓｐｒｉｎｇｅｒ．１９９３：１０６—１　１９．　［２４］ＳＡＭＡＴＯＶＡ　Ｎ　Ｆ．Ｇｌｏｂａｌ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｐａｉｒｗｉｓｅ　ｐｒｏｔｅｉｎ　ｉｎ—　ｔｅｒａｅｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｍａｘｉｍａｌ　ｃｏｍｍｏｎ　ｃｏｎｓｅｒｖｅｄ　ｐａｔｔｅｒｎｓ　　ｌＪ｝．Ｉｎｔｅｒｎａｔｉｏｎａ１　Ｊｏｕｒｎａｌ　ｏｆ　Ｇｅｎｏｍｉｃｓ，２０１３：６７０６２３．　２５］ＢＡＵＥＲ　Ｍ，ＫＬＡＵ　Ｇ　Ｗ，ＲＥＩＮＥＲＴ　Ｋ，ｅｔ　ａ１．Ａｃｃｕｒａｔｅ　ｍｕｈｉｐｌｅ　ｓｅｑｕｅｎｃｅ—ｓｔｒｕｃｔｕｒｅ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ＲＮＡ　ｓｅｑｕｅｎｃｅｓ　　ＩＪ　１．ＢＭＣ　Ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２００９：１５－３３．　［２６］ＢＡＹＡＴＩ　Ｍ，ＳＨＡＨ　Ｄ，ＳＨＡＲＭＡ　Ｍ．Ｍａｘ—ｐｒｏｄｕｃｔ　ｆｏｒ　ｍａｘｉｍｕｍ　ｗｅｉｇｈｔ　ｍａｔｃｈｉｎｇ：ｃｏｎｖｅｒｇｅｎｃｅ，ｃｏｒｒｅｃｔｎｅｓｓ，　ａｎｄ　ＬＰ　ｄｕａｌｉｔｙ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，２００８，５４（３）：１２４１—１２５１．　［２７］ＢＡＹＡＴＩ　Ｍ，ＧＥＲＲＩＴＳＥＮ　Ｍ，ＧＬＥＩＣＨ　Ｄ　Ｆ，ｅｔ　ａ１．Ａｌｇｏ—　ｒｉｔｈｍｓ　ｆｏｒ　ｌａｒｇｅ，ｓｐａｒｓｅ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍｓ［Ｃ］／／　０９　Ｎｉｎｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｄａｔａ　Ｍｉｎｉｎｇ，２００９：７０５—７１０．　［２８］ＰＥＡＲＬ　Ｊ．Ｒｅｖｅｒｅｎｄ　Ｂａｙｅｓ　ｏｎ　ｉｎｆｅｒｅｎｃｅ　ｅｎｇｉｎｅｓ：ａ　ｄｉｓｔｒｉｂ—　ｕｔｅｄ　ｈｉｅｒａｒｃｈｉｃａｌ　ａｐｐｒｏａｃｈ［Ｃ］／／ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＡＡＡＩ．　１９８２：１３３—１３６．　［２９］ＳＡＮＧＨＡＶＩ　Ｓ，ＭＡＬＩＯＵＴＯＶ　Ｄ　Ｍ，ＷＩＬＬＳＫＹ　Ａ　Ｓ．Ｌｉｎｅａｒ　ｐｒｏｇｒａｍｍｉｎｇ　ａｎａｌｙｓｉｓ　ｏｆ　ｌｏｏｐｙ　ｂｅｌｉｅｆ　ｐｒｏｐａｇａｔｉｏｎ　ｆｏｒ　ｗｅｉｇｈ—　ｔｅｄ　ｍａｔｃｈｉｎｇ［Ｃ］／／ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＮＩＰＳ，２００７：．　［３０］ＤＡＧＵＭ　Ｌ，ＭＥＮＯＮ　Ｒ．ＯｐｅｎＭＰ：ａｎ　ｉｎｄｕｓｔｙｒ　ｓｔａｎｄａｒｄ　ＡＰＩ　ｆｏｒ　ｓｈａｒｅｄ—ｍｅｍｏｒｙ　ｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓａｃ—　ｔｉｏｎｓ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，１９９８，５　（１）：４６—５５．　［３１］ＪＵＮＧ　Ｊ，ＭＯＲＩ　Ｔ，ＳＵＧＩＴＡ　Ｙ．Ｍｉｄｐｏｉｎｔ　ｃｅｌｌ　ｍｅｔｈｏｄ　ｆｏｒ　ｈｙｂｒｉｄ（ＭＰＩ＋ＯｐｅｎＭＰ）ｐａｒａｌｌｅｌｉｚａｔｉｏｎ　ｏｆ　ｍｏｌｅｃｕｌａｒ　ｄｙ—　ｎａｍｉｃｓ　ｓｉｍｕｌａｔｉｏｎｓ『Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｈｅｍｉｓ—　ｔｒｙ，２０１４：１０６４—１０７２．　『３２］ＴＨＯＭＡＮ　Ｐ，ＪＯＲＤＡＮ　Ｈ，ＰＥＬＬＥＧＲＩＮＩ　Ｓ，ｅｔ　ａ１．Ａｕｔｏ—　ｍａｔｉｅ　ＯｐｅｎＭＰ　ｌｏｏｐ　ｓｃｈｅｄｕｌｉｎｇ：ａ　ｃｏｍｂｉｎｅｄ　ｃｏｍｐｉｌｅｒ　ａｎｄ　ｒｕｎｔｉｍｅ　ａｐｐｒｏａｃｈ［Ｍ］．Ｓｐｒｉｎｇｅｒ，２０１２：８８—１０１．　［３３］ＧＯＵＶＥＩＡ　Ａ，ＳＩＬＶＡ　Ｎ，ＲＯＣＨＡ　Ｊ，ｅｔ　１ａ．Ｉｔｅｒａｔｉｖｅ　ｏｎｔｏｌ—　ｏｇｙ　ａｌｉｇｎｍｅｎｔ　ｄｅｂｕｇｇｉｎｇ　ｕｓｉｎｇ　ａ　ｓｃｅｎａｒｉｏ－－ａｎｄ　ｓｔｒａｔｅｇｙ・－ｄｒｉｖ・－　ｅｎ　ａｐｐｒｏａｃｈ［Ｃ］／／Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｄａｔａｂａｓｅ　ａｎｄ　Ｅｘｐｅ￣Ｓｙｓｔｅｍｓ　Ａｐｐｌｉｃａｔｉｏｎｓ　（ＤＥＸＡ），２０１２＼：２５４—２５８．　［３４］ＰＡＧＥ　Ｌ，ＢＲＩＮ　Ｓ，ＭＯＴＷＡＮＩ　Ｒ，ｅｔ　ａ１．Ｔｈｅ　ＰａｇｅＲａｎｋ　ｃｉ—　ｔａｔｉｏｎ　ｒａｎｋｉｎｇ：ｂｒｉｎｇｉｎｇ　ｏｒｄｅｒ　ｔｏ　ｔｈｅ　ｗｅｂ［Ｊ］．１９９９：１０２—　１０９．　［３５］ＬＩＡＯ　Ｃ—Ｓ，ＬＵ　Ｋ，ＢＡＹＭ　Ｍ，ｅｔ　ａ１．ＩｓｏＲａｎｋＮ：ｓｐｅｃｔｒａｌ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｇｌｏｂａｌ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｍｕｌｔｉｐｌｅ　ｐｒｏｔｅｉｎ　ｎｅｔｗｏｒｋｓ　［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２００９，２５（１２）：ｉ２５３一ｉ２５８．　［３６］ＡＮＤＥＲＳＥＮ　Ｒ，ＣＨＵＮＧ　Ｆ，ＬＡＮＧ　Ｋ．Ｌｏｃａｌ　ｇｒａｐｈ　ｐａｒｔｉ—　ｔｉｏｎｉｎｇ　ｕｓｉｎｇ　ｐａｇｅｒａｎｋ　ｖｅｃｔｏｒｓ［Ｃ］／／４７ｔｈ　Ａｎｎｕａｌ　ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２００６　２００６：．　［３７］ＡＬＡＤＡＧ　Ａ　Ｅ，ＥＲＴＥＮ　Ｃ．ＳＰＩＮＡＬ：ｓｅａｌａｂｌｅ　ｐｒｏｔｅｉｎ　ｉｎ—　ｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２０１３，２９　（７）：９１７—９２４．　［３８］ＫＥＬＬＥＹ　Ｂ　Ｐ，ＹＵＡＮ　Ｂ，ＬＥＷＩＴＦＥＲ　Ｆ，ｅｔ　ａ１．Ｐａｔｈ—　ＢＬＡＳＴ：ａ　ｔｏｏｌ　ｆｏｒ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔ—　ｗｏｒｋｓ［Ｊ］．Ｎｕｃｌｅｉｃ　ａｃｉｄｓ　ｒｅｓｅａｒｃｈ，２００４，３２（ｓｕｐｐｌ　２）：　Ｗ８３一Ｗ８８．　［３９］ＳＨＡＲＡＮ　Ｒ，ＳＵＴＨＲＡＭ　Ｓ，ＫＥＬＬＥＹ　Ｒ　Ｍ，ｅｔ　ａ１．Ｃｏｎ—　ｓｅｒｖｅｄ　ｐａｔｔｅｒｕｓ　ｏｆ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｉｎ　ｍｕｌｔｉｐｌｅ　ｓｐｅｃｉｅｓ　［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ　ｏｆ　ｔｈｅ　Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ　ｏｆ　Ａｍｅｒｉｃａ，２００５，１０２（６）：１９７４—１９７９．　［４０］ＫＯＹＵＴ　ＲＫ　Ｍ，ＫＩＭ　Ｙ，ＴＯＰＫＡＲＡ　Ｕ，ｅｔ　ａ１．Ｐａｉｒｗｉｓｅ　ａ—　ｌｉｇｎｍｅｎｔ　ｏｆ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｂｉｏｌｏｇｙ，２００６．１３（２）：１８２—１９９．　［４１］ＦＬＡＮＮＩＣＫ　Ｊ，ＮＯＶＡＫ　Ａ，ＳＲＩＮＩＶＡＳＡＮ　Ｂ　Ｓ，ｅｔ　ａ１．　Ｇｒａｅｍｌｉｎ：ｇｅｎｅｒａｌ　ａｎｄ　ｒｏｂｕｓｔ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｍｕｌｔｉｐｌｅ　ｌａｒｇｅ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ『Ｊ］．Ｇｅｎｏｍｅ　Ｒｅｓｅａｒｃｈ，２００６，１６　（９）：１１６９．１１８１．　［４２］ＦＬＡＮＮＩＣＫ　Ｊ，ＮＯＶＡＫ　Ａ，ＤＯ　Ｃ　Ｂ，ｅｔ　ａ１．Ａｕｔｏｍａｔｉｃ　ｐａ—　ｒａｍｅｔｅｒ　ｌｅａｒｎｉｎｇ　ｏｆｒ　ｍｕｌｔｉｐｌｅ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ［Ｃ］／／Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｒｅｓｅａｒｃｈ　ｉｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｍｏｌｅｃｕｌａｒ　Ｂｉｏｌｏ—　ｇｙ，Ｆ，２００８：２１４—２３１．　［４３］ＷＡＮＧ　Ｂ，ＧＡＯ　Ｌ．Ｓｅｅｄ　ｓｅｌｅｃｔｉｏｎ　ｓｔｒａｔｅｇｙ　ｉｎ　ｇｌｏｂａｌ　ｎｅｔ—　ｗｏｒｋ　ａｌｉｇｎｍｅｎｔ　ｗｉｔｈｏｕｔ　ｄｅｓｔｒｏｙｉｎｇ　ｔｈｅ　ｅｎｔｉｒｅ　ｓｔｕｒｃｔｕｒｅｓ　ｏｆ　ｆｕｎｃｔｉｏｎａｌ　ｍｏｄｕｌｅｓ［Ｊ］．Ｐｒｏｔｅｏｍｅ　ｓｃｉｅｎｃｅ，２０１２，１０（Ｓｕｐ—　ｐｌ　１）：Ｓ１６．　『４４］ＫＯＶ　ＣＳ　Ｉ　Ａ，ＰＡＬＯＴＡＩ　Ｒ，ＳＺＡＬＡＹ　Ｍ　Ｓ，ｅｔ　ａ１．Ｃｏｍｍｕ—　ｎｉｔｙ　ｌａｎｄｓｃａｐｅｓ：ａｎ　ｉｎｔｅｇｒａｔｉｖｅ　ａｐｐｒｏａｃｈ　ｔｏ　ｄｅｔｅｒｍｉｎｅ　ｏｖｅｒ—　ｌａｐｐｉｎｇ　ｎｅｔｗｏｒｋ　ｍｏｄｕｌｅ　ｈｉｅｒａｒｃｈｙ，ｉｄｅｎｔｉｆｙ　ｋｅｙ　ｎｏｄｅｓ　ａｎｄ　ｐｒｅｄｉｃｔ　ｎｅｔｗｏｒｋ　ｄｙｎａｍｉｃｓ［Ｊ］．ＰｌｏＳ　ｏｎｅ，２０１０，５（９）：　ｅ１２５２８．　［４５］ＭＩＬＥＮＫＯＶＩＣ　Ｔ，ＡＤＶＩＳＥＲ—ＰＲＺＵＬＪ　Ｎ．Ｆｒｏｍ　ｔｏｐｏｌｏｇｉｃａｌ　ｎｅｔｗｏｒｋ　ａｎａｌｙｓｅｓ　ａｎｄ　ａｌｉｇｎｍｅｎｔｓ　ｔｏ　ｂｉｏｌｏｇｉｃａｌ　ｆｕｎｃｔｉｏｎ，　ｄｉｓｅａｓｅ，ａｎｄ　ｅｖｏｌｕｔｉｏｎ『Ｍ］．Ｃａｌｉｆｏｒｎｉａ　Ｓｔａｔｅ　Ｕｎｉｖｅｒｓｉｔｙ　ａｔ　Ｌｏｎｇ　Ｂｅａｃｈ，２０１０　［４６］ＡＴＬＡＳ　Ｎ，ＳＨＡＲＡＮ　Ｒ．Ｃｏｍｐａｒａｔｉｖｅ　ａｎａｌｙｓｉｓ　ｏｆ　ｐｒｏｔｅｉｎ　ｎｅｔｗｏｒｋｓ：ｈａｒｄ　ｐｒｏｂｌｅｍｓ，ｐｒａｃｔｉｃａｌ　ｓｏｌｕｔｉｏｎｓ［Ｊ］．Ｃｏｍｍｕ—　ｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，２０１２，５５（５）：８８—９７．　第４期　刘富，等：复杂网络结构比对算法研究进展　・５１７・　［４７］ＭＩＬＥＮＫＯＶＩ　Ｃ　Ｔ，ＰＲＺＵＬＪ　Ｎ．Ｕｎｃｏｖｅｒｉｎｇ　ｂｉｏｌｏｇｉｃａｌ　ｎｅｔ—　ｗｏｒｋ　ｆｕｎｃｔｉｏｎ　ｖｉａ　ｇｒａｐｈｌｅｔ　ｄｅｇｒｅｅ　ｓｉｇｎａｔｕｒｅｓ［Ｊ］．Ｃａｎｃｅｒ　ｉｎｆｏｒｍａｔｉｃｓ，２００８，（６）：５６—６５．　『４８］ＭＩＬＬＳ—ＴＥ　ＩＹＩ１ＥＹ　Ｇ　Ａ．ＳＴＥＮＴＺ　Ａ，ＤＩＡＳ　Ｍ　Ｂ．Ｔｈｅ　ｄｙ—　ｎａｍｉｃ　ｈｕｎｇａｒｉａｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　ｃｈａｎｇｉｎｇ　ｃｏｓｔｓ［Ｊ］．２００７：１—１９．　［４９］ＷＥＳＴ　Ｄ　Ｂ．Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｇｒａｐｈ　ｔｈｅｏｒｙ［Ｍ］．Ｐｒｅｎｔｉｃｅ　ｈａｌｌ　Ｕｐｐｅｒ　Ｓａｄｄｌｅ　Ｒｉｖｅｒ，２００１：１７８—１８５．　［５０］ＭＥＭＩ￣ＥＶＩＣ　Ｖ，ＰＲＺＵＬＪ　Ｎ．Ｃ—ＧＲＡＡＬ：Ｃｏｍｍｏｎ—ｎｅｉｇｈ—　ｂｏｒｓ—ｂａｓｅｄ　ｇｌｏｂａｌ　ＧＲＡｐｈ　ＡＬｉｇｎｍｅｎｔ　ｏｆ　ｂｉｏｌｏｇｉｃａｌ　ｎｅｔｗｏｒｋｓ　［Ｊ］．Ｉｎｔｅｇｒａｔｉｖｅ　Ｂｉｏｌｏｇｙ，２０１２，４（７）：７３４—７４３．　［５　１］ＤＵＡＮ　Ｒ，ＰＥ　ｒｒＩＥ　Ｓ．Ｌｉｎｅａｒ—Ｔｉｍｅ　Ａｐｐｒｏｘｉｍａｔｉｏｎ　ｏｆｒ　Ｍａｘ—　ｉｍｕｍ　Ｗｅｉｇｈｔ　Ｍａｔｃｈｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　ＡｃＭ（ＪＡＣＭ），　２０１４，６１（１）：１．　［５２］ＫＯＬＬＩＡＳ　Ｇ，Ｍ０ＨＡＭＭＡＤＩ　Ｓ，ＧＲＡＭＡ　Ａ．Ｎｅｔｗｏｒｋ　Ｓｉｍ—　ｉｌａｒｉｔｙ　Ｄｅｃｏｍｐｏｓｉｔｉｏｎ（ＮＳＤ）：Ａ　ｆａｓｔ　ａｎｄ　ｓｃａｌａｂｌｅ　ａｐ—　ｐｒｏａｃｈ　ｔｏ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎ—　ｇｉｎｅｅｒｉｎｇ，ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ，２０１２，２４（１２）：２２３２—　２２４３．　［５３］ＨＵＡＮＧ　Ｑ，ｗｕ　Ｌ—Ｙ，ＺＨＡＮＧ　Ｘ—Ｓ．Ｃｏｒｂｉ：Ａ　ｎｅｗ　Ｒ　ｐａｃｋａｇｅ　ｆｏｒ　ｂｉｏｌｏｇｉｃａｌ　ｎｅｔｗｏｒｋ　ａｌｉｇｎｍｅｎｔ　ａｎｄ　ｑｕｅｒｙｉｎｇ［Ｊ］．　ＢＭＣ　Ｓｙｓｔｅｍｓ　Ｂｉｏｌｏｇｙ，２０１３，７（２）：１－９．　［５４］ＰＩＪＰＥＲＳ　Ｖ，ＤＥ　ＬＥＥＮＨＥＥＲ　Ｐ，ＧＯＲＤＩＪＮ　Ｊ，ｅｔ　１ａ．Ｕｓｉｎｇ　ｃｏｎｃｅｐｔｕａｌ　ｍｏｄｅｌｓ　ｔｏ　ｅｘｐｌｏｒｅ　ｂｕｓｉｎｅｓｓ—ＩＣＴ　ａｌｉｇｎｍｅｎｔ　ｉｎ　ｎｅｔｗｏｒｋｅｄ　ｖａｌｕｅ　ｃｏｎｓｔｅｌｌａｔｉｏｎｓ［Ｊ］．Ｒｅｑｕｉｒｅｍｅｎｔｓ　Ｅｎｇｉ—　ｎｅｅｒｉｎｇ，２０１２，１７（３）：２０３—２２６．　［５５］ＫＥＡＲＮＳ　Ｍ，ＳＩＮＧＨ　Ｓ．Ｎｅａｒ—ｏｐｔｉｍａｌ　ｒｅｉｎｆｏｒｃｅｍｅｎｔ　ｌｅａｒｎ—　ｉｎｇ　ｉｎ　ｐｏｌｙｎｏｍｉｌａ　ｔｉｍｅ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，２００２，４９　（２—３）：２０９—２３２．　［５６］ＬＩＵ　Ｇ，ＬＩ　Ｊ，ＷＯＮＧ　Ｌ．Ａｓｓｅｓｓｉｎｇ　ａｎｄ　ｐｒｅｄｉｃｔｉｎｇ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎｓ　ｕｓｉｎｇ　ｂｏｔｈ　ｌｏｃａｌ　ａｎｄ　ｇｌｏｂａｌ　ｎｅｔｗｏｒｋ　ｔｏｐｏｌｏｇｉｃａｌ　ｍｅｔｒｉｃｓ】Ｊ　１．Ｇｅｎｏｍｅ　Ｉｎｆｏｒｍａｔｉｃｓ，２００８，２２　１３８—１４９．　［５７］ＫＵＣＨＡＩＥＶ　Ｏ，ＲＡ￣ＡＪＳＫＩ　Ｍ，ＨＩＧＨＡＭ　Ｄ　Ｊ，ｅｔ　ａ１．Ｇｅｏ—　ｍｅｔｒｉｃ　ｄｅ・－ｎｏｉｓｉｎｇ　ｏｆ　ｐｒｏｔｅｉｎ－－ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　［Ｊ］．ＰＬｏＳ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｂｉｏｌｏｇｙ，２００９，５（８）：　ｅ１０００４５４．　［５８］ＣＨＵＡ　Ｈ　Ｎ，ＳＵＮＧ　Ｗ—Ｋ，ＷＯＮＧ　Ｌ．Ｅｘｐｌｏｉｔｉｎｇ　ｉｎｄｉｒｅｃｔ　ｎｅｉｇｈｂｏｕｒｓ　ａｎｄ　ｔｏｐｏｌｏｇｉｃａｌ　ｗｅｉｇｈｔ　ｔｏ　ｐｒｅｄｉｃｔ　ｐｒｏｔｅｉｎ　ｆｕｎｃ—　ｔｉｏｎ　ｆｒｏｍ　ｐｒｏｔｅｉｎ—ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎｓ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔ—　ｉｃｓ，２００６，２２（１３）：１６２３—１６３０．　［５９］ＮＡＢＩＥＶＡ　Ｅ，ＪＩＭ　Ｋ，ＡＧＡＲＷＡＬ　Ａ，ｅｔ　ａ１．Ｗｈｏｌｅ—ｐｒｏ—　ｔｅｏｍｅ　ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｐｒｏｔｅｉｎ　ｆｕｎｃｔｉｏｎ　ｖｉａ　ｇｒａｐｈ・－ｔｈｅｏｒｅｔｉｃ　ａ－－　ｎａｌｙｓｉｓ　ｏｆ　ｉｎｔｅｒａｃｔｉｏｎ　ｍａｐｓ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００５，２１　（ｓｕｐｐｌ　１）：ｉ３０２一ｉ３１０．　［６０］ＡＬＩ　Ｗ，ＤＥＡＮＥ　Ｃ　Ｍ．Ｆｕｎｃｔｉｏｎａｌｌｙ　ｇｕｉｄｅｄ　ａｌｉｇｎｍｅｎｔ　ｏｆ　ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｍｏｄｕｌｅ　ｄｅｔｅｃｔｉｏｎ　Ｉ　Ｊ】．　Ｂｉｏｉｎｆｏｒｍａｔｉｅｓ，２００９，２５（２３）：３１６６—３１７３．　［６１］ＣＬＡＵＳＥＴ　Ａ，ＭＯＯＲＥ　Ｃ，ＮＥｗＭＡＮ　Ｍ　Ｅ．Ｈｉｅｒａｒｃｈｉｃａｌ　ｓｔｒｕｃｔｕｒｅ　ａｎｄ　ｔｈｅ　ｐｒｅｄｉｃｔｉｏｎ　ｏｆ　ｍｉｓｓｉｎｇ　ｌｉｎｋｓ　ｉｎ　ｎｅｔｗｏｒｋｓ　［Ｊ］．Ｎａｔｕｒｅ，２００８，４５３（７１９１）：９８—１０１．　［６２］ＰＲ￣ＵＬＪ　Ｎ．Ｂｉｏｌｏｇｉｃａｌ　ｎｅｔｗｏｒｋ　ｃｏｍｐａｒｉｓｏｎ　ｕｓｉｎｇ　ｇｒａｐｈｌｅｔ　ｄｅｇｒｅｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００７，２３（２）：　ｅ】７７一ｅ】８３．　［６３］ＺＨＵ　Ｌ，ＹＯＵ　Ｚ—Ｈ，ＨＵＡＮＧ　Ｄ—Ｓ．Ｉｎｃｒｅａｓｉｎｇ　ｔｈｅ　ｒｅｌｉａｂｉｌｉｔｙ　ｏｆ　ｐｒｏｔｅｉｎ—ｐｒｏｔｅｉｎ　ｉｎｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｖｉａ　ｎｏｎ－ｃｏｎｖｅｘ　ｓｅｍａｎｔｉｃ　ｅｍｂｅｄｄｉｎｇ［Ｊ］．Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ，２０１３，ｖ１２１，　ｐ９９—１０７．　［６４］ＴＥＲＲＡＤＯＴ　Ｌ，ＤＵＲＮＥＬＬ　Ｎ，ＬＩ　Ｍ，ｅｔ　ａ１．Ｂｉｏｃｈｅｍｉｃａｌ　Ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ｏｆ　Ｐｒｏｔｅｉｎ　Ｃｏｍｐｌｅｘｅｓ　ｆｒｏｍ　ｔｈｅ　Ｈｅｌｉｃｏｂａｃｔ—　ｅｒ　ｐｙｌｏｒｉ　Ｐｒｏｔｅｉｎ　Ｉｎｔｅｒａｃｔｉｏｎ　Ｍａｐ　Ｓｔｒａｔｅｇｉｅｓ　ｆｏｒ　Ｃｏｍｐｌｅｘ　Ｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｅｖｉｄｅｎｃｅ　ｆｏｒ　Ｎｏｖｅｌ　Ｉｎｔｅｒａｃｔｉｏｎｓ　Ｗｉｔｈｉｎ　Ｔｙｐｅ　ＩＶ　Ｓｅｃｒｅｔｉｏｎ　Ｓｙｓｔｅｍｓ　Ｉ　Ｊ　１．Ｍｏｌｅｃｕｌａｒ＆Ｃｅｌｌｕｌａｒ　Ｐｒｏ—　ｔｃｏｍｉｃｓ，２００４，３（８）：８０９－８１９．　Ｉ　６５　ＳＵＮ　Ｐ　Ｇ，ＧＡ０　Ｌ．ＳＨＡＮ　ＨＡＮ　Ｓ．Ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ｏｆ　ｏｖｅｒ—　ｌａｐｐｉｎｇ　ａｎｄ　ｎｏｎ—ｏｖｅｒｌａｐｐｉｎｇ　ｃｏｍｍｕｎｉｔｙ　ｓｔｒｕｃｔｕｒｅ　ｂｙ　ｆｕｚｚｙ　ｃｌｕｓｔｅｒｉｎｇ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，　２０１１，１８１（６）：１０６０—１０７１．　［６６］ＨＡＶＥＭＡＮＮ　Ｆ，ＧＬ　ＳＥＲ　Ｊ，ＨＥＩＮＺ　Ｍ，ｅｔ　ａ１．Ｉｄｅｎｔｉｆｙｉｎｇ　ｏｖｅｒｌａｐｐｉｎｇ　ａｎｄ　ｈｉｅｒａｒｃｈｉｃａｌ　ｔｈｅｍａｔｉｃ　ｓｔｒｕｃｔｕｒｅｓ　ｉｎ　ｎｅｔ—　ｗｏｒｋｓ　ｏｆ　ｓｃｈｏｌａｒｌｙ　ｐａｐｅｒｓ：Ａ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｔｈｒｅｅ　ａｐｐｒｏａ—　ｃｈｅｓ［Ｊ］．ＰｌｏＳ　ｏｎｅ，２０１２，７（３）：ｅ３３２５５．　［６７］ＬＥＥ　Ｃ，ＲＥＩＤ　Ｆ，ＭＣＤＡＩＤ　Ａ，ｅｔ　ａ１．Ｓｅｅｄｉｎｇ　ｆｏｒ　ｐｅｒｖａ—　ｓｉｖｅｌｙ　ｏｖｅｒｌａｐｐｉｎｇ　ｃｏｍｍｕｎｉｔｉｅｓ［Ｊ］．Ｐｈｙｓｉｃａｌ　Ｒｅｖｉｅｗ　Ｅ，　２０１１，８３（６）．　［６８］ＤＥＮＴ　Ｊ　Ｅ，ＹＡＮＧ　Ｘ，ＮＡＲＤＩＮＩ　Ｃ．ＳＰＮＣｏｎｖｅｒｔｅｒ：ａ　ｎｅｗ　ｌｉｎｋ　ｂｅｔｗｅｅｎ　ｓｔａｔｉｃ　ａｎｄ　ｄｙｎａｍｉｃ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋ　ａｎａｌｙｓｉｓ　［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２０１３，２９（１９）：２５０７—２５０８．　［６９］ＷＡＮＧ　Ｊ，ＰＥＮＧ　Ｘ，ＰＥＮＧ　Ｗ，ｅｔ　ａ１．Ｄｙｎａｍｉｃ　ｐｒｏｔｅｉｎ　ｉｎ—　ｔｅｒａｃｔｉｏｎ　ｎｅｔｗｏｒｋ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｎｄ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｊ］．Ｐｒｏ—　ｔｅｏｍｉｃｓ，２０１４，１４（４—５）：３３８—３５２．　［７０］ＶＡＮ　ＤＥＮ　ＨＯＦ　Ｐ　Ｍ，ＤＡＮＫＥＲＳ　Ａ，ＨＥＵＢＥＲＧＥＲ　Ｐ　Ｓ，　ｅｔ　ａ１．Ｉｄｅｎｔｉｉｆｃａｔｉｏｎ　ｏｆ　ｄｙｎａｍｉｃ　ｍｏｄｅｌｓ　ｉｎ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈ　ｐｒｅｄｉｃｔｉｏｎ　ｅｒｒｏｒ　ｍｅｔｈｏｄｓ－－Ｂａｓｉｃ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｃｏｎｓｉｓｔ—　ｅｎｔ　ｍｏｄｕｌｅ　ｅｓｔｉｍａｔｅｓ［Ｊ］．Ａｕｔｏｍａｔｉｃａ，２０１３，４９（１０）：　２９９４—３００６．　［７１］ＭＡ　ＡＹＡＮ　Ａ．Ｉｎｓｉｇｈｔｓ　ｉｎｔｏ　ｔｈｅ　ｏｒｇａｎｉｚａｔｉｏｎ　ｏｆ　ｂｉｏｃｈｅｍｉｃａｌ　ｒｅｇｕｌａｔｏｒｙ　ｎｅｔｗｏｒｋｓ　ｕｓｉｎｇ　ｇｒａｐｈ　ｔｈｅｏｒｙ　ａｎａｌｙｓｅｓ［Ｊ］．Ｊｏｕｒ－　ｎａｌ　ｏｆ　ｂｉｏｌｏｇｉｃａｌ　ｃｈｅｍｉｓｔｙｒ，２００９，２８４（９）：５４５１—５４５５．　［７２］　作者简介：　刘富，男，１９６８年生，博士生导师，　博士，博士，主要研究方向为模式识别　与智能系统。参与国家博士后科学基　金项目，国家８６３计划项目，国家自然　科学基金项目，国家信息产业部项目，　吉林省科技发展重大项目以及某部委　预研基金项目等。发表论文２０多篇。　姜奕含，女，１９９０年生，硕士研究　生，主要研究方向为模式识别中的网络　的比对分析研究。　［责任编辑：马兰兰］