具有结果多样性的近似子图查询算法

针对大型图中的各种top-k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.     

SLAM中融合形状上下文和随机步进的图匹配数据关联算法

提出了一种在非确定环境下求解SLAM数据关联问题的图匹配算法. 算法建立了SLAM中数据关联的图论模型,对图模型节点提取了不依赖位置信息的形状上下文特征(shape context,SC),最后通过二次加权随机步进算法(reweighted random walks,RRW)得到图匹配问题的优化解. RRW&SC图匹配算法充分利用了路标间的拓扑结构关系以及路标间的形状结构,极大地扩展了数据关联时所依据的几何信息量. 仿真实验结果表明,与传统算法相比,该算法能有效处理SLAM中噪声干扰增加、机器人迷失、路标被动态遮挡等不确定程度高、歧义性大环境中的数据关联.      

基于改进TADW的链路预测算法

针对经典的节点相似性链路预测算法只考虑网络拓扑结构或者节点属性信息的问题,使用词嵌入模型Word2vec学习得到节点文本属性信息的表示,进而改进TADW(text-associated deep walk)算法,弥补其语义信息表示能力的不足.基于改进的TADW图嵌入方法提出一种融合网络拓扑结构和节点属性信息的相似性指标,并基于此相似性指标提出链路预测算法.在三个真实数据集上的实验结果表明所提出算法可以提高预测精度,并具有更好的鲁棒性,同时使用图嵌入的方法有效解决了网络数据的稀疏性问题.     

采用方向场配准和图匹配的指纹匹配算法

提出一种新的指纹匹配算法.在配准阶段,引入局部方向场匹配,并结合局部细节点拓扑结构匹配以进行指纹对齐;在对齐后的匹配中,首先在两个指纹的细节点集之间进行弹性匹配,得到一个由匹配的细节点对组成的相似集,然后以相似集中的细节点做顶点,以各顶点之间的连线为边,为输入指纹和模板指纹组成对应的拓扑图进行图匹配;还引入了全局方向场匹配,并与细节点集匹配进行融合,以提高算法的精度.采用FVC2002公布的指纹库进行对比实验,结果证明了算法的有效性.     

基于定向天线的无线自组网拓扑控制算法

为采用定向天线的特点解决无线自组网中节点异构、能量有限、带宽受限的问题,提出了一种基于定向天线的异构无线自组网拓扑控制算法K-DRNG.该算法包括三个阶段:信息收集阶段,节点控制发射功率,通过扇区转换机制收集邻域拓扑信息;拓扑构建阶段,节点根据链路权重和节点剩余能量构建定向邻近图;拓扑优化阶段,构建初始拓扑子图及添加或删除方向性链路,确保生成拓扑的双向连通性.仿真结果表明,算法能够降低网络中的节点平均能耗,提高无线资源空间复用性,改善网络性能.     

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

基于异质图神经网络的推荐算法研究

基于图神经网络的推荐算法通过从图中获取知识,提高了推荐的可解释性.然而随着推荐系统网络数据规模的不断扩大,用户-项目评分矩阵呈现出稀疏性问题,图神经网络难以学习到高质量的网络节点特征,导致推荐质量下降.本文将图神经网络与异质信息网络相结合,提出一种基于异质图神经网络的推荐算法.该算法使用异质信息网络对多源异质数据进行联合解码,将注意力机制引入用户-项目交互网络和用户社交网络的用户、项目聚合表示过程,从而实现用户-项目交互和用户社交两类网络间的节点及拓扑结构特征的有效融合.两个公开数据集上的对比实验结果表明,本文提出的算法在不断稀疏化的数据集上的推荐误差比基线方法少40％.     

P2P网络借贷平台中债权匹配问题的建模及算法研究

在P2P网络借贷平台中,债权匹配问题即如何匹配贷款人与借款人,使得平台的效率及效益最高是一个非常重要的问题.针对P2P网络借贷问题中的债权匹配问题,建立了以借款人与贷款人双方的满意程度最大为目标的数学模型,提出了一种基于满意度的搜索算法,基于该算法对债权匹配问题进行了求解,并通过数据实验验证了该算法的有效性.     

基于图多层感知机的节点分类算法

多数图神经网络(Graph Neural Networks, GNN)通过设计复杂的节点信息传递和聚合方式，以提升节点分类等图分析任务的实验表现，而本文提出了一种无需信息传递和聚合的图多层感知机(Multi-Layer Perceptron, MLP)模型A&T-MLP,利用属性和拓扑信息引导的对比损失来增强模型表征能力。A&T-MLP首先使用属性矩阵和邻接矩阵计算节点间的属性和拓扑相似度；然后使用基于相似度信息引导的对比损失，增大特征空间中相似节点的一致性和不相似节点的差异性；最后构建多层感知机模型并引入交叉熵损失进行端到端训练。在节点分类任务中，A&T-MLP表现优于基线模型，Wikipedia数据集上的Micro-F1和Macro-F1相较GNN模型图卷积网络(Graph Convolutional Network, GCN)提升了15.86%和13.64%。实验结果表明，A&T-MLP能够通过对比损失保留丰富原始图的信息，提升模型性能。此外，A&T-MLP在处理拓扑信息不准确的图数据时具有较为明显的优势，即使在缺失80%拓扑信息的极端情况...