检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

面向时序图的周期性三角形枚举算法研究

计算机科学与探索 2023年第8期17卷 1833-1841页

作者：任泽槟李荣华戴永恒王国仁北京理工大学计算机学院北京100081 电科云(北京)科技有限公司北京100041

真实世界中的图通常是时序图,即图中的边具有时间戳。随着图数据挖掘算法和现实需要的发展,时序图的数据挖掘算法开始成为热点问题。其中,周期性是时序数据中一个非常重要的特征。周期性出现的数据通常代表着现实世界中值得关注的行为... 详细信息

真实世界中的图通常是时序图,即图中的边具有时间戳。随着图数据挖掘算法和现实需要的发展,时序图的数据挖掘算法开始成为热点问题。其中,周期性是时序数据中一个非常重要的特征。周期性出现的数据通常代表着现实世界中值得关注的行为模式。在静态图的数据挖掘算法中,三角形枚举是一个基础且重要的问题。基于时序图,提出了一种新的三角形社群模型,周期三角形,并将周期性数据挖掘与图中的三角形枚举算法相结合,提出了一种高效的时序图周期性三角形枚举算法。该算法主要包含三部分:高效的多级剪枝算法,该算法可以在较小的时间代价下删除不在任何周期三角形中的顶点和边;极大周期枚举算法,通过计算极大周期,提出的算法可以避免对时间维度上重叠社群进行重复枚举;边枚举边剪枝的高效的周期三角形枚举算法。实验表明,该算法可以快速枚举出图中的周期性三角形。

关键词：时序图周期性三角形枚举

在线全文

学校读者我要写书评

暂无评论

基于时序图的替补种子节点挖掘算法研究

燕山大学学报 2023年第5期47卷 433-440页

作者：许成伟邹晓红燕山大学信息科学与工程学院河北秦皇岛066004 燕山大学河北省计算机虚拟技术与系统集成重点实验室河北秦皇岛066004

针对时序图中种子节点失效问题,提出了一种可适用于大规模时序网络的替补种子节点挖掘算法。算法分为启发式预选与贪心式终选两个阶段,预选阶段从失效种子节点局部入手,结合时序图中信息传播的时序特性,定义了节点可替换度的概念,并将... 详细信息

针对时序图中种子节点失效问题,提出了一种可适用于大规模时序网络的替补种子节点挖掘算法。算法分为启发式预选与贪心式终选两个阶段,预选阶段从失效种子节点局部入手,结合时序图中信息传播的时序特性,定义了节点可替换度的概念,并将其作为选点依据为失效种子节点构建替补列表。终选阶段通过对替补列表中备选节点进行边际效应计算,进一步筛选出能够使得网络影响力达到全局最优的替补种子节点。实验结果表明本文算法挖掘所得替补种子节点可替代性较高,其影响力在保证对特定区域节点高覆盖率的同时,依旧能够维持较高的网络全局影响力。

关键词：影响力最大化时序图替补种子节点边际效应

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

时序图节点嵌入策略的研究

软件学报 2021年第3期32卷 650-668页

作者：吴安彪袁野马玉亮王国仁东北大学计算机科学与工程学院辽宁沈阳110169 北京理工大学计算机学院北京100081 东北大学工商管理学院辽宁沈阳110169

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上,利用神经网络相关技术,更有效地进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经... 详细信息

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上,利用神经网络相关技术,更有效地进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经典问题上效果显著.虽然研究者们在图嵌入方面已取得了诸多成果,但是面向时序图的节点嵌入问题却未被充分重视.在先前研究工作的基础上,结合信息在时序图中的传播特性,提出一种对时序图节点进行自适应嵌入表达的方法ATGEB(adaptive temporal graph embedding).首先,为了解决不同类型时序图节点活跃程度不同的问题,通过设计一种自适应方式对其活跃时刻进行聚类;而后,在此基础上设计一种游走模型,用以保存节点对之间的时间关系,并将节点游走序列保存在双向多叉树上,进而可以更快速地得到节点时间相关的游走序列;最后,在基于节点游走特性和图拓扑结构的基础上对节点向量进行重要节点采样,以便在尽可能短的时间内训练出满足需求的网络模型.通过充分的实验证明:面向时序图的嵌入策略相较于现流行的嵌入方法,在时序图时序中节点间时序可达性检测以及节点分类等问题上得出了更好的实验效果.

