基于GraphSage节点度重要性聚合的网络节点分类研究

传统的图嵌入算法及图神经网络模型在对网络节点分类时仅使用了节点本身的属性信息或者特征信息,很少使用节点在网络中的结构信息。如何在图神经网络聚合时引入节点网络结构信息来提升分类准确性也是一个值得深入研究的问题。因此,本文在GraphSage模型的基础上,根据网络中节点度及节点重要性设计了新的聚合函数并提出了一个新的GraphSage-Degree模型。首先,模型根据节点度获得节点在邻域中的重要性,然后再以重要性为依据来聚合节点的特征,使得网络中重要的节点能够尽可能的聚合更多的特征信息,并且在GraphSage-Degree中设置了一个与节点度有关的超参数D,能够通过调节该参数D使得在不同的数据集上达到最佳分类状态。在Cora、Citeseer和Pubmed三个公开数据集上进行了测试,GraphSage-Degree与其他方法相比,macro-F1的平均提升值分别为8.72%、10.37%和8.29%,在Pubmed上有最大提升值38.84%;micro-F1的平均提升值分别为8.97%、11.16%和6.9%,在Pubmed上有最大提升值38.39%。     

融合LDA的门控图卷积网络文本分类研究

在现有文本图基础上引入隐狄利克雷分布,将文档-主题和主题-词信息融入文本图以丰富文本图中节点间关系,之后将该文本图送入一个基于图卷积网络门控机制模型.在多个数据集上进行验证.结果表明,所提出的模型优于现有图卷积网络文本分类模型.     

基于图注意力网络的案件罪名预测方法:CP-GAT

案件罪名预测任务是基于文本数据去预测案件所属罪名.针对现有方法在相似罪名和长尾数据集上表现不佳的问题，提出了一种基于图注意力网络的案件罪名预测方法CP-GAT(charge prediction based on graph attention network).该方法首先使用司法文书数据集中的案例事件描述文本和案例对应的法条信息建立异质图结构数据，构建后的异质图包含两种类型的节点(词节点、案例节点)，两种类型的边(词节点与词节点相连的边，词节点与案例节点相连的边).在基于法律文本构建后的异质图上使用图注意力网络进行图特征提取，最后将得到的特征向量输入到罪名预测的分类器中，得到案例所属的罪名.在CAIL2018法律数据集上的实验结果表明，基于图注意力网络的罪名预测方法优于对比实验使用的方法，准确率和宏观F1值分别达到了95.2%和66.1，验证了提出的方法有利于提升案件罪名预测任务的性能.     

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

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

基于卷积神经网络的灾难场景图像分类

为了对灾难场景图像进行快速分析和识别,提出了一种基于多分辨率卷积神经网络和残差注意力机制(attention module)相结合的图像分类模型.首先,对灾难场景数据集进行预处理,在相同类型的条件下将其随机划分为训练集和测试集.基于改进的卷积神经网络(convolutional neural network,CNN),提取训练集的图像特征.使用训练集图片的特征进行训练,并且在测试集图片上实现分类测试.选取DenseNet、Xception和MobileNetV2三种模型,以灾难场景数据集(Disaster_Data_Scenes)为数据集进行实验验证.结果表明:改进的Xception和MobileNetV2网络在灾难场景数据集上进行的图像分类实验测试,比原网络精度分别提升了4.56％和3.04％.其中改进的DenseNet网络比原网络模型精度分别提升9.13％、17.88％和10.27％.可见改进的卷积神经网络模型的分类精度得到有效提高.     

非稳态拓扑下的机会网络分层模型

为了解决在消息敏感的机会网络中社团划分结果不可重用的问题,提出了一种与消息类型相匹配的机会网络分层模型.首先,将机会网络的物理节点集映射为与消息类型匹配的虚拟节点集,并以此为基础建立虚拟机会网络层;然后,在虚拟机会网络层上,建立虚拟节点集的社会关系;最后,对虚拟节点集的社会关系进行社团划分.实验结果表明:在消息数量相同的条件下,当消息序列中相邻位置消息的类型差异度分别为40%和100%时,在虚拟层上进行社团划分的时间与在物理机会网络上直接进行社团划分的时间相比分别减少约58%和89%;基于分层模型的社团划分的运行次数仅依赖于消息类型的数量,而不会随消息数量或消息序列中不同类型消息交错方式的变化而变化.     

