用于成对PPI网络比对的分治与整合算法

生物网络比对是分析不同生物间进化关系的重要手段,它可以揭示不同物种间的保守功能并为物种间的注释转移提供重要信息。网络比对与子图同构类似,是一个NP-hard问题。本文提出了一种新的分治与整合策略的生物网络比对算法。首先进行模块划分,并根据已有的比对信息计算模块相似性;然后根据模块间结点的子比对获取候选结果集,最终通过超图匹配获得比对结果。使用已有的比对信息的集体行为预估模块间的相似性,大大提高了模块匹配的效率。基于路径和结点的得分函数保证了模块内结点的相似性。对于不同网络间结点的相似性,分别从结点自身和结点间的差异进行相似性判断。与现有算法相比,本文算法在生物和拓扑指标上均表现最佳。     

一种基于遗传算法的PPI网络全局比对算法

蛋白质相互作用网络比对在识别同源蛋白质或者蛋白质功能模块、蛋白质功能预测等方面具有十分重要的生物学意义.通常从拓扑特性和生物特性两个方面来衡量网络比对的结果，而现有的网络比对算法很难同时取得好的拓扑特性和生物特性.基于此，本文提出一种新的网络比对算法NABG.NABG利用最小度启发式算法计算节点在网络中的重要性，并基于重要性得分计算节点对的拓扑相似性，引入节点对的序列相似信息，使拓扑和生物相似性高的蛋白质对被比对上；基于结合了节点相似性和边保守性的目标函数，使用遗传算法模拟生物进化过程来优化比对结果.NABG分别在合成网络和真实网络上进行了实验，并与MGANA++、PROPER、SPINAL等算法作比较分析.实验结果表明，NABG的比对结果在拓扑指标以及生物指标上能保持均衡的高指标且更具有生物学意义.     

基于随机游走与最优匹配的装配体相似性分析

为了提高利用拓扑信息进行装配体检索的能力,提出一种基于随机游走和最优匹配的相似性分析方法.首先用图节点表示装配体中的零件,将装配体转化为属性连接图并进行简化;然后分析零件连接装配关系的紧密程度并构建转移概率矩阵,利用随机游走模型分析各零件的拓扑特征;最后依据拓扑和属性特征进行零件的两两相似性评价,建立对比装配体的二分图并用最优匹配获得装配体的整体相似性.实例验证了文中方法是正确和有效的.     

基于区域分割的三维自由曲面相似性评价算法

为了在工程应用中检索已有的三维CAD模型,以便重用相应零件的设计信息,节省设计和加工成本,提出一种基于曲面分割技术的CAD自由曲面相似性评价算法.依据曲面的曲率将自由曲面分割成具有相对固定曲率特征的不同区域;对每个分割得到的区域用一个7维向量表达其形状的几何特征和拓扑特征,一个自由曲面形状特征即可通过各分割区域所对应的7维向量组成的向量组表达;将该向量组作为自由曲面的形状描述子,2个自由曲面的相似性可通过相对应的形状描述子间的相似性表达.在评价2个曲面形状描述子的相似性时,将描述子中的每个向量看成是一个带有属性的节点,2个形状描述子所对应的2组属性节点可看成是一个二分图,2组属性节点间相应节点距离看成是二分图的权值,并利用赋权二分图最优匹配的算法求出2组属性节点的相似性,实现2个自由曲面之间的相似性评价.实验结果表明,该算法是有效、可行的.     

基于局部优化与二分图匹配的PPI网络比对算法

生物蛋白质相互作用网络,简称PPI网络,是一种生物信息学中用来表示蛋白质之间相互作用关系的图模型。不同物种PPI网络之间的比对,有着重要的生物学意义,一个好的PPI网络比对算法,显得尤为重要。针对该问题,首次提出了LOBM(Local Optimization based on Bipartite graph Matching)算法。LOBM是一种能够局部优化既有比对结果,并且利用二分图匹配这一经典图论模型,来提高既有比对算法的比对效果。实验表明,LOBM相比一些现有的比对算法,在比对结果上有较大的提升。     

基于距离度量的多样性图排序方法

有效结合查询相关性和多样性的扩展相关性是多样性图排序问题的一种优化目标.基于扩展相关性的多样性图排序可建模为一个子模函数优化问题,贪心子模优化算法可近似求解该问题.然而,扩展相关性不能直接度量节点间的不相似性.子模优化算法是串行算法不能充分利用诸如Spark等集群计算平台有效提高算法效率.针对这些问题,本文提出一种描述节点间不相似性的距离度量.基于此距离度量,将多样性图排序问题建模为一个在查询相关节点集上构造的带权完全图的最大和k-dispersion优化问题.提出了求解该问题的多项式时间2-近似算法.鉴于不同节点对的距离度量计算是相互独立的,进一步地提出了基于MapReduce编程模型的并行化多样性图排序算法.最后,在真实图数据集上验证了本文提出算法的高效性和有效性.     