关键词：时序图节点嵌入重要采样时序可达节点分类

基于多属性时序图的动态Skyline路径查询方法研究

在线全文

学校读者我要写书评

暂无评论

基于多属性时序图的动态Skyline路径查询方法研究

作者：张港辽宁大学

学位级别：硕士

近年来,随着互联网的快速发展,关于图数据的研究越来越广泛。路径研究一直是热门话题,对于静态图上的路径查询,已经有许多成熟的算法和数据结构。这些算法可以在静态图上找到最短路径,但是这些算法忽略了时间因素,在应用中非常有限。而... 详细信息

近年来,随着互联网的快速发展,关于图数据的研究越来越广泛。路径研究一直是热门话题,对于静态图上的路径查询,已经有许多成熟的算法和数据结构。这些算法可以在静态图上找到最短路径,但是这些算法忽略了时间因素,在应用中非常有限。而对于时序图上的路径查询,主要涉及到最早到达时间、最短路径和最快时间路径等问题。这方面的研究主要侧重于单约束路径,忽略了多元约束条件的情况,不能满足用户的多样化查询需求。为了解决多元约束最优路径查询问题,学者们提出了Skyline路径查询问题。Skyline路径查询是一种查询多元最优路径的方法,是由Skyline查询拓展而来。Skyline路径查询在基于网络的应用程序中得到了广泛应用,例如交通导航、地图搜索等。然而,目前的Skyline路径查询主要集中在静态图上的多元约束路径查询,没有考虑到时序图上的路径查询。此外,现有的Skyline路径查询方法只能针对可以量化的元素进行查询,无法满足用户的个性化需求。针对上述路径查询中存在的问题和挑战,本文提出了多属性时序图上的Skyline路径查询问题。为了解决这个问题,本文设计了名为Main Point(MP)的索引结构以及基于该索引结构的查询算法。同时,考虑到时序图的动态变化,本文还提出了全局更新的时序图上的Skyline路径查询问题,并利用MP索引的动态更新和基于分区的Skyline路径查询索引来解决该问题。论文的主要研究内容及创新之处如下:(1)为了解决传统路径研究中忽略时间因素以及不能满足用户多样化查询需求问题,本文提出了多属性时序图上的Skyline路径查询问题,该问题考虑了多元约束条件包括时间因素、标签因素,能够满足用户的个性化需求。为了解决该问题,本文首先构建了MP索引结构,它分为Main Point节点选择和Mout集合构建两个阶段。其次,基于MP索引以及双向拓扑结构,本文提出了一种高效的查询算法,用于在多属性时序图上提供Skyline路径查询。(2)针对时序图随时间变化的特点,本文提出了全局更新的时序图上的Skyline路径查询问题。为了解决该问题,本文利用MP索引的动态更新来对最优Skyline路径进行增量计算,并将计算结果加入到滑动窗口进行遍历。同时,还设计了基于分区的Skyline路径查询索引来进行查询。具体来说,本文首先将滑动窗口中的数据进行空间划分,然后进行数据映射,构建支配关系树,最后计算支配关系得到当前滑动窗口中的最优Skyline路径以及影响区域。随着滑动窗口滑动,时序图上的Skyline路径可以实时更新。(3)实验表明本文提出的算法在真实数据集和合成数据集上都表现出了优异的性能,能够更快地响应用户的查询需求,证明了算法的可行性和有效性。

关键词：时序图 Skyline路径多属性索引结构查询算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于时序图的简单环路枚举研究

