基于矩阵运算的超网络构建方法研究及特性分析

基于邻接矩阵Khatri-Rao积运算及Khatri-Rao和运算,研究了构建超网络的方法,并通过边际节点度及联合节点度来研究超网络的内在机理。将Khatri-Rao积运算迭代地应用于一个初始图序列组成超网络的邻接矩阵,得到一个分形维数不超过3的自相似超网络。若所有初始图均是连通非二分图,则得到的超网络同时具有小世界特性,其直径不超过所有初始图直径和的两倍。此外,将Khatri-Rao和运算顺次应用于多个初始图序列组成超网络的邻接矩阵,得到一个边际节点度呈一维高斯分布而联合节点度呈高维高斯分布的随机超网络。最后,给出了基于矩阵运算的超网络构建方法的若干性质。     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

一种提高3D模型浅浮雕建模质量的方法

顶点数较少的3D模型本身细节不够丰富,浅浮雕建模生成的浮雕效果较差.针对低分辨率3D模型本身细节不够丰富的问题,引入深度学习的方法对3D模型生成的法向图做超分辨率放大,设计出一种基于法向图的超分辨率卷积神经网络,丰富低分辨率法向图的细节,网络的输入是低分辨率3D模型的法向图,输出是高分辨率法向图.实验结果表明:该算法可以有效提升低分辨率法向图的细节,显著提升低分辨率3D模型的浅浮雕建模质量.     

无向图与有向图的全部生成树的计算机算法

