图数据中的链接关系预测技术研究

摘要

人们面对的世界是普遍联系且不断发展的，认识事物的发展变化规律一直是科学研究热点。人们通常采用图的方式对现实世界中的复杂系统进行刻画和描述。在复杂系统中存在不同类型的对象及不同类型的联系，每个对象和联系都蕴含着不同的意义。理解和掌握图数据中隐含的信息是数据挖掘研究领域的一个重要内容。由于各种原因，人们不能完整获得复杂系统中的各种对象及它们之间的链接关系的信息，而是需要根据已知的信息对隐含的链接关系、缺失的链接关系和虚假的链接关系进行分析和判断。因此，链接关系预测可以为我们更好地认识和分析复杂系统。
　　学者们从不同的领域对链接关系预测进行了研究，包括计算机科学方面、物理学方面、社会学方面和生物学等方面，并提出了各种方法，主要基于网络的结构特征、马尔科夫链和机器学习等方法。各种链接关系预测方法的核心是对象之间的相似性度量，学者们提出了多种相似性度量指标从不同角度度量对象的相似度。目前研究较多的基于节点相似性、路径相似性等指标。所以，在图数据中如何利用网络的结构信息和节点的属性信息进行相似性度量是非常重要的，直接关系到链接关系预测的质量。
　　目前，链接关系预测的研究面临两个问题:
　　(1)如何提高相似性度量的准确度。目前的相似性度量方法只考虑共同邻居数量，而忽视了个体的所有邻居数量;而且，仅考虑了结构相似性而忽视了节点属性相似性。这将造成相似性度量准确度不够高。
　　(2)异构网络的链接关系预测问题。传统的链接关系预测模型多用于同构网络，用于异构网络时，普遍存在预测精度不够高的问题。
　　本文针对上述的两个问题，分三部分进行研究，结合从全局相似性和局部相似性，提出了图数据的链接关系预测方法。本文主要的研究内容和成果如下:
　　(1)针对相似性度量问题，本文研究了对象之间相似程度的非对称信息，提出了基于相似要素的相似性度量方法(Similarity Measure based on SimilarityElement，SMSE)。传统的相似性度量方法中认为如果两个节点相似，则相似程度是相同的，仅考虑共同邻居数而忽略了个体邻居数的影响。SMSE方法则考虑了节点个体的邻居数的非对称信息，与传统的相似性度量方法相比，SMSE方法更好地区分了两个节点之间相似程度的不同。实验结果表明，本文SMSE方法提高了相似性度量的准确性，有助于提高基于相似性的链接关系预测准确度。
　　(2)传统的相似性度量方法偏重于网络结构信息而忽视节点属性信息。本文将网络结构的相似信息视为全局相似信息，节点属性的相似信息视为局部相似信息，提出将全局相似性和局部相似性相融合的面向对象的相似性(Object-orientedSimilarity Algorithm，OSA)度量方法。OSA方法融合了结构信息和属性信息，避免了只考虑结构相似信息的度量方法的片面性。实验结果表明，本文提出的OSA方法提高了相似性度量的准确度。
　　(3)针对异构网络的链接关系预测问题，本文借助node2vec的网络表示学习的方法，对异构网络进行邻居节点集合的采样，有效保留了全局信息和局部信息，然后利用基于异构的相似性度量HeteSim方法进行相似性计算，得到网络节点的相似值，构建了异构网络链接关系预测模型(Link Prediction in HeterogeneousNetwork, LPHN)。实验结果表明，本文提出的LPHN方法能够有效降低异构网络相似性计算的复杂度，为异构网络的链接关系预测提供了新的方法。
　　综上所述，本文提出和逐步完善了图数据中的链接关系预测模型，能够提高对象的相似性度量准确度，改善了图数据中的链接关系预测结果。

目录

摘要

第一章 研究背景及意义

1．1 选题的背景及意义

1．2 链接关系预测研究现状

1．3 主要工作和创新点

1．4 论文的组织结构

第二章 链接关系预测相关技术

2．1 网络基本概念

2．1．1 网络表示方法

2．1．2 网络的测度及参数

2．2 相似性度量

2．2．1 结构等价相似性

2．2．2 规则等价相似性

2．3 网络建模

2．3．1 网络的特征表示

2．3．2 网络的建模方法

2．4 链接关系预测的常用方法

2．4．1 节点属性相似性的链接关系预测

2．4．2 结构相似性的链接关系预测

2．4．3 路径相似性的链接关系预测

2．4．4 基于概率模型的链接关系预测

2．4．5 基于似然估计的关系预测

2．5 链接关系预测指标

2．6 链接关系预测的方法比较

第三章 基于相似要素的链接关系预测方法

3．1 引言

3．2 非对称相似系数ASC

3．3 基于非对称信息的相似度量

3．3．1 ASCCN指标

3．3．2 ASCAA指标

3．3．3 ASCRA指标

3．3．4 基于相似要素的链接关系预测

3．4 实验结果与分析

3．4．1 评价指标

3．4．2 实验数据集

3．4．3 实验结果

3．5 小结

第四章 面向对象的链接关系预测方法

4．1 引言

4．2 对象相似性度量方法

4．3 面向对象相似性算法OSA

4．4 实验结果及分析

4．4．1 相似度模拟计算实验

4．4．2 真实数据集

4．4．3 实验结果及分析

4．5 小结

第五章 异构网络的链接关系预测方法

5．1 引言

5．2 异构网络

5．3 链接关系预测模型

5．3．1 学术信息网络构建

5．3．2 异构网络结构特征提取

5．3．3 异构网络相似性度量

5．3．4 异构网络链接关系预测模型

5．4 实验结果及分析

5．4．1 实验数据集

5．4．2 实验结果及分析

5．5 小结

第六章 总结及展望

6．1 本文工作总结

6．2 下一步研究方向

参考文献

攻读博士期间发表的论文及科研活动

声明

致谢