异构信息网络中基于元路径的搜索和挖掘(上)

大连理工大学本科外文翻译异构信息网络中基于元路径的搜索和挖掘Meta-Path-BasedSearchandMininginHeterogeneousInformationNetworks学院（系）：软件学院专业：网络工程学生姓名：学号：指导教师：完成日期：2014年4月大连理工大学DalianUniversityofTechnology异构信息网络中基于元路径的搜索与挖掘-1-异构信息网络中基于元路径的搜索和挖掘YizhouSunJiaweiHan波士顿东北大学计算机与信息学院伊利诺伊大学香槟分校计算机学院摘要：最近，从各个领域提取出来的信息网络被广泛的研究，提出和发展了不同的功能挖掘这些网络，如排名，社区检测和链路预测。大多数现有的网络研究是同构网络，其中的节点和链接假设为一个单一类型。然而在现实中，异构信息网络可以更好地模拟真实世界的系统，这是典型的半结构化和类型化，承接网络架构。为了直接开采这些异构信息网络，我们提出探索信息网络的元结构，即网络架构。提出的元路径的概念，系统地捕获在多个类型的对象，通过网络架构的图形的众多语义关系，它们被定义为一个路径。元路径可以为搜索和挖掘网络提供指导，帮助分析和了解网络中的对象和关系的语义。在此框架下，相似性搜索和其他挖掘任务，如关系的预测和集群可以通过网络的元结构的系统的探索加以解决。此外，随着用户的指导和反馈，我们可以为一个特定的挖掘任务选择最好的元路径或它们的加权组合。关键词：异构信息网络；元路径；相似性搜索；关系预测；用户指导引言真实世界的物理和抽象的数据对象是相互关联的，形成一个庞大互连网络。通过这些结构化数据对象和这些对象之间的交互成多种类型，如网络成为半结构化的异构信息网络。用于处理大数据的现实世界的应用，包括相互连接的社交媒体和社交网络，科学，工程或医疗信息系统，在线电子商务系统，和大多数数据库系统，可以被结构化为异构信息网络。不同于对象和链接被看做相同类型或无类型的节点或链路的同构信息网络，在我们的模型中，异构信息网络是半结构化和类型，即节点和链接被构造一组类型，形成了网络架构。例如在像书目数据库DBLP（）和PubMed（），论文通过作者，期刊和条件连在一起。Flickr（），一个社交网络，照片是通过用户，组，标签和评论连接在一起。不同种类的知识都可以从这样一个信息网络视图中导出，如发现集群和层次结构[1-3]，排名[1,3,4]主题分析[5,6]分类[7，8],相似性搜索[9,10],以及关系预测。这些功能有助于在几异构信息网络中基于元路径的搜索与挖掘-2-乎每个行业的无处不在的在线数据库和其他联机或脱机的系统的新知识的产生。例如，不同的研究领域和为作者和会议排序可以通过这样的分析在书目数据库发现，这对用户更好地理解数据，并获得宝贵的知识将是有益的。目前大多数网络的研究都是基于同构网络。为了将同质信息网络为基础的方法适用到异构信息网络，我们必须将异构网络成看出同质的，或者干脆忽略与节点和链路相关的类型信息。不幸的是，这两种方法会导致严重的信息丢失。因此，利用异构节点和链路的语义含义直接提供挖掘方法对异构信息网络来说是有必要的。由于对象通过在异构信息网络不同的语义含义连接，我们建议充分利用异构信息网络的网络架构。网络架构提供了信息网络的元结构，它提供了搜索网络和挖掘的指导和帮助分析和了解网络中的对象和关系的语义。更具体地讲，一个元路径为基础的方法被提出。元的路径是一种定义在在网络的架构的路径，它是两个对象类型之间的关系的序列，并定义对象之间的新的或现有的关系所限定的路径。在这篇文章中，我们介绍了在异构信息网络三种类型的挖掘任务，即相似性搜索，关系的预测和聚类。在文章的最后，我们讨论了一些沿着这个方向发展的研究前沿。1异构信息网络和元路径信息网络表示现实世界的抽象，着眼于对象之间的对象和相互作用。事实证明，这个抽象级别中不仅表示和存储有关的真实世界的基本信息，拥有极大的权力，同时也通过探索链接的作用，提供一个从中挖掘知识的有用工具。在形式上，我们定义了一个信息网络，如下所示。1.1定义1信息网络信息网络被定义为一个有向图，),(VG，与对象类型映射函数:，链接类型映射函数R:，每个对象V属于一个特殊的对象类型)(。每一个链接e属于一个特殊的关系Re)(，并且如果两个链路都属于相同的关系式，两个链路共享相同的起始对象类型以及该结束的对象类型。给定一个复杂的异构信息网络，为更好地理解对象类型和在网络中的链路类型，有必要提供其元层（即，模式级别）描述。因此，我们提出网络架构的概念来描述一个网络的元结构。异构信息网络中基于元路径的搜索与挖掘-3-1.2定义2网络架构网络架构表示为),(RTG的有向图，其中，A是对象的类型，R是关系属性集合，是一个象类型映射函数:，链接类型映射函数R:的异构网络),(VG的元模板。异构信息网络的网络架构指定对象之间的关系的约束集和关系类型化。这些限制使得异构信息网络半结构化，并且引导了网络的语义搜索。符合网络架构的信息网络是调用网络架构的一个网络实例。异构信息网络无处不在现实世界中，我们提供了以下几个例子。（1）书目信息网络：一个数目信息网络网络，比如从DBLP获得的计算机科学书目信息网络，是一个典型的异构网络，包含四种类型的实体对象：文章（P），期刊（V），作者（A），术语（T）。对于每一个文章，它有链接到一组作者，期刊，以及一组术语，属于一组链路类型。它可能还包含一些论文引文信息，那就是，这些论文对于那些引用它的文章有链接。对于这样的书目网络和一个实例网络的网络结构描述示如图1.1。（2）Twitter的信息网络：作为社交媒体的Twitter也可以被看作是一个信息网络，包含的对象类型，例如用户，推特，标签，和关系（或链接）类型，如用户之间，用户和推特之间，推特与推特之间，推特和主题标签之间。（3）Flickr的信息网络：照片共享网站Flickr的可以被看作是一个信息网络，包含了一组对象类型：图像，用户，标签，群组和注释，以及一组关系类型，如用户和图像之间的上传，图像和标签之间的包含关系，图像和组的属于关系，用户和评论之间。（4）医疗卫生信息网络：一个医疗系统可以建模为一个医疗信息网络，包含了一组对象类型，如医生，病人，疾病，治疗和设备，以及一组关系类型，例如用于供治疗和疾病之间，已病人和疾病，病人和医生之间的访问关系。在异构信息网络，对象可以通过不同类型的关系进行连接。在参考文献[9]中，我们建议使用元路径，系统地捕获两个对象类型，它被正式定义如下的关系式。异构信息网络中基于元路径的搜索与挖掘-4-1.3定义3元路径元路径P是定义在网络架构),(RTG的，以AAAlRRRl121...21，它表示了一个1A到1lA之间复杂的关系lRRRR...21，其中是关系的运算符。对于图1.1中所示的书目网络架构，我们在图1.1b和1.1c列出的图元的路径的两个例子，其中的箭头明确地示出了一个关系的方向。我们说一个在网络G中符合元路径P的路径p=(laaa...21)，我们称这些为元路径的实例，表示为Pp。路径实例的例子已经图1.1：符合架构的数目网络架构和书目网络实例异构信息网络中基于元路径的搜索与挖掘-5-如表1.1所示，在这里我们列出了两个作者和荟萃路径，这些路径实例属于之间的可能路径实例。除了指出元路径我们感兴趣的是，我们还需要考虑如何量化两个对象之间的连接下一个给定的元路径。通常情况下，我们可以使用的路径数数，随机游走为基础的措施，或PathSim[9]量化元路径，这些措施更多的讨论可以在参考文献[9,11,12]中找到。类似地，对应于传统的数据集，它可以在许多挖掘任务中可以用在信息网络中基于元路径的度量。图1.2数目网络架构和元路径表1.1：异构网络中的路径实例和元路径在接下来的几节中，我们将演示基于元路径的方法如何可以在三个非常关键的挖掘功能，即相似性搜索，关系的预测和聚类中使用。异构信息网络中基于元路径的搜索与挖掘-6-2相似性搜索在信息网络中的相似性搜索的目的是找到一个给定节点最相似或最邻近的节点。链接在决定节点，如个性化的PageRank[13]和SimRank[14]之间的相似性发挥了显著作用。然而，对于一个异构网络信息时，相似性度量可以根据不同的语义定义。然后，我们建议使用元路径捕获两个对象类型之间的关系类型的不同的语义，并提出了相应的基于元路径的相似性搜索框架。2.1基于元路径的相似性搜索架构相似性搜索在网络的分析中具有重要作用。通过考虑在网络中不同的链路路径（即元路径），可以在异构网络中的信息推导出相似的各种语义。例如，表2.1中，通过使用不同的元路径，可以发现与一个非常著名的数据挖掘研究员ChristosFaloutsos最相似的不同的作者。例如，通过使用作者-论文-作者元路径，我们可以发现ChristosFaloutsos的学生或合作者；通过作者-论文-期刊-论文-作者元路径，我们可以找到具有类似的研究领域的其他的研究人员。表2.1不同元路径下最与ChristosFaloutsos相似的前十位异构信息网络中基于元路径的搜索与挖掘-7-通过以不同的方式定量的元路径，我们可以进一步定义具有不同性质的相似度测量。在文献[9]中介绍了基于元路径的相似性度量PathSim，与以随机行走为基础的相似度量比较，它在查找对等节点中能够产生更好的结果。文献[15]介绍了另一中度量HeteSim，它计算不同类型的对象之间的相关程度。2.2PathSim：寻找相似的节点虽然有几个类似的度量，如个性化PageRank和SimRank，他们对于要么高度可见的物体或高度集中的对象有效，但无法捕捉同行相似的语义。例如，路径数和随机游走为基础的相似性总是青睐具有比较大的度的对象，基于成对的随机游走的相似性有利于浓缩物，即大部分的链接，进入到物体的一小部分。然而，在许多情况下，在网络中发现类似的对象是要找到类似的同行，如基于各自的领域和声誉发现类似的作者，根据他们的电影风格和生产力发现相似的演员，并根据它们的功能和人气找到同类产品。这促使我们提出了一个新的，基于元路径的相似性度量，称为PathSim，捕捉同行相似的精妙之处。根据直觉，两个类似的对等对象不应只强连接，而且还分享媲美的知名度。为对等体之间的关系应该是对称的，我们只限于PathSim对称元的路径。这是很容易看到，往返的元路径路径)(1llPPP总是对称的。定义4：PathSim：基于元路径的相似性度量给定一个对称的元路径P，两个相同类型之间的PathSim：PppPppPppyxsyyyyxxxxyxyx:::2),(，其中yxp是x,y之间的一个实例，xxp是x,y之间的一个实例，yyp是y,y之间的一个实例。给定一个元路径，这个定义向我们展示了：s（x,y）的一定有两部分：（1）通过路径之间的数量定义的连通性；（2）它们的可见性，其中一个根据P的可见性被定义的平衡。请注意，我们做的算多次出现的路径实例作为路径实例的权重，这是路径实例中的所有链接的权重的乘积。表2.2列出了三项措施，在数据库和结果信息系统（DBIS）区域，通过元路径路径APVPA（基于他们共同的期刊）查询在数据库领域年轻的研究员AnhaiDoan前5最相似的作者。P-PageRank返回最相似的作者他们为高度排列的作者;SimRank返回一组作者，都集中于少数与AnhaiDoan具有相同的期刊;而PathSim返回Patel,Deshpande,Yang,andMiller，他们具有非常相似的出版记录，并在数据库中和AnhaiDoan一样也是在冉冉升起的新星。显然，在这样的网络中