论文部分内容阅读
随着科学技术的飞速发展，越来越多领域中实体间的相互作用或关联关系可被测量和记录，譬如生物学中蛋白质之间的相互作用、用户在社交网络的通信、互联网各个计算机的连接情况、环保领域水污染扩散过程等。由于这些实体间的相互作用关系可以被表示成一个图，因而在学术界引起了图挖掘研究热潮的兴起。目前研究的热点主要集中在单关系图上，其刻画的是一种实体间的一种作用关系。然而，在现实世界中实体间的相互作用通常较为复杂，具有实体多元性、作用多类型和作用超二元性等特性。譬如在社会化媒体网络中，包含用户、故事、评论等多种实体，作用关系包括好友关系、评论关系、群组关系等，而且群组关系表示的是超过两个用户之间的相互作用。这样的复杂网络需要用多关系图来刻画，即图中包含不同的类型节点和不同类型的边，且一条边可以连接两个上的节点。多关系图挖掘具有重要的意义，其能帮助人们揭示复杂作用系统中有价值的信息。譬如，挖掘多关系图中节点的重要性将有助于互联网链接分析、社交网络核心或枢纽成员的鉴别、微博系统用户影响力的判断等；挖掘学术多关系图中的社区将有助于找到某一特定研究领域中紧密关联的作者、论文、关键词；挖掘生物多关系图中的模块将有助于发现特定生物功能的组织。然而对于这种类型的图，目前的研究结果和挖掘技术还很少。因此，本文针对这种多关系图展开研究，主要考虑节点重要性计算和社区发现问题，并以张量为载体提出了一系列算法来解决这两个问题。本文的主要研究内容和创新包括：1.针对多关系图挖掘理论基础缺乏的问题，提出了张量马尔可夫链模型，通过张量积近似的方法将高阶马尔可夫链极限概率的求解问题转变成张量等式的求解问题，提出了类似幂法的迭代求解算法。从理论上分析了该模型的解的存在性、唯一性以及求解算法的收敛性。并通过实验结果验证了该模型的有效性。该模型是整个论文研究工作的理论基础，其作为主线贯穿整个研究问题。2.针对多关系图中查询无关的节点重要性计算问题，提出了MultiRank算法和HAR算法。这两个算法以张量马尔可夫链模型为基础，将PageRank算法和HITS算法的思想扩展到多关系图上以解决节点重要性计算问题。从理论上分析了MultiRank算法和HAR算法的解的存在性、唯一性以及求解算法收敛性。在DBLP数据上的实验结果表明MultiRank算法和HAR算法能够合理有效的给出节点和关系的重要性。3.针对多关系图中查询相关的节点重要性计算问题，提出了MultiVCRank算法。该算法将张量马尔可夫链模型和带回位的随机游走思想结合起来，巧妙的将查询输入融入马尔可夫链当中。通过理论分析，证明了MultiVCRank算法的解的存在性，并且证明当回位参数满足一定条件时，MultiVCRank算法收敛到唯一解。在TREC文本数据和Corel图像数据上的实验结果表明MultiVCRank算法的检索效果明显优于传统算法。4.针对时序无关多关系图中的社区发现问题，提出了MultiComm算法。面向可表示为多个张量的多关系图，MultiComm算法基于多个张量建立带回位的马尔可夫链，以其极限概率来反映节点之间的相似性，从而逐步将图中节点加入社区中以找到社区结构。理论结果分析表明在一定条件下MultiComm算法结果是唯一的。模拟数据和SIAM/DBLP数据上的实验结果表明MultiComm的社区发现效果优于当前最好算法。5.针对时序相关多关系图中的社区发现问题，提出了MultiFacTV算法。该算法通过在张量分解目标函数中引入TV(totalvariation)项来约束时间维的分解向量，从而保持社区结构的时间特性。理论分析结果表明MultiFacTV算法能够收敛到局部最优解。实验结果表明MultiFacTV的效果优于Multifac算法和EDISA算法，且在拟南芥、酵母和智人生物时序多关系图数据上发现了有意义的生物模块。总体而言，本文紧扣多关系图中节点重要性计算和社区发现两个研究问题，建立张量马尔可夫链模型作为理论基础和贯穿研究内容的主线，提出了MultiRank/HAR算法，MultiVCRank算法，MultiComm算法和MultiFacTV算法。本文的研究将推动多关系图挖掘的进一步发展，并且有望为张量和马尔可夫链的研究带来新方向。