第一章 绪论
1.1研究背景与意义
现实世界中，广泛存在人与人之间的交流、信息之间的传递、各种实体之间的交互，例如移动网络中手机间的通信、社交网络中用户之间的各种交互、疫情控制中疾病在人群中的传播等。这些对象、活动和行为之间的联系形成了庞大的网络体系。应用数学建模的方法，将现实生活中的实体对象表示为点，将实体之间的联系表示为边，就构成了网络，也可以称之为图[1]。随着信息技术和网络媒体的发展，各种应用领域的信息呈现爆炸式的增长，现实应用中积累了大量的图数据并且蕴含了海量的信息。例如，全球最大的社交平台 Facebook，每个用户在 Facebook 上分享动态、关注朋友，与周围的亲朋好友互动，形成了一个庞大的社交网络。截止 2009 年 9 月，Facebook 社交网络已有 3 亿多个节点。DBLP 作为一个计算机领域英文文献和著作管理数据库系统，存储了全球计算机领域不同方向所有发表的文献、作者、日期等信息，这些信息构成了一个庞大的合著者网络，可以用来反映作者之间的合作关系、文献之间的引用关系等。
通过挖掘图数据研究网络中实体对象之间的联系和交互，可以帮助我们发现网络中隐藏的联系和特征，促进信息发现和知识学习，因此，越来越多的研究者开始关注图数据的学习和研究。例如，在 Facebook 社交网络中，研究者们通过挖掘人与人之间的各种交互关系，可以发现潜在的社团（社团发现[2][3]）、对用户进行新关系推荐（链接预测[4]）等。此外，网络信息挖掘也有助于网络分析[5]、链接挖掘[6]、超文本和网络挖掘[7]、网络科学[8]以及图挖掘[9]等领域的研究。
1.1.1 同构网络与异构网络
在诸如图 1.1 所示的同构网络中，由于节点和边的类型单一，包含的信息较少，因此便于理解和建模。在网络信息挖掘方面，现有大多数研究都是基于同构网络的，例如基于社交网络进行社团发现[10]、预测未来可能出现的链接[4]、衡量影响力传播[11][12]等。
........................
1.2国内外研究现状
随着 PageRank 算法[23]的提出以及成功应用，基于网络的随机游走技术的研究引起了广泛的注意。根据网络类型的不同，可以分为两大类：（1）面向同构网络的随机游走技术的研究；（2）面向异构网络随机游走技术的研究。接下来分别就这两类方法进行介绍。
.........................
第二章 相关背景知识介绍
2.1张量（Tensor）
张量是一个多维的数据存储格式。数据的维数被称为张量的阶数，也可以称之为模式（Mode）。从张量的角度来讲，一维的向量也可以称为一阶张量，二维的矩阵也可以称之为二阶张量，如图 2.1 所示。文献[51]给出了张量的具体定义：
...........................
2.2 随机游走模型
随机游走模型描述的是自然界中实体以未知的方向和未知的速度运动这一现象。网络上节点之间通过边连接表现出节点之间的相互联系，并且这种联系具有传递性。例如在社交网络中，A 和 B 是朋友关系，B 和 C 也是朋友关系，那么 A 跟 C 之间会产生某些联系。基于网络研究随机游走模型可以发现这些潜在的联系，并且可以发现更多的信息。
..............................
1.1研究背景与意义
现实世界中，广泛存在人与人之间的交流、信息之间的传递、各种实体之间的交互，例如移动网络中手机间的通信、社交网络中用户之间的各种交互、疫情控制中疾病在人群中的传播等。这些对象、活动和行为之间的联系形成了庞大的网络体系。应用数学建模的方法，将现实生活中的实体对象表示为点，将实体之间的联系表示为边，就构成了网络，也可以称之为图[1]。随着信息技术和网络媒体的发展，各种应用领域的信息呈现爆炸式的增长，现实应用中积累了大量的图数据并且蕴含了海量的信息。例如，全球最大的社交平台 Facebook，每个用户在 Facebook 上分享动态、关注朋友，与周围的亲朋好友互动，形成了一个庞大的社交网络。截止 2009 年 9 月，Facebook 社交网络已有 3 亿多个节点。DBLP 作为一个计算机领域英文文献和著作管理数据库系统，存储了全球计算机领域不同方向所有发表的文献、作者、日期等信息，这些信息构成了一个庞大的合著者网络，可以用来反映作者之间的合作关系、文献之间的引用关系等。
通过挖掘图数据研究网络中实体对象之间的联系和交互，可以帮助我们发现网络中隐藏的联系和特征，促进信息发现和知识学习，因此，越来越多的研究者开始关注图数据的学习和研究。例如，在 Facebook 社交网络中，研究者们通过挖掘人与人之间的各种交互关系，可以发现潜在的社团（社团发现[2][3]）、对用户进行新关系推荐（链接预测[4]）等。此外，网络信息挖掘也有助于网络分析[5]、链接挖掘[6]、超文本和网络挖掘[7]、网络科学[8]以及图挖掘[9]等领域的研究。
1.1.1 同构网络与异构网络
在诸如图 1.1 所示的同构网络中，由于节点和边的类型单一，包含的信息较少，因此便于理解和建模。在网络信息挖掘方面，现有大多数研究都是基于同构网络的，例如基于社交网络进行社团发现[10]、预测未来可能出现的链接[4]、衡量影响力传播[11][12]等。
........................
1.2国内外研究现状
随着 PageRank 算法[23]的提出以及成功应用，基于网络的随机游走技术的研究引起了广泛的注意。根据网络类型的不同，可以分为两大类：（1）面向同构网络的随机游走技术的研究；（2）面向异构网络随机游走技术的研究。接下来分别就这两类方法进行介绍。
.........................
第二章 相关背景知识介绍
2.1张量（Tensor）
张量是一个多维的数据存储格式。数据的维数被称为张量的阶数，也可以称之为模式（Mode）。从张量的角度来讲，一维的向量也可以称为一阶张量，二维的矩阵也可以称之为二阶张量，如图 2.1 所示。文献[51]给出了张量的具体定义：
...........................
2.2 随机游走模型
随机游走模型描述的是自然界中实体以未知的方向和未知的速度运动这一现象。网络上节点之间通过边连接表现出节点之间的相互联系，并且这种联系具有传递性。例如在社交网络中，A 和 B 是朋友关系，B 和 C 也是朋友关系，那么 A 跟 C 之间会产生某些联系。基于网络研究随机游走模型可以发现这些潜在的联系，并且可以发现更多的信息。
在如图 2.6 的同构网络上的随机游走中，假设当前一个随机游走者（Random Surfer）处于节点 a1 的位置，由于 a1 只有一条出链指向 a2，因此接下来随机游走者将走向 a2 节点；a2节点有两条出链分别指向 a4 和 a3，那么接下来随机游走者将以同等的概率走向 a4 节点或者a3 节点。以此类推，随机游走者每一次所处的位置只与上一次的位置有关，并且在经过有限次的游走之后总能回到原点。
..............................
第三章 基于半监督的多关系随机游走 SemiRank ................................... 19
3.1SemiRank 算法 ............................... 19
3.2应用与实验 .............................. 23
第四章 基于有监督的多关系随机游走 TRWRank ................................... 33
4.1TRWRank 算法 ................................ 33
4.1.1 优化问题 ................................ 34
4.1.2 求解优化问题 ..................................... 35
第五章 基于无监督的多关系随机游走 ClusterRank .................................. 47
5.1ClusterRank 算法 ................................ 47
5.1.1 多关系网络中局部随机游走距离................................... 49
5.1.2 聚类过程 ............................... 49
第五章 基于无监督的多关系随机游走 ClusterRank
5.1 ClusterRank 算法
在现实生活的网络中，根据网络中对象之间的各种关系，可以将网络中的对象划分为各种彼此之间关系密切的团体，如图 5.1 所示。例如在社交网络中，团体内的对象链接紧密，团体间的对象链接稀疏。通过图聚类的方法可以将图划分为若干个内部链接紧密的团体/簇（Cluster）。
.............................
第六章 总结与展望
随着社交网络和多媒体技术的发展，对于网络的挖掘技术的研究吸引了广大研究者的注意。从网络数据中进行挖掘和研究，可以发现很多有用的信息。而在这些众多的技术中，基于网络的随机游走是一个十分有意义的方向。通过对网络上的随机游走过程的研究，研究者提出了 PageRank 并且在 Google 搜索中取得了成功的应用，开启了网络搜索的新纪元，也表明了网络上随机游走过程研究的有效性和必要性。对于网络随机游走技术的研究大多数集中于同构网络。然而，随着网络的快速发展，出现了更加复杂的异构网络。研究者基于 PageRank进行改进，提出了 MultiRank 算法以及后来的一些改进的算法来模拟多关系异构网络上的随机游走过程，将低维的马尔科夫随机游走的过程类比到高维空间来解决多关系异构网络中随机游走的问题。但是这些方法将所有类型的关系一视同仁，没有考虑到不同类型的关系对随机游走过程的影响程度不同，这显然不合理。
本文通过研究多关系异构网络中不同类型关系对网络中随机游走过程的影响，以张量为载体对多关系网络上的随机游走过程进行研究。本文的主要工作总结如下：
（1）通过学习和总结张量的相关知识，使用张量为载体来表征多关系网络。在多关系网络的随机游走的过程中使用张量来进行计算。
（2）针对多关系网络随机游走过程中多种类型关系对游走过程的影响，设计了一种半监督的方法 SemiRank 指导随机游走者在游走的过程中选择哪种关系进行跳转。通过已知的重要节点集，引入损失函数来衡量关系的重要度，从而得到更加准确的随机游走的结果。
（3）结合多关系异构网络中节点的属性和边的属性，提出了一种监督学习的方法TRWRank，通过设计一个优化问题来对多关系网络的随机游走过程进行偏移，使得随机游走者在游走过程更加倾向于访问重要的节点，避免了每种关系都赋予同样重要度。实验证明我们提出的 TRWRank 方法可以取得更好的随机游走的结果。
（4）此外，由于前面两种方法都需要预先提供一定的训练数据，我们提出了一种无监督的多关系网络上的随机游走的方法 ClusterRank。通过对多关系网络中的对象进行聚类，借助强关系和弱关系的概念来区分多种关系的强度，从而指导随机游走者选择何种关系进行转移。
参考文献（略）