基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

一种改进的针对合著关系网络的链接预测方法

主要针对那些实体类标号属性未知的社会网络进行链接预测.由于实体的类标号属性与具体的社会网络有关,因此具体解决对作者之间合著关系网络图的链接预测问题.首先,给出了合著关系图的结构表示,然后把一个作者是否是多产的定义为合著关系图中作者实体的类标号属性.另外,还提出了一种改进的利用有指导学习进行链接预测的方法.在改进的链接预测方法中为每对作者新引入了一个特征属性--是否至少有一个是多产的.当所要预测的合著关系图中作者实体的类标号属性不完全已知时,用改进后的ICCLP算法对合著关系进行预测,以提高链接预测的性能.改进后的ICCLP算法中采用上面提到的改进后的链接预测方法.     

一种增量式约简方法求解最小顶点覆盖问题

最小顶点覆盖问题是一个应用很广泛的NP难题,针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转化为一个决策表的最小属性约简问题;利用增量式属性约简思想,随着图中边数的增多,提出一种更新最小顶点覆盖的增量式属性约简算法;该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度,同时针对大规模图问题,可随着边的增加动态更新最小顶点覆盖,因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间;实验结果表明该算法的可行性和有效性。     

一种有效的社会网络社区发现模型和算法

社会网络的社区发现存在划分效果较好的算法时间复杂度过高、现有快速划分算法划分质量不佳、缺乏表达和充分利用个体和链接属性信息的模型和机制等问题.针对这些问题,提出了一种边稳定系数模型和一种能表达个体间关系紧密度的完全信息图模型,在此基础上设计和实现了一种有效的社区发现算法.提出的完全信息图模型具有较高通用性,适用于需要融合个体和链接属性的社区发现算法.通过系列实验表明,所提出的以边稳定系数模型和完全信息图为基础的算法,对社会网络中的社区发现问题是有效的.算法不仅具有较快的速度,也能适用于带权与不带权的网络,得到的社区划分结果也具有较高的划分质量.     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

结构-属性平衡图节点相似度测量算法

摘  要：节点相似度是图聚类算法的重要基础,在基于结构-属性图聚类现有方法中,由于传统图模型的限制,需要多次矩阵相乘来调整属性边的权值,算法执行效率低。为解决这一问题,提出了结构-属性平衡图的概念,并采用随机游走模型策略统一度量结构-属性平衡图GB中顶点间的相似度。与现有方法相比,该方法不但能测量直接相连的顶点之间的相似度,还可测量不直接相连而存在不同长度的路径的顶点之间的相似度,且没有增加原相似度矩阵的规模,节省了大量存储空间,提高了算法执行效率。     

粗糙形式概念抽取的属性集合幂集方法

为了最大限度地抽取出形式背景中的粗糙形式概念,以便为粗糙概念格的构建提供完整的信息源,对粗糙形式概念的抽取进行了研究,提出了粗糙形式概念抽取的属性集合幂集方法.其操作要点为:粗糙形式概念的内涵由属性集合幂集方法所求得的子集确定,粗糙形式概念的外延由属性集合幂集所对应对象的上下近似集确定.该方法实现了粗糙形式概念的抽取,...     

异质信息网络中最大路径连通Steiner分量查询算法

异质信息网络(HINs)是包含多种类型对象(顶点)和链接(边)的有向图,能够表达丰富复杂的语义和结构信息.HINs中的稠密子图查询问题,即给定一个查询点q,在HINs中查询包含q的稠密子图,已成为该领域的热点和重点研究问题,并在活动策划、生物分析和商品推荐等领域具有广泛应用.但现有方法主要存在以下两个问题:(1)基于模体团和关系约束查询的稠密子图具有多种类型顶点,导致其不能解决仅关注某种特定类型顶点的场景;(2)基于元路径的方法虽然可查询到某种特定类型顶点的稠密子图,但其忽略了子图中顶点之间基于元路径的连通度.为此,首先在HINs中提出了基于元路径的边不相交路径的连通度,即路径连通度;然后,基于路径连通度提出了k-路径连通分量(k-PCC)模型,该模型要求子图的路径连通度至少为k;其次,基于k-PCC模型提出了最大路径连通Steiner分量(SMPCC)概念,其为包含q的具有最大路径连通度的k-PCC;最后,提出一种高效的基于图分解的k-PCC发现算法,并在此基础上提出了优化查询SMPCC算法.大量基于真实和合成HINs数据的实验结果验证了所提出模型和算法的有效性和高效性.     

一种基于粗糙熵的信息系统属性约简算法

在信息系统中,研究了知识的粗糙性,定义了一种粗糙熵度量方法,并证明了知识的粗糙熵随着划分的增大而单调增加的结论,给出了属性的重要性度量方法,在此基础上提出了一种基于粗糙熵的启发式属性约简算法。实例验证表明,该算法能有效地从信息系统中获取最优属性约简。     