基于时序图的简单环路枚举研究

作者：陈康广州大学

学位级别：硕士

网络和计算机技术的快速发展使得数据和信息在全球范围内更快流动和传播,也使得用户之间交互形成的时序网络变得愈加庞大,因此也对在时序图下寻找简单环路算法提出了更高的要求。在时序图下进行简单环路枚举问题是图论中一个非常基础且... 详细信息

网络和计算机技术的快速发展使得数据和信息在全球范围内更快流动和传播,也使得用户之间交互形成的时序网络变得愈加庞大,因此也对在时序图下寻找简单环路算法提出了更高的要求。在时序图下进行简单环路枚举问题是图论中一个非常基础且重要的问题,该问题在研究社区发展和金融行业反洗钱问题中发挥着重要作用。本文从研究解决相关问题的算法入手,分析了其优势,并探究其移植到本文问题上的可能性,在指出现有时序图下简单环路枚举算法所存在的痛点的同时,提出了一种充分利用时序图的时间特性来解决该问题的方法。本文基于剪枝的思想去开展研究,主要利用了边候选集索引结构来解决“时序”这一问题,又在其基础上设计了计算反向源点可达性的算法来进行枚举过程中的剪枝,通过两个方法的结合运用高效的解决了该问题。时序图与普通有向图最大的不同点在于时序图中的每一条边都带有时间戳属性,这就导致了两个不同源点之间可能存在更多的交互,形成更多的边,因此进行无效边的过滤对提高算法执行效率至关重要。现有解决算法大都以点为基础进行计算,都存在着过滤效果不强,时间复杂度较高等问题。本文提出了以边为基础进行算法研究的概念,通过约束在一定时间复杂度下的计算建立边的正、反向候选集索引来维护边与边之间的邻居关系,获得符合时序要求的基于边的正、反向邻居集合,从而避免了在枚举过程中进行重复而又无意义的时序条件判断。现有解决该问题的大多数方法都是基于深度优先搜索的,能否在深度优先搜索过程中的增强剪枝能力也是能否提高算法效率的关键,本文受到解决s-t简单路径枚举问题算法的启发,提出了反向计算边的源点可达性与正向进行深度优先搜索的结合算法。第一步在枚举前通过一种变式的广度优先搜索方法,确定每条边是否具有形成正确结果的可能性,来标记其是否具有源点可达性;第二步结合边是否标记为源点可达进行深度优先搜索,整体算法的时间复杂度约束在与结果数量相关,为高效解决该问题提供了理论保证。实验对比了来自真实世界的六个时序图数据集,通过结果对比证明了该算法在解决时序图下简单环路枚举问题上有优异的表现。

关键词：时序图时序路径 s-t简单路径枚举深度优先搜索

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向时序图数据的季节突发性子图挖掘算法

软件学报 2024年

作者：张千桢郭得科赵翔国防科技大学系统工程学院

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,季节突发性子图是在多个时间周期内具有突发性特征的稠密子图,它可以用于社交网络中的活动发现和群体关系分析.然而以前大多数的研究主要集中在识别没有时间信息的网络中的... 详细信息

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,季节突发性子图是在多个时间周期内具有突发性特征的稠密子图,它可以用于社交网络中的活动发现和群体关系分析.然而以前大多数的研究主要集中在识别没有时间信息的网络中的稠密子图.为此,提出一种极大(ω, θ)-稠密子图模型对时序图中的季节突发性子图进行建模.所提模型表示时序图中在至少ω个长度不小于θ的时间段内快速累积密度的子图.为了挖掘出时序图中所有的极大(ω, θ)-稠密子图,将该类挖掘问题转化为一个混合的整数规划问题,包括挖掘最稠密子图和寻找突发值最大化时间段集合两个子问题,并给出有效的解决方案.进一步基于key-核模型和动态规划思想设计两种优化策略来提升算法的性能.实验表明所提模型能够真实地反映现实世界中具有季节突发性的行为模式.同时在5个真实时序网络中验证了所提算法的有效性、效率和可扩展性.

