基于遗传算法的二部图判定算法

应用遗传算法来判定二部图的具体过程是首先将无向图G的节点随机分配到两个不同社区中,然后用遗传算法进行进化操作,优化无向图G的模块化函数Q,当Q取最小值且无向图G的边只存在于两个社区之间,则无向图G为二部图.实例分析结果验证了算法的有效性.     

图的矩阵表示方法的双向推广

本用定义的方式对相邻矩阵的概念在平行边和自回路两个方向作了推广，最终建立了对称矩阵和无向图之间的一一对应关系。     

IE_K2：一种基于贝叶斯网络的高效基因调控网络构建方法

为获得正确的节点次序,提高K2算法的执行效率和精确度,提出一种构建基因调控网络的IE-K2算法.基于两个节点互信息构建无向图,通过引入联合信息熵来获得最佳的节点次序.在Alarm网络中的实验结果表明,其预测的准确率优于爬山算法和随机节点顺序的K2算法;将IE-K2算法用于构建酿酒酵母的基因调控网络,通过现有文献证明了调控关系的正确性,结果显示了该算法的有效性.     

基于相邻节点聚类的社团划分算法

社团结构是复杂网络中的拓扑属性之一,具有同一社团内的节点连接紧密而不同社团的节点连接疏松的性质.作者基于复杂网络中的社团结构的性质并根据网络中相邻节点的距离关系,提出了一种社团划分算法--基于相邻节点聚类的社团划分算法.笔者对算法的基本概念以及实现进行了详细的描述,通过应用在实例上所得结果说明算法的可行性.     

利用视觉显著性的前景目标分割

针对图像中的前景目标分割问题,提出一种视觉显著性引导的前景目标分割算法.对原始图像进行预处理后分解为互不重叠的超像素区域.将这些区域构成一个无向图,相邻两个区域间存在边,通过计算相邻区域间的特征差异得到边的权值.提取图像边缘的超像素区域作为背景区域,利用无向图计算各超像素区域相对于背景区域的视觉显著性,得到初始显著图.对初始显著图进行改进和优化,根据视觉显著性计算结果采用自适应阈值进行前景目标分割.在公开的图像数据集MASR-1000、ECSSD、Pascal-S和SOD上进行实验验证,并和目前流行的算法进行对比.结果表明,本研究算法在查准率、召回率、平均绝对误差及F-Measure等方面优于目前流行的几种算法,用于图像和视频的前景目标检测与分割是正确有效的.     

通信网最佳可靠路由确定方法研究

研究了对给定拓扑结构的通信网在节点和边同时存在随机破坏的情况下,利用赋权无向图模型,通过计算点对间的路由概率确定最佳可靠路由的两种算法－－邻接矩阵算法和动态路由算法。该算法不仅应用于确定最佳可靠路由,而且适用于以其它类似参量为目标函数的最佳路由确定问题。     

用矩阵判断无向图同构的几种方法

给出了用无向图的邻接矩阵及关联矩阵判断两个图是否同构的两种新方法。     

基于随机游走策略的专家关系网络构建

专家关系组织是专家关系网络构建的核心。提出了一种基于随机游走策略的专家关系网络构建方法,该方法首先提取专家实体及关系,获得专家之间朋友关系、指导关系及同事关系的简单无向图,利用图中专家节点连接关系,构建专家关系矩阵,然后借助随机游走策略思想,将若干表征专家关系的简单无向图进行有机组合,从而构建出复杂专家关系网络。实验结果验证了该方法的有效性。     

基于语义路径覆盖的Gene Ontology术语间语义相似性度量方法

进行GO(gene ontology)语义相似性度量是解决生物学数据集成中语义异构问题的重要方法. 传统方法主要是基于距离的度量和基于信息量的度量.文中提出了一种基于语义路径覆盖的度量方法，并实现了其中Combine算法.该算法首先计算出每个节点的信息量，然后分别计算两个节点的语义路径的交的节点信息量之和以及这两个节点语义路径的并的节点信息量之和，将这两者之间的比率作为相似性度量值.实验结果表明该算法具有较高的相关系数.     

图与它们的表示之间的关系

本文研究了无向图的性质与无向图表示之间的关系     

3度非对称的点传递图的性质

设X为3度连通的简单无向图,X称为具有非平凡点稳定子群的非对称的点传递图,若X的全自同构群A在X的顶点集合上作用是传递的,而且X的任意顶点在A中的稳定子群在该点的邻域上的作用是非传递的、非平凡的.本文考察了这种图,我们给出了这类图的一些性质.     

分布式优化在智能电网经济调度问题中的应用

