多关系异构网络上随机游走技术的研究及应用

论文摘要

随着信息技术的发展和多媒体技术的日新月异,各领域实体之间的联系和交互愈加频繁,形成了庞大的网络体系。在图上进行分析和挖掘可以发现许多隐含的知识和信息,例如发现潜在链接进行推荐、发现社团等。因此,基于图的挖掘技术成为广大学者研究的热点。图信息挖掘方面现有大多数研究都是基于同构网络的。然而,现实中网络对象之间交互复杂,实体类型繁多,例如在微博社交网络中,包含用户、博文等实体,实体之间的交互包括关注、评论、转发等行为,这样的复杂网络需要用异构网络来刻画。图挖掘技术的一个重要研究方向就是基于马尔科夫链的随机游走,通过模拟用户在网络中的跳转最终得到网络中每个节点的访问概率,其结果可用于排序、推荐、知识发现等相关研究领域。由于异构网络中存在多种类型的节点和边,使得基于异构网络的随机游走过程的研究更加困难。研究者通过类比同构网络上的随机游走,设计了高阶马尔科夫过程来解决多关系异构网络随机游走的问题(MultiRank)。然而这些方法并没有区分不同类型的关系对随机游走过程的影响,这显然与实际情况不符,得到的结果也存在一定的偏差。因此,本文针对多关系异构网络上的随机游走过程展开调研和研究,以张量为载体,设计了一系列的算法来解决多关系网络随机游走过程这一问题,主要内容如下:(1)通过分析多关系网络实体之间的跳转,使用关系内转移概率和关系间转移概率分别刻画同种关系内实体之间的跳转以及不同关系间的跳转。SemiRank算法通过预先给定先验信息,建立损失函数来计算关系间转移概率,从而约束随机游走者选择何种关系进行游走。实验结果表明本文提出的方法比MultiRank算法效果更好。(2)TRWRank算法结合随机游走过程和监督学习任务,考虑多关系网络结构以及节点和边的属性,设计一个优化问题来获取关系内转移概率和关系间转移概率,使得随机游走者更加倾向于访问重要的节点,从而指导多关系网络的随机游走。实验证明TRWRank算法可以进一步提高结果。(3)ClusterRank算法结合图聚类以及弱关系理论,将多关系网络中的节点进行聚类并计算每种关系中弱关系的比例,从而可以得到不同类型关系的重要度,最后进行多关系网络的随机游走。这种算法不需要提供先验知识,因此比前两种算法具有更广泛的应用空间。实验证明ClusterRank比MultiRank表现更优。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景与意义
•     1.1.1 同构网络与异构网络
•     1.1.2 基于网络的随机游走
•   1.2 国内外研究现状
•     1.2.1 面向同构网络的随机游走
•     1.2.2 面向异构网络的随机游走
•   1.3 问题总结与分析
•   1.4 本文的主要工作
•   1.5 本文的结构组织
• 第二章 相关背景知识介绍
•   2.1 张量（Tensor）
•   2.2 基于张量表示的多关系网络
•   2.3 随机游走模型
•   2.4 本章小结
• 第三章 基于半监督的多关系随机游走SemiRank
•   3.1 SemiRank算法
•   3.2 应用与实验
•     3.2.1 应用背景
•     3.2.2 数据集和数据处理
•     3.2.3 实验参数设置
•     3.2.4 实验结果
•   3.3 本章小结
• 第四章 基于有监督的多关系随机游走TRWRank
•   4.1 TRWRank算法
•     4.1.1 优化问题
•     4.1.2 求解优化问题
•     4.1.3 算法流程
•   4.2 应用与实验
•     4.2.1 实验参数设置
•     4.2.2 实验结果
•   4.3 本章小结
• 第五章 基于无监督的多关系随机游走ClusterRank
•   5.1 ClusterRank算法
•     5.1.1 多关系网络中局部随机游走距离
•     5.1.2 聚类过程
•     5.1.3 参数调整
•     5.1.4 算法流程
•   5.2 应用与实验
•     5.2.1 实验一:关键短语提取
•     5.2.2 实验二:欧洲空中多路传输网络
•   5.3 本章小结
• 第六章 总结与展望
• 参考文献
• 附录1 攻读硕士学位期间撰写的论文
• 附录2 攻读硕士学位期间参加的科研项目
• 致谢

文章来源

类型: 硕士论文

作者: 陈文燕

导师: 李云

关键词: 多关系异构网络,马尔科夫链,随机游走,张量,转移概率

来源: 南京邮电大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 南京邮电大学

分类号: O211.6;O157.5

DOI: 10.27251/d.cnki.gnjdc.2019.000565

总页数: 74

文件大小: 3335K

下载量: 84