关键词：时序图稠密子图季节突发性子图挖掘时间段

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

基于时序图的作战指挥行为知识表示学习方法

系统工程与电子技术 2020年第11期42卷 2520-2528页

作者：王保魁吴琳胡晓峰贺筱媛郭圣明国防大学研究生院北京100091 国防大学联合作战学院北京100091

为深入探索时序作战指挥行为知识的建模方法,实现对具有时序关联特征的指挥员作战指挥行为的有效表征,以兵棋推演作战指令为基础,提出一种基于时序图的作战指挥行为知识表示学习方法,对作战指挥行为进行知识表示学习,并通过作战指挥行... 详细信息

为深入探索时序作战指挥行为知识的建模方法,实现对具有时序关联特征的指挥员作战指挥行为的有效表征,以兵棋推演作战指令为基础,提出一种基于时序图的作战指挥行为知识表示学习方法,对作战指挥行为进行知识表示学习,并通过作战指挥行为预测任务验证模型的有效性。实验结果表明,提出的方法对于评估指标提升较大,能够有效捕捉想定场景下联合作战指挥员的作战指挥行为时空特征,为时序作战指挥行为知识的表示学习提供了可行范例,为联合作战指挥员的指挥经验抽取和联合作战态势认知提供基础。

关键词：作战指挥行为时序图知识表示学习图嵌入联合作战

在线全文

学校读者我要写书评

暂无评论

基于UML时序图的系统运行时耦合度量方法

计算机工程 2006年第20期32卷 75-77页

作者：杜防汛黄志球杨俊张玉宏南京航空航天大学信息科学与技术学院南京210016

面向对象耦合性是软件质量重要的内部属性,该文分析了现有基于静态分析的耦合度量,以及其因继承和多态的使用而产生对运行时耦合度量的不足。提出了以用于系统动态建模的UML时序图为基础,定义了反映系统运行时的耦合度量指标,并通过实... 详细信息

面向对象耦合性是软件质量重要的内部属性,该文分析了现有基于静态分析的耦合度量,以及其因继承和多态的使用而产生对运行时耦合度量的不足。提出了以用于系统动态建模的UML时序图为基础,定义了反映系统运行时的耦合度量指标,并通过实例验证了耦合指标定义的可操作性和实用性。

关键词：统一建模语言时序图运行时耦合度量

在线全文

学校读者我要写书评

暂无评论

面向大规模时序图SimRank的计算方法

清华大学学报（自然科学版） 2018年第12期58卷 1066-1071页

作者：苗壮袁野乔百友王一舒马玉亮王国仁东北大学计算机科学与工程学院

顶点相似度计算在现实生活中具有广泛的应用。当前对相似性计算的研究工作主要集中于静态图上,并且大多相似性计算模型是基于SimRank算法提出的。而现实中的许多场景,需采用时序图进行建模。当前针对静态图的大量SimRank的计算方法无法... 详细信息

顶点相似度计算在现实生活中具有广泛的应用。当前对相似性计算的研究工作主要集中于静态图上,并且大多相似性计算模型是基于SimRank算法提出的。而现实中的许多场景,需采用时序图进行建模。当前针对静态图的大量SimRank的计算方法无法在时序图中实现,因此该文对大规模时序图中的SimRank计算开展详细研究,并提出一种时序关联的SimRank计算方法(temporal-aware SimRank,TaSimRank)。TaSimRank根据图的拓扑结构和时间约束通过高效的迭代方法计算SimRank。同时,该文提出一种近似算法,通过随机游走方法建立树形索引,使用Monte Carlo方法近似计算顶点的相似度,取得时间和效率的平衡。最后,通过大量真实实验验证了提出算法的有效性和可扩展性。

关键词：时序图相似度随机游走