本体结构特征分析与匹配应用研究

针对本体匹配中结构蕴含的隐式语义信息难以正确表示和充分使用问题,提出将本体结构特征量化引入本体匹配。根据本体与复杂网络的相似性,分析本体具有的网络特征,提出了一系列基于结构和语义特征的理论和节点、边的量化标准,并将其用于核心节点的选取和边权重的度量。将本体匹配转换为基于元素个体特征和整体组织结构的有权标签图匹配问题,通过二次规划方法求取近似最优匹配。实验证明本体拓扑结构特征对本体匹配具有较大影响,其与核心节点匹配的紧密藕合能够显著提高匹配的准确性。     

基于蜂窝结构的改进混合无线传感器网络覆盖优化算法

基于蜂窝结构的混合无线传感器网络（HWSN）覆盖优化算法HWSNBCS存在移动节点平均移动距离较大的问题,为此,提出一种改进的HWSN覆盖优化算法IHWSNBCS。寻找移动传感器节点初始位置与通过HWSNBCS算法得出的候选目标位置之间的最优匹配,将移动节点移动距离之和最小化问题转化为二分图最优匹配问题,利用带权二分图匹配算法KM寻找该匹配问题的最优解,从而得到移动节点最终的目标位置,并实现对HWSNBCS算法移动节点平均移动距离的进一步优化。实验结果表明,IHWSNBCS算法在取得与HWSNBCS算法相同网络覆盖率的前提下,移动节点的平均移动距离减少幅度达到38.87%～43.28%,单个移动节点的最大移动距离减少幅度达到22.65%～66.58%,降低了系统因重新部署移动传感器节点所产生的能耗以及单个传感器节点因能量耗尽而失效的概率,从而延长了网络生命周期,同时,IHWSNBCS的ΔCov-Dist性能指标为HWSNBCS算法的1.64～1.76倍,表明移动节点移动相同距离时IHWSNBCS算法的网络覆盖率提升更大。     

节点层次化的二进制文件比对技术

当前二进制文件比对技术主流是以BinDiff为代表的结构化比对方法,存在结构相似导致的误匹配、分析耗时较高的问题。针对该问题提出一种基于节点层次化、价值化的匹配方法。通过提取函数节点在函数调用图中的层次与函数在调用网络中的价值,对层次模糊的节点提供了节点层次估算算法,最后递归匹配节点。实验表明,该方法避免了结构相似导致的误匹配,其时耗低于结构化比对工具Bindiff的1/2,节点匹配数量减少在15%以内。该方法可有效提高嵌入式设备固件的跨版本相似性分析效率。     

基于模块度函数的加权蛋白质复合物识别算法

针对加权模块度函数聚类算法在蛋白质相互作用网络中进行复合物识别的准确率不高、召回率较低以及时间性能不佳等问题进行了研究,提出一种基于模块度函数的加权蛋白质复合物识别算法IWPC-MF（Algorithm for Identifying Weighted Protein Complexes based on Modularity Function）。融合点聚集系数改进边聚集系数,将改进后的边点聚集系数与基因共表达的皮尔逊相关系数结合来构建加权蛋白质网络;基于节点权重选取种子节点,遍历种子的邻居节点,设计节点间的相似度度量和蛋白质附着度来获取初始聚类模块;设计基于紧密度的蛋白质复合物模块度函数来合并初始模块,并最终完成复合物的识别,克服传统的模块度函数无法识别出重叠和规模较小的复合物的缺陷。将IWPC-MF算法应用在DIP数据上进行复合物的识别,实验结果表明IWPC-MF算法的准确率和召回率较高,能够较准确地识别蛋白质复合物。     

基于加权投影的二分网络的链路预测

二分网络上的链路预测是复杂网络中的重要研究内容。充分利用拓扑结构,提出一种基于双向投影的二分网络上的链路预测算法。它能同时投影二分网络上的两类节点,分别生成基于顶部节点的投影图和基于底部节点的投影图。通过基于资源分配的加权方法得到同类节点之间的资源权重比,利用相似度度量两类节点之间未链接边资源分配值进行比较,预测出链路边。在实验分析中通过利用AUC来分析算法的准确性和精度,得出该算法具有一定的优势。     

加权迭代节点匹配算法及其在语言网络中的应用

复杂网络间节点匹配在很多领域中均具有重要现实意义。然而,传统的节点匹配算法通常只利用网络的局部拓扑信息,在对拥有高对称性的真实网络作用时往往会失效。为了克服这一缺点,我们近期利用网络拓扑信息和连边权重信息,提出了一种新型的同时来计算不同网络间节点相似度的方法,并在此基础上设计了一种加权迭代节点匹配算法。将该算法在高度拓扑对称仿真网络对和真实中英文语言网络对上分别进行了测试,结果表明加权迭代节点匹配算法在此类网络上优于纯拓扑迭代节点匹配算法。     