一种基于节点稳定性的社区发现算法

许多成功的社区发现算法已经被广泛应用于复杂网络社区发现任务中.随着数据复杂性的增加,网络中节点间的关系也呈现多样化的特点,因此提出一种基于信息熵的节点稳定性度量方法,衡量网络中节点在社区划分中的稳定性;并在此基础上提出一种基于节点稳定性的社区发现算法(Node Stability-based Algorithm,NSA).首先得到网络的t种社区划分,计算各节点的标签熵,选择熵小于一定阈值的节点作为网络的稳定节点集S;然后,利用所得到的稳定节点集S从原网络中抽取一个包含S的连通子图Gs,使Gs中节点的不稳定性尽可能低;在连通子图Gs上进行社区发现,得到初始聚类结果,再计算其他未聚类节点与初始类簇的距离,确定其社区归属,得到最终聚类结果 .在四个带标签真实网络数据集和八个不带标签的真实网络数据集上,与LPA,Infomap,Walktrap,BGLL,LPA-S等经典算法的比较实验表明,所提出的NSA算法能够较好地进行社区发现,在NMI和模块度等方面表现良好.     

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

多数图神经网络(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%拓扑信息的极端情况...     

基于路径相互关注的网络嵌入算法

网络嵌入,或者称为网络表示学习,旨在将网络中的节点映射到表示空间中,生成低维稠密的向量,从而在保留网络结构信息的前提下对网络中的节点进行表示,而后通过已有的机器学习方法解决诸如链接预测、节点分类、社团发现和网络可视化等下游任务.随机游走算法可以很好地探索网络中节点的局部结构,然而之前的基于随机游走的表示学习算法只能为节点产生一种角色嵌入,没有考虑到和不同邻居进行交互时节点扮演的不同角色嵌入.因此,提出一种基于路径相互关注的网络嵌入算法,使用节点随机游走产生的上下文信息,通过注意力机制为每个节点生成上下文相互关注的节点嵌入.在真实数据集上的实验结果表明,与三个经典的网络嵌入算法相比,该算法具有更好的表现.     

基于DynamicRank的重要节点集挖掘算法

为了更为有效地挖掘复杂网络中综合影响力高的节点集、提高重要节点集挖掘算法的准确性,针对节点集中各节点在信息传播中不同程度的相互促进和相互抑制作用,基于DynamicRank算法设计了一种新的级联概率计算模型。通过增强贪心策略,优先从种子集邻居以外的节点中选取备选节点,减小种子集内重叠邻居对信息传播引发的抑制作用;利用级联概率计算模型,增强种子集对信息传播的级联促进作用。在4个实际网络上采用SIR模型进行了测试,实验结果表明,相较于已有重要节点挖掘方法H-index、Degree、DynamicRank、VoteRank和EnRenew,提出的算法挖掘出的节点集具有更高影响力。特别地,在Grid数据集上,本文方法挖掘出的种子集的传播范围比对比算法平均提升了49.3%。提出的算法针对信息传播概率和贪心策略的改进有利于重要节点集的挖掘和识别。     

一种基于图深度优先搜索的基本路径集自动生成优化算法

本文介绍了一种结合边访问标志集合使用图深度优先搜索方法遍历控制流程图,生成最小长度测试序列基本路径集合的优化算法.以矩阵工具为算法提供输入,利用回滚机制避免程序控制流中环造成的不收敛,提出引入结点复用路径最小长度记忆机制对结果进行优化,获得最小长度测试序列的优化基本路径集合作为算法输出.     

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

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

一种多层次语义视频对象分割算法

提出一种基于高斯马尔可夫随机场及规则化图划分的多层次语义视频对象分割算法,其主要特点是将视频序列帧中对象的分割看成是“内容树”结构中复合结点的形成过程.首先使用高斯-马尔可夫模型来进行视频帧内的最优标记场标定,然后引入规则化图划分准则进行过分割区域的合并,得到具有语义意义的视频对象.实验表明,本分割算法具有较高的准确性,误差的均值为11.375%,标准方差为0.94%.     

基于图神经网络的兴趣点推荐的隐私保护框架

传统的基于图神经网络的兴趣点模型的研究是通过简单的注意力机制进行权重定义,或仅仅将多种因素简单进行线性组合,缺乏从多角度考虑用户和兴趣点自身的语义信息和交互信息。此外,现有的图神经网络推荐依赖于图结构信息的集中式存储和训练,存在隐私泄露风险。为了解决上述问题,提出基于图神经网络的兴趣点推荐的隐私保护框架(privacy of POI recommendations for graph neural networks, PPGNN)。首先,通过引入多特征模式和注意力机制对图结构进行强化,构建强化用户社交关系图模型;其次,通过多场景角度提出兴趣点邻居结点采样算法以及重新设计卷积聚合机制,对异质图使用语义级别注意力机制进行聚合;最后,提出了可变动态梯度的客户端差分隐私算法,达到边优化边反馈的效果。通过在Yelp和Gowalla不同的数据集上进行大量实验,证明该方案具有有效性,弥补了图神经网络推荐因隐私威胁带来的局限性,优于集中式图神经网络推荐方法,同时也优于传统兴趣点推荐方法,并且PPGNN可以更好地克服推荐中的数据稀疏和冷启动问题。     

基于雷达图表示原理的英文字符识别方法

在多元数据多元图表示原理理论基础上,提出了一种新的字符模式识别方法.首先基于多元数据雷达图表示原理进行字符的非数值数据-数值数据变换,进而实现字符信息的雷达图表示;然后对待识别字符进行多元图图形基元和特征基元分析,形成字符识别的多元图基元表示模犁;最后在字符识别的多元图基元表示模型基础上实现字符识别.本文以手写体大写英文字符的识别为例介绍该方法,通过实验证明该方法具有较好的识别效果.     

无线网络中一种智能路由算法

一个ad hoc网络是一个多跳无线网络,网络中的节点互相通信而不依赖于预先架设的固定基础设施,这种动态网络的最重要特点是寻找在通常情况下很好执行的路由算法。基于“簇”的算法是最有效的算法,目前,创建和维持“簇”通常是基于启发式方法。MWIS是一个分布式算法用于在一个无线网络拓扑图中确定最大权独立集算法,而划分网络节点为“簇”的问题可以很容易简化为寻找最大权力集问题。基于MWIS,我们提出了寻找一个最大向量权独立集算法MVWIS并且通过MATUB进行了仿真实验。     

厂网分开条件下购电配电计划的优化方法

将电力系统描述为一个由发电节点和用电节点两类构成的二分图·在电力系统的经济决策和系统运行技术分析可以分别进行的前提下,提出一种电力市场下电力购买与配送计划优化的模型,基于图论理论给出模型解存在的必要条件·并提出基于线性规划的模型求解算法·根据各类节点的电量和资金平衡条件,构造包含节点电价的线性方程组,从而构成确定各节点成本电价的方法·上述方法对大量来源于实际电力系统购配电计划模拟问题进行了计算,取得了满意的结果·     

Improved Approximate Minimum Degree Ordering Method and Its Application for Electrical Power Network Analysis and Computation

Electrical power network analysis and computation play an important role in the planning and operation of the power grid, and they are modeled mathematically as differential equations and network algebraic equations.The direct method based on Gaussian elimination theory can obtain analytical results. Two factors affect computing efficiency: the number of nonzero element fillings and the length of elimination tree. This article constructs mapping correspondence between eliminated tree nodes and quotient graph nodes through graph and quotient graph theories.The Approximate Minimum Degree(AMD) of quotient graph nodes and the length of the elimination tree nodes are composed to build an Approximate Minimum Degree and Minimum Length(AMDML) model. The quotient graph node with the minimum degree, which is also the minimum length of elimination tree node, is selected as the next ordering vector. Compared with AMD ordering method and other common methods, the proposed method further reduces the length of elimination tree without increasing the number of nonzero fillings; the length was decreased by about 10% compared with the AMD method. A testbed for experiment was built. The efficiency of the proposed method was evaluated based on different sizes of coefficient matrices of power flow cases.