复杂异质网络中有效元路径挖掘方法的研究与实现

论文摘要

近年来,数据挖掘领域中关于异质信息网络的研究受到越来越多研究者的关注。由于从现实世界中提取的大多数的图数据是异构的,人们花费更多的注意力在图数据中节点和边的多样性上,因此,异质信息网络上的重要概念――元路径承担着关键的作用。元路径是异质信息网络上的一个包含语义的重要工具,大量的数据处理依赖于有效的元路径。然而,在模式丰富的异质信息网络上,由于点的数量众多,类型繁杂,元路径难以通过人工设计得到。基于以上情形,我们研究了元路径挖掘问题,并提出了高效算法用来解决模式丰富异质信息网络中存在的这个难题。在简单异质信息网络中,本文探索了通过给定节点对生成具有最大相似度元路径的方法。首先,本文提出了一种基于网络模式的短元路径集挖掘算法――生成验证算法。此算法主要分为生成模块与验证模块两个部分,首先通过生成模块列举出所有的短元路径,然后在验证模块中通过路径限制随机游走筛选出具有最高关联度的元路径集。同时为了提高算法效率,本文提出了生成验证算法算法的改进算法,改进算法融合了生成模块和验证模块,在生成元路径的同时验证元路径的相关性,然后根据元路径的相关性又对生成模块进行剪枝,从而极大提高了算法的时间效率。然而在复杂异质信息网络中,网络模式往往过于巨大难以进行元路径挖掘。为了解决网络模式失效这一难题,本文构建了一种新颖的局部网络模式。此结构既有简单异质信息网络中网络模式的高效性和规模小的特点,又最大限度的存储了复杂异质信息网络的网络模式所蕴含的丰富信息。将此新型的数据结构替代复杂异质信息网络上失效的网络模式,极大提升了本文算法的效率。同时,为了应对节点多类型选择问题,本文总结了常用的异质信息网络节点相似性度量方法的缺点,设计了一个新颖的类型评价函数。通过对输入点对集的特殊性和支持度两方面考量,同时综合了前文提出局部网络模式的结构特点,提出了基于类型评分的元路径相似性度量方法。基于上文提出的类型选择方法和元路径相似性度量方法,本文在局部网络模式上设计了快速特殊路径挖掘算法,能从模式丰富的异构信息网络中自动提取有效的元路径。在新型局部网络模式和自动化类型选择的辅助下,问题的时间复杂度大大降低。借助于挖掘的元路径,能够在相似性测度、聚类、分类、链接预测、排名、推荐、信息融合等方面进行更深入的研究。该算法主要包括三部分:第一部分是关于局部层次化图的快速生成过程;第二部分是结合类型选择将生成的多个局部层次化图融合,生成上述新型的局部网络模式;第三部分则是在局部网络模式上的元路径快速挖掘方法。综合这三个过程,就构成了本文的最大相似度元路径挖掘算法。本文通过在Yago数据库和DBpedia数据库上进行大量的实验,对所提出的算法进行了详细评估。在各个知识图谱上的链路预测实验和聚类实验结果表明,此算法相较其他元路径挖掘算法不仅时间效率大大提升,同时精确度也有不同程度的提高。通过实验,可以得出本文算法具有高效与稳定的优点。

论文目录

文章来源

类型: 硕士论文

作者: 孙川

导师: 黄健斌

关键词: 异质信息网络,元路径,网络模式,数据挖掘

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O157.5

DOI: 10.27389/d.cnki.gxadu.2019.001827

总页数: 72

文件大小: 4112K

下载量: 69

相关论文文献

• [1].路径测试中基本路径集自动生成方法的研究[J]. 微电子学与计算机 2013(01)
• [2].一种基于源代码分析的程序变化影响路径集的生成方法[J]. 计算机科学 2015(12)
• [3].基于模型代数的基本路径集的自动生成[J]. 计算机科学 2017(04)
• [4].城市公共交通合理路径集生成研究[J]. 交通科技与经济 2016(03)
• [5].一种改进的测试路径集生成算法[J]. 计算机系统应用 2010(11)
• [6].基于有效路径集合的节点间连通度估计方法研究[J]. 武汉理工大学学报(交通科学与工程版) 2009(05)
• [7].一种基于图深度优先搜索的基本路径集自动生成优化算法[J]. 南华大学学报(自然科学版) 2012(03)
• [8].用于动态交通分配的合理路径集合算法研究[J]. 郑州大学学报(工学版) 2009(02)
• [9].基于影响度的有效路径集合的确定[J]. 交通运输系统工程与信息 2011(06)
• [10].基于备选路径集的在线最短耗时公交换乘方法[J]. 计算机工程与应用 2015(09)
• [11].一种基本路径集求解算法[J]. 计算机应用与软件 2014(11)
• [12].基于交通信息的个性化路径集成规划方法[J]. 华中师范大学学报(自然科学版) 2009(03)
• [13].一种基于FCP的C#变更影响路径集生成方法[J]. 北京信息科技大学学报(自然科学版) 2018(03)
• [14].一种基于无约束边替换的相似路径算法[J]. 信息与电脑(理论版) 2016(11)
• [15].一种基于路段惩罚法的合理路径集生成算法[J]. 公路交通科技 2009(09)
• [16].分支覆盖测试路径集生成系统设计与实现[J]. 计算机应用 2010(S1)
• [17].基本路径测试用例设计的改进方法[J]. 计算机应用与软件 2019(10)
• [18].基于有序路径集的边界表示模型搜索方法[J]. 计算机辅助设计与图形学学报 2011(07)
• [19].基于限制路径集的N-路径随机用户均衡模型构建及性质[J]. 武汉大学学报(工学版) 2019(03)
• [20].一种基于疏散路径集合的路径选择模型在人群疏散仿真中的应用研究[J]. 计算机学报 2018(12)
• [21].煤巷掘进机纠偏路径随机约束环境建模研究[J]. 矿业科学学报 2019(01)
• [22].考虑时空约束的地铁乘客出行路径集生成算法[J]. 同济大学学报(自然科学版) 2015(07)
• [23].基于旅行时间分析的城轨乘客路径集验证方法[J]. 同济大学学报(自然科学版) 2019(01)
• [24].突发中断条件下轨道交通客流疏运路径集模型[J]. 铁道运营技术 2013(04)
• [25].路票交易下的私家车通勤路径选择[J]. 深圳大学学报(理工版) 2018(02)
• [26].无重叠视域中多目标最优路径集合的数据关联[J]. 光电工程 2014(04)
• [27].一种基于稀疏矩阵的求路径集的新算法[J]. 计算机与数字工程 2009(11)
• [28].Java自动化基本路径测试技术研究[J]. 计算机测量与控制 2018(04)
• [29].程序不可达路径的检测方法姚婷[J]. 电脑知识与技术 2018(29)
• [30].寻找图中两顶点间最长路径的算法设计[J]. 电脑编程技巧与维护 2018(07)

标签：异质信息网络论文;  元路径论文;  网络模式论文;  数据挖掘论文;