3D Model Retrieval Using Bipartite Graph Matching Based on Attention

In this paper, we propose an attention-based bipartite graph 3D model retrieval algorithm, where many-to-many matching method, the weighted bipartite graph matching, is employed for comparison between two 3D models. Considering the panoramic views can donate the spatial and structural information, in this work, we use panoramic views to represent each 3D model. Attention mechanism is used to generate the weight of all views of each model. And then, we construct a weighted bipartite graph with the views of those models and the weight of each view. According to the bipartite graph, the matching result is used to measure the similarity between two 3D models. We experiment our method on ModelNet, NTU and ETH datasets, and the experimental results and comparison with other methods show the effectiveness of our method.

     

The discriminant elastic graph matching algorithm applied to frontal face verification

In this paper a generalized framework for face verification is proposed employing discriminant techniques in all phases of elastic graph matching. The proposed algorithm is called discriminant elastic graph matching (DEGM) algorithm. In the first step of the proposed method, DEGM, discriminant techniques at the node feature vectors are used for feature selection. In the sequel, the two local similarity values, i.e., the similarity measure for the projected node feature vector and the node deformation, are combined in a discriminant manner in order to form the new local similarity measure. Moreover, the new local similarity values at the nodes of the elastic graph are weighted by coefficients that are derived as well from discriminant analysis in order to form a total similarity measure between faces. The proposed method exploits the individuality of the human face and the discriminant information of elastic graph matching in order to improve the verification performance of elastic graph matching. We have applied the proposed scheme to a modified morphological elastic graph matching algorithm. All experiments have been conducted in the XM2VTS database resulting in very low error rates for the test sets.     

一种潜在文档相似模型

提出一种潜在文档相似模型（LDSM）,把每对文档看作一个二分图,把文档的潜在主题看作二分图的顶点,用主题问的加权相似度为相应边赋权值,并用二分图的最佳匹配表示文档的相似度。实验结果表明,LDSM的平均查准率和平均查全率都优于用TextTiling和二分图最佳匹配方法构建的文档相似模型。     

PPI网络比对用于植物乳杆菌的糖代谢研究

蛋白质-蛋白质相互作用网络（PPI网络）比对是预测蛋白质相互作用,分析不同物种之间功能差异的重要手段。为研究植物乳杆菌WCFS1和JDM1糖代谢功能模块差异,采用Evolutionary Graph Edit Distance Algorithm算法对两者的糖酵解、戊糖磷酸途径、柠檬酸循环三个模块PPI网络进行比对。实验表明,两者的三个模块边正确性分别达到93.6%、96%、100%,表明其拓扑结构极其相似,戊糖磷酸途径中,WCFS1存在蛋白质2-keto-3-deoxygluconate kinase（kdgK）,但JDM1中没有kdgK,却有其产物2-keto-3-deoxy-6-phospho-gluconate aldolase（JDM1_0578）。糖酵解模块中,推测蛋白质pyruvate dehydrogenase complex,E2 component（pdhC）与pyruvate kinase（pyk）具有相互作用。实验表明,PPI网络比对可以阐明两者糖代谢PPI网络的拓扑相似性及模块差异,预测蛋白质之间的相互作用。     

融合多元影响力节点识别指标MPR的链接预测

多元网络通常是指节点之间存在多种维度链接关系的图结构.多元网络链接预测算法在构建相似度指标时,多数仅考虑单一维度网络的拓扑结构属性,未挖掘不同维度子网络之间存在的关联,影响链接预测的效果.针对该问题,提出一种基于多元全局节点影响力识别指标MPR的多元网络链接预测算法.通过定义一个多维度节点影响力排序指标MPR,度量多元网络空间中影响力较大的节点,并把影响力排名函数转化为潜在节点对之间的相似度得分,从而应用到多元网络链接预测场景中.在2个真实多元网络数据集上的实验结果表明,该算法的预测效果优于PR、EDC、ANC等对比算法,且具有较好的稳定性.     

Fast parallel algorithms for graph similarity and matching

This paper addresses the problem of global graph alignment on supercomputer-class clusters. We define the alignment of two graphs, as a mapping of each vertex in the first graph to a unique vertex in the second graph so as to optimize a given similarity-based cost function.¹ Using a state of the art serial algorithm for the computation of vertex similarity scores called Network Similarity Decomposition (NSD), we derive corresponding parallel formulations. Coupling this parallel similarity algorithm with a parallel auction-based bipartite matching technique, we obtain a highly efficient and scalable graph matching pipeline. We validate the performance of our integrated approach on a large parallel platform and on diverse graph instances (including Protein Interaction, Wikipedia and Web networks). Experimental results demonstrate that our algorithms scale to large machine configurations (thousands of cores) and problem instances, enabling the alignment of networks of sizes two orders of magnitude larger than reported in the current literature.