一种融合节点属性信息的社会网络链接预测方法

随着大规模社会网络的发展,链接预测成为了一个重要的研究课题。研究了在社会网络中融合节点属性信息进行链接预测,在传统的社会-属性网络图模型的基础上,将节点属性的类别这一重要参量加入到网络构建中。基于此,提出了一系列为网络中不同类型的连边分配边权重的方法,最后通过随机游走的方法进行网络链接的预测。实验表明,所提链接预测方法相比同类方法有明显的效果提升。     

基于多维社交关系嵌入的深层图神经网络推荐方法

社会化推荐系统通过用户的社会属性信息能缓解推荐系统中数据稀疏性和冷启动问题，从而提高推荐系统的精度。然而大多数社会化推荐方法主要针对单一的社交网络，或对多个社交网络进行线性叠加，使得用户社会属性难以充分参与计算，因而推荐的精度有限。针对该问题，提出一种多重网络嵌入的图形神经网络模型来实现复杂多维社交网络下的推荐，该模型构建了统一的方法来融合用户-物品、用户-用户等各种关系构成的多维复杂网络，通过注意力机制聚合不同类型的多邻居对节点生成作出贡献，并将多个图神经网络进行组合，从而构建了多维社交关系下的图神经网络推荐框架。这种方法通过拓扑结构直接反映推荐系统中实体及其相互间关系，直接在图上对相关信息进行不断更新计算，具有很强的归纳性，有效避免了传统推荐方法中信息利用不完全的问题。通过与相关的社会推荐算法进行比较，实验结果表明，所提方法在均方根误差（RMSE）和平均绝对误差（MAE）等推荐精度指标上有所改善，甚至在数据稀疏情况下也有良好的精度。     

基于多维社交关系嵌入的深层图神经网络推荐方法

社会化推荐系统通过用户的社会属性信息能缓解推荐系统中数据稀疏性和冷启动问题,从而提高推荐系统的精度。然而大多数社会化推荐方法主要针对单一的社交网络,或对多个社交网络进行线性叠加,使得用户社会属性难以充分参与计算,因而推荐的精度有限。针对该问题,提出一种多重网络嵌入的图形神经网络模型来实现复杂多维社交网络下的推荐,该模型构建了统一的方法来融合用户-物品、用户-用户等各种关系构成的多维复杂网络,通过注意力机制聚合不同类型的多邻居对节点生成作出贡献,并将多个图神经网络进行组合,从而构建了多维社交关系下的图神经网络推荐框架。这种方法通过拓扑结构直接反映推荐系统中实体及其相互间关系,直接在图上对相关信息进行不断更新计算,具有很强的归纳性,有效避免了传统推荐方法中信息利用不完全的问题。通过与相关的社会推荐算法进行比较,实验结果表明,所提方法在均方根误差（RMSE）和平均绝对误差（MAE）等推荐精度指标上有所改善,甚至在数据稀疏情况下也有良好的精度。     

语义增强的大规模多元图简化可视分析方法

网络图可视化可以有效展示网络节点之间的连接关系,广泛应用于诸多领域,如社交网络、知识图谱、生物基因网络等.随着网络数据规模的不断增加,如何简化表达大规模网络图结构已成为图可视化领域中的研究热点.经典的网络图简化可视化方法主要包括图采样、边绑定和图聚类等技术,在减少大量点线交叉造成的视觉紊乱的基础上,提高用户对大规模网络结构的探索和认知效率.然而,上述方法主要侧重于网络图中的拓扑结构,却较少考虑和利用多元图节点的多维属性特征,难以有效提取和表达语义信息,从而无法帮助用户理解大规模多元网络的拓扑结构与多维属性之间的内在关联,为大规模多元图的认知和理解带来困难.因此,本文提出一种语义增强的大规模多元图简化可视分析方法,首先在基于模块度的图聚类算法基础上提取出网络图的层次结构;其次通过多维属性信息熵的计算和比较分析,对网络层次结构进行自适应划分,筛选出具有最优属性聚集特征的社团;进而设计交互便捷的多个关联视图来展示社团之间的拓扑结构、层次关系和属性分布,从不同角度帮助用户分析多维属性在社团形成和网络演化中的作用.大量实验结果表明,本文方法能够有效简化大规模多元图的视觉表达,可以快速分析不同应用领域大规模多元图的关联结构与语义构成,具有较强的实用性.     

基于信息增益和粗糙集的入侵检测方法

传统的随机森林在网络入侵检测中收敛速度慢,并且学习性能不够完善。为消除原始入侵检测数据中的冗余信息,提出一种基于信息增益和粗糙集的随机森林入侵检测方法。使用信息增益对数据的各个属性进行相关分析,删除冗余属性,减小属性简约的时间复杂度;利用粗糙集理论从数据中提取分明函数,求得属性简约;使用随机森林分类器进行分类。实验结果表明,该方法收敛速度较快,在召回率和精度方面都要高于传统的随机森林方法,尤其是在训练样本充足的网络环境下,效果更加明显。     