找有向图与无向图的全部生成树的问题,产生于解电网络的问题中。这个问题国外一直在进行研究,已经提出了各种有效的算法。近几年来,国内这方面的研究也在开展。 迄今为止,求无向图与有向图中所有生成树的最好算法是Gabow和Myers在1978年给出的算法(以下简称G-M算法)。本算法(以下称BST算法——即基于子树集的     

一种基于能量指数的复杂网络牵制控制策略

针对复杂大系统控制中,现有牵制控制策略仅依据拓扑结构而存在的不足和控制器设计中控制参数选择简单(视为常数)的问题,引入了能量指数的概念,提出一种新的牵制控制策略—–能量指数法.该方法同时考虑节点对于网络的贡献力和节点的网络特性,给出了引入能量指数后的网络动态模型描述,并将节点能量指数用于自适应控制器设计,得到了控制律设计新方法.与现有方法比较,所提方法可使系统收敛更快,更容易实现同步,从而表明基于能量指数的牵制策略和自适应控制器设计方法均是有效的,在电力、交通以及传染病防治等各种复杂网络中都具有实际应用价值.     

一种基于边缘提取的交互式图像分割算法

提出了基于边缘提取的交互式图像分割算法,该算法将图像映射为无向图,使用拉普拉斯零交叉点、边缘强度和动态轨迹长度构造能量模型,并为无向图中的边赋予能量代价.根据能量代价,引入角点信息,在交互得到的控制点间搜索最优路径,迭代此过程,实现分割.实验结果表明,该算法具有较高的精度和效率,能较好地克服噪声影响,适用于灰度及彩色图像.     

超网络的全终端可靠性分析

网络的可靠性是复杂网络研究的一个重要领域,能有效刻画某些复杂系统的超网络属于复杂网络的研究范畴。基于超网络的拓扑结构——超图,提出了超网络在边失效下的全终端可靠度的定义,并给出了计算可靠度的两种基本方法,即状态枚举法和因式分解法,依据因式分解法对一些具有特殊结构的超网络进行化简。作为超网络可靠性的应用,研究了连通生成子网络的数目;在与普通复杂网络的对比中可以得知,超网络的可靠性研究不能用其转换后的普通复杂网络可靠性作替代研究,该研究是对超网络可靠性研究的初步探索,有着广阔的研究空间和应用前景。     

基于多尺度图匹配核的场景单字识别方法

由于自然场景中的文字具有较大的类内间距, 因此识别场景文字具有很大的挑战性. 本文提出了一种基于多尺度图匹配核的场景单字识别方法. 为了利用字符特有的结构特征, 将每幅图像表示为基于不同网格划分的无向图, 通过计算两个无向图之间图匹配的最优能量值来得到两幅图像的相似度, 由于图匹配在计算每个节点的最佳匹配节点时也考虑了相邻节点之间的空间位置约束, 因此可以应对具有一定形变的文字. 通过图匹配得到的两幅图像之间的相似度很适合用来构造支持向量机的核矩阵. 本文将不同尺度网格划分下得到的核矩阵进行多核融合, 使得最终得到的核矩阵更加地鲁棒. 在国际公开场景文字识别数据集Chars74k和ICDAR03-CH上的实验结果表明, 本方法取得了高于国际上已发表的其他方法的单字识别率.     

一种图的st编号路径长度算法

通过对无向图的顶点标注st-编号,可以使它转换为一个有向图,根据有向图的方向可计算出从源点到汇点的路径长度.用DFS算法可计算出st-编号,但一个图有多种不同的st-编号方法,不能确定图的最长路径或者最短路径.使用移除法,连续移除根据时间戳选择出来的顶点,计算出图的st-编号,能够确定图的最长路径或者最短路径.st-编号路径长度在计算网络动态路由、计算最少着色数、减少框图高度等问题上有广泛的应用.     

如何判断有向图的连通性？

(一)问题 2000年第24期擂台赛的问题是有向图的连通性判断。 对一个有向图,忽略所有有向边的方向性而得到对应的一个无向图,如果该无向图是连通的,即其中任意两点有通路相连,则称原有向图是弱连通的:如果在原有向图中任意两点间至少有一点至另一点的通路,则称该图是单向连通的:而如果原图任两点之间一定既有甲至乙,也有乙至甲的通路,即有双向通路,则称该图是强连通的。 例如,图1是一个非弱连通非单向连通与非强连通图:图     

基于转化策略的异质超网络表示学习

与传统网络相比,超网络结构更加复杂,并对现有网络表示学习方法提出了很大的挑战。为了克服网络表示学习面临的超网络结构的挑战,提出一种基于转化策略的异质超网络表示学习方法MT2vec。首先,结合团扩展和星型扩展将抽象为超图的异质超网络转换为抽象的2-截图+关联图的异质网络;然后提出一种感知节点语义相关性的元路径游走方法来捕获节点之间的成对关系和元组关系;最后,设计一种结合多层感知器的skip-gram优化模型同时训练节点成对相似性和元组相似性来获得节点表示向量。通过在三个不同类型的超网络数据集上进行实验。结果表明MT2vec算法在链接预测和超网络重建任务中,效果优于其他基线方法。     

带权超网络的度量方法及其性质

超网络是较通常意义上的复杂网络更为复杂的网络,该网络的每一条超边能连接任意多个节点的特性使其比复杂网络能更好地描述真实世界中的复杂系统。针对现有超网络研究中对超网络度量方法的缺陷与不足,提出了一种超网络度量方法——超网络维数（HD）,即为所有超边包含的节点权重之和与对应超边权重乘积和的对数值和节点权重之和与超边权重之和乘积对数值的比值的两倍。超网络维数可以应用于节点权重与超边权重为正实数、负实数、纯虚数,乃至复数等多种不同数值类型的带权超网络中。最后给出了超网络维数的若干性质。     

基于0-1规划的并行计算图划分模型

图划分广泛地应用在许多科学与工程领域,但它应用于并行计算任务分配时,使用无向图表示数据依赖关系,这限制了它的应用(例如,无向图不能表示矩形和非对称依赖关系的应用).为了克服图划分的这个缺点,我们对数据间的依赖关系进行区分(即同一条边区分通信的发送方与接收方),然后基于0-1规划模型化这个问题,并通过互联网上求解优化问题常用的NEOS服务器进行求解,在一些数据集上的实验表明,0-1规划方法优于求解图划分流行的多层划分方法.     

利用邻接结构熵确定超网络关键节点

识别网络中的关键节点对研究网络的拓扑结构及功能特性具有重要的实际应用价值.基于超图的超网络拓扑结构为超图,由于超图中的超边可以包含任意数量的节点,使得超网络能够清晰明了地表达出多元、多维、多准则的复杂关系.为了更好地挖掘超网络中的关键节点,基于超图理论及性质,提出超图中的邻接结构熵识别超网络中的关键节点,该方法通过研究...     

图计算加速架构综述

在大数据时代,图被用于各种领域表示具有复杂联系的数据.图计算应用被广泛用于各种领域,以挖掘图数据中潜在的价值.图计算应用特有的不规则执行行为,引发了不规则负载、密集读改写更新操作、不规则访存和不规则通信等挑战.现有通用架构无法有效地应对上述挑战.为了克服加速图计算应用面临的挑战,大量的图计算硬件加速架构设计被提出.它们为图计算应用定制了专用的计算流水线、访存子系统、存储子系统和通信子系统.得益于这些定制的硬件设计,图计算加速架构相比于传统的通用处理器架构,在性能和能效上均取得了显著的提升.为了让相关的研究学者深入了解图计算硬件加速架构,首先基于计算机的金字塔组织结构,从上到下对现有工作进行分类和总结,并以多个完整架构实例分析应用于不同层次的优化技术之间的关系.接着以图神经网络加速架构的具体案例讨论新兴图计算应用的加速架构设计.最后对该领域的前沿研究方向进行了总结,并放眼于未来探讨图计算加速架构的发展趋势.     

Intelligent fault diagnosis for rolling bearings based on graph shift regularization with directed graphs

Graph shift regularization is a new and effective graph-based semi-supervised classification method, but its performance is closely related to the representation graphs. Since directed graphs can convey more information about the relationship between vertices than undirected graphs, an intelligent method called graph shift regularization with directed graphs (GSR-D) is presented for fault diagnosis of rolling bearings. For greatly improving the diagnosis performance of GSR-D, a directed and weighted k-nearest neighbor graph is first constructed by treating each sample (i.e., each vibration signal segment) as a vertex, in which the similarity between samples is measured by cosine distance instead of the commonly used Euclidean distance, and the edge weights are also defined by cosine distance instead of the commonly used heat kernel. Then, the labels of samples are considered as the graph signals indexed by the vertices of the representation graph. Finally, the states of unlabeled samples are predicted by finding a graph signal that has minimal total variation and satisfies the constraint given by labeled samples as much as possible. Experimental results indicate that GSR-D is better and more stable than the standard convolutional neural network and support vector machine in rolling bearing fault diagnosis, and GSR-D only has two tuning parameters with certain robustness.     

图神经网络推荐研究进展

图神经网络(graph neural network, GNN)具有从图的领域对数据进行特征提取和表示的优势,近年来成为人工智能研究的热点,图神经网络推荐也是推荐系统研究的一个新方向。本文对GNN模型进行深入研究的基础上,分析了GNN推荐过程,并从无向单元图推荐、无向二元图推荐、无向多元图推荐3个方面详细讨论了现有GNN推荐研究取得的主要进展及不足,阐明了现有GNN推荐研究中存在的主要难点,最后提出了GNN上下文推荐、GNN跨领域推荐、GNN群组推荐、GNN推荐的可解释性等未来GNN推荐的研究方向。     

图神经网络在复杂图挖掘上的研究进展

图神经网络对非欧式空间数据建立了深度学习框架,相比传统网络表示学习模型,它对图结构能够实施更加深层的信息聚合操作.近年来,图神经网络完成了向复杂图结构的迁移,诞生了一系列基于复杂图的图神经网络模型.然而,现有综述文章缺乏对复杂图神经网络全面、系统的归纳和总结工作.将复杂图分为异质图、动态图和超图3种类型.将异质图神经网络按照信息聚合方式划分为关系类型感知和元路径感知两大类,在此基础上,分别介绍普通异质图和知识图谱.将动态图神经网络按照处理时序信息的方式划分成基于循环神经网络、基于自编码器以及时空图神经网络三大类.将超图神经网络按照是否将超图展开成成对图划分为展开型和非展开型两大类,进一步按照展开方式将展开型划分成星形展开、团式展开和线形展开3种类型.详细阐述了每种算法的核心思想,比较了不同算法间的优缺点,系统列举了各类复杂图神经网络的关键算法、(交叉)应用领域和常用数据集,并对未来可能的研究方向进行了展望.     

基于复杂结构信息的图神经网络序列推荐算法

图结构因其在序列推荐场景中的自然适应性而备受关注,而现有的基于图神经网络的会话序列推荐算法虽然能够利用图结构信息达到较好的推荐效果,但是没有考虑用户在会话序列中的重复点击行为和项目之间的复杂转换,且未很好地利用图中复杂的结构信息,导致推荐的效果受到一定程度的限制。提出有向与无向信息同注意力相融合的图神经网络序列推荐算法,并基于推荐算法给出项目隐含向量建模算法,结合会话序列图中的有向结构信息与无向结构信息,通过考虑用户的重复点击行为和引入注意力机制建立会话中点击项目的复杂转换模型。图节点在特征传播的过程中平衡邻居节点信息与自身信息的比例,以更准确地预测推荐过程中生成的会话向量。在Diginetica、Yoochoose 1/64、Yoochoose 1/4 3个数据集上的实验结果表明,与SR-GNN、TAGNN算法相比,该算法精度最高提升4.34%,能够更好地预测用户在会话中的下一次点击精度。