为了减少智能电网中节点之间信息交换的需求,降低智能电网的发电成本和用户的用电消费,提出了一种时变拓扑下的分布式优化算法,用以寻找经济调度问题的最优解;结合图论的相关理论,将节点之间的信息交换用时变无向图表示,并根据光滑精确罚函数的思想,简化经济调度问题,将优化问题中的不等式约束整理到目标函数中,从而得到一个只含有等式约束的新的优化问题,随后通过调整参数值求得最优值,因为算法考虑了每个节点的容量约束,所以在实际应用中具有更好的普适性;证明了当全局目标函数取得最小值时,各个节点共同达到最优解,最后通过实例验证了算法的有效性和可行性。     

关于完全s部整图

F.Harary和A.J.Schwenk(Lecture Notes in Mathematics.Berlin:Springer-Verlag,1974,406:46-51.)提出了整图的概念,即当无向图G的邻接矩阵A的特征值都是整数时,G称为整图.目前,人们已经研究了n类简单整图的性质,并得到了一些有趣的结果.运用线性代数方法证明了两个结论:设r,r1,r2,s是正整数,那么:1)完全s部图K(r,r,…,r)是整图;2)完全2部图K(r1,r2)是整图的充要条件是r1r2为完全平方数.     

Graph publishing method based on differential privacy protection

There are growing concerns surrounding the data security of social networks because large amount of user information and sensitive data are collected. Differential privacy is an effective method for privacy protection that can provide rigorous and quantitative protection. Concerning the application of differential privacy in social networks,this paper analyzes current trends of research and provides some background information including privacy protection standards and noise mechanisms.Focusing on the privacy protection of social network data publishing,a graph-publishing model is designed to provide differential privacy in social networks via three steps: Firstly,according to the features of social network where two nodes that possess certain common properties are associated with a higher probability,a raw graph is divided into several disconnected sub-graphs,and correspondingly dense adjacent matrixes and the number of bridges are obtained. Secondly,taking the advantage of quad-trees,dense region exploration of the adjacent matrixes is conducted. Finally,using an exponential mechanism and leaf nodes of quad-trees,an adjacent matrix of the sanitized graph is reconstructed. In addition,a set of experiments is conducted to evaluate its feasibility,availability and strengths using three analysis techniques: degree distribution,shortest path,and clustering coefficients.     

基于图注意力和特征融合的链路预测方法

链路预测是一种还原网络缺失信息的方法，通过当前已观察到的链路，预测实际存在但未被观察到的链路或可能出现的新链路.当前链路预测主要是基于图神经网络的深度学习方法，相比基于规则的启发式方法，前者可有效利用网络拓扑结构信息，较大地提升了网络链路预测性能，并可应用到类型更广泛的网络中.但是现有基于图神经网络的方法，仅利用网络中节点相对位置信息，忽视了节点基本属性和链路的邻居信息，且无法区分不同节点对链路形成的重要程度.为此，本文提出一种基于图注意力网络和特征融合的链路预测方法.通过增加节点的度、链路的共同邻居数量和共同邻居最大度等特征，丰富了网络的输入特征信息.本文首先提取以目标节点对为中心的子图，然后将其转化为对应的线图，线图中的节点和原图中的链路一一对应，从而将原图节点和链路信息融合到线图的节点中，提升了特征融合的有效性和可解释性.同时本文使用图注意力机制学习节点的权重，增强了特征融合的灵活性.实验表明，本文所提出的方法，在多个不同领域数据集上的AUC和AP均超过90%,在已观测链路缺失较多时，预测性能保持80%以上，且均优于现有最新方法.     

环的强零因子图的一个注记

一个环R的一个元α叫做一个强零因子,假如对R中的某个非零元b,有〈α〉〈b〉=0,或者〈b〉〈α〉=0（其中〈x〉是由x∈R生成的理想）．在该文中,用S（R）表示所有强零因子的集合．对于任意的一个环r,用^~Г（R）表示一个无向图,它的顶点集是S（R）^＊=S（R）-{0},其中两上不同的顶点α和b相连当且仅当〈n〉〈b〉=0或者〈b〉〈α〉=0．该文主要研究质环直积的强零因子图的团数．     

基于度信息的图像过渡区提取与分割

提出一种基于度信息的图像过渡区提取与分割算法．将一幅图像映射为带权无向图,权函数定义为节点之间的相似度,由于目标内部与背景内部的像素同质性好,相似度大,因此度值较大,而边缘像素的度值就小,由此提取过渡区并进行图像分割．实验结果表明,本方法能够稳定地提取过渡区,且处理速度明显优于原有的过渡区提取方法。     

基于粘贴系统求解无向图最短路径问题的DNA计算模型

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。     

关于图的拟拉普拉斯特征多项式

设G是一简单无向图,C（G）表示G的无向关联矩阵,Q（G）＝C（G）C（G）^T,det(λI-Q(G)称为图G的拟拉普拉斯特征多项式,该文图的拟拉普拉斯特征多项式的系数进行了研究,给出了图的拟拉普拉斯特征多项式系数的一些性质,得到了正则图的线图,细分图,全图的的拟拉普拉斯特征多项式。