IBNAD:一种基于交互的5G核心网网络功能异常检测模型

现有 5G(5th Generation Mobile Communication Technology)核心网异常检测主要基于信令流量深度解析, 但较少利用核心网网络功能交互关系的作用。针对上述问题, 提出一种基于交互的 5G 核心网网络功能异常检测模型。首先, 该模型以行为分析为驱动, 基于信令流量和网络功能注册数据提取多维属性, 通过行为画像来表征网络功能行为模式, 并采用集成学习算法RFECV(Recursive Feature Elimination with Cross-Validation)进行属性特征选择, 降低特征维度的同时筛选出与区分网络功能行为模式高度相关的属性特征。然后, 模型基于网络功能交互关系对核心网进行图建模, 建模后的图数据融合了网络功能属性信息和交互信息。最后, 模型通过基于空间域的图卷积网络聚合邻域节点属性信息和结构信息来融合行为模式特征, 新生成的节点表示用于分类, 从而将核心网网络功能异常检测问题转化为图节点分类问题。通过在 free5GC 仿真平台上采集数据, 并在搭建的异常检测系统中的实验表明, 该模型的异常检测性能优于基于属性特征分析的传统机器学习模型、基于结构特征分析的图嵌入模型及部分 5G 核心网异常检测模型。10%数据集作为训练集时, 所提模型的准确率比支持向量机模型提高 6.6%, 比Struc2vec 模型提高 13%, 比深度神经网络模型提高 8%。     

基于粗糙集的不完备信息系统增量式属性约简

属性约简是粗糙集理论在模式识别中一项重要的应用,传统的属性约简算法只适合处理静态的信息系统,而处理不断动态更新的信息系统面临着巨大的挑战。对于不完备信息系统,提出一种增量式的属性约简算法。在不完备信息系统下引入粗糙集理论中关于正区域的概念,针对不完备信息系统中属性增加的情形,提出了基于正区域的增量式属性约简算法。实验结果表明了所提出的增量式属性约简算法比非增量式的算法具有更高的效率,同时比其他同类型的算法具有更高的优越性。     

基于粗糙图的网络风险评估模型

针对在进行网络安全分析时所获得的信息系统是不完备的、粗糙的这一特性,将网络攻击过程类比于粗糙不确定性问题的关系挖掘过程,提出基于粗糙图的网络风险评估模型。该模型由部件节点粗糙关联网络、攻击图的粗糙图生成算法以及网络风险最大流分析算法三部分主要内容组成;并以一个具有代表性的网络系统实例阐明了该模型的使用方法,验证了模型的正确性。模型优势分析表明其较以往的攻击图、风险评价模型更能真实地反映实际情况,所获得的评估结论、安全建议等也更加准确、合理。     

基于图分析和支持向量机的企业网异常用户检测

在企业网络中,若其内部的攻击者获得了用户的身份认证信息,其行为与正常用户将很难区分;而目前研究对于企业网中的异常用户检测方法比较单一,召回率不高。用户的认证活动信息直接反映了用户在网络中与各类资源或人员的交互,基于此,提出一种利用用户认证活动信息来检测网络中异常用户的方法。该方法利用用户的认证活动生成用户认证图,之后基于图分析方法提取认证图中的属性,如图的最大连通组件的大小、孤立认证的数量等,这些属性反映了用户在企业网中的认证行为特征。最后利用有监督的支持向量机（SVM）对提取到的图属性进行建模,以此来间接识别和检测网络中的异常用户。在提取了用户图向量之后,具体对训练集和测试集、惩罚参数、核函数取不同值的情况进行了分析。通过对这些参数的调节,召回率、精确率和F1-Score均达到80%以上。实验数据表明,该方法能够有效检测企业网络中的异常用户。     

不完备邻域粗糙集的不确定性度量和属性约简

针对现有的属性约简算法不适合处理数值型属性和符号型属性共同存在的不完备数据,提出了一种拓展不完备邻域粗糙集模型。首先,通过考虑属性值的概率分布来定义缺失属性值之间的距离,可以度量具有混合属性的不完备数据;其次,定义了邻域混合熵来评价属性约简的质量,分析证明了相关的性质定理,并构造了一种基于邻域混合熵的不完备邻域粗糙集属性约简算法;最后从UCI数据集中选取了7组数据进行实验,并分别与基于依赖度的属性约简（ARD）、基于邻域条件熵的属性约简（ARCE）、基于邻域组合测度的属性约简（ARNCM）算法进行了比较。理论分析和实验结果表明,所提算法约简属性比ARD、ARCE、ARNCM分别减少了约1,7,0个,所提算法的分类精度比ARD、ARCE、ARNCM分别提高了约2.5,2.1,0.8个百分点。所提算法不仅能够获得较少的约简属性,同时具有较高的分类精度。