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

大 连 理 工 大 学 本 科 外 文 翻 译

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

Meta-Path-Based Search and Mining in Heterogeneous Information

Networks

学 院（系）： 软件学院 专 业： 网络工程 学 生 姓 名： 学 号： 指 导 教 师： 完 成 日 期： 2014年4月

大连理工大学

Dalian University of Technology

异构信息网络中基于元路径的搜索与挖掘

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

Yizhou Sun Jiawei Han

波士顿东北大学计算机与信息学院 伊利诺伊大学香槟分校计算机学院

摘要：最近，从各个领域提取出来的信息网络被广泛的研究，提出和发展了不同的功能挖掘这些网络，如排名，社区检测和链路预测。大多数现有的网络研究是同构网络，其中的节点和链接假设为一个单一类型。然而在现实中，异构信息网络可以更好地模拟真实世界的系统，这是典型的半结构化和类型化，承接网络架构。为了直接开采这些异构信息网络，我们提出探索信息网络的元结构，即网络架构。提出的元路径的概念，系统地捕获在多个类型的对象，通过网络架构的图形的众多语义关系，它们被定义为一个路径。元路径可以为搜索和挖掘网络提供指导，帮助分析和了解网络中的对象和关系的语义。在此框架下，相似性搜索和其他挖掘任务，如关系的预测和集群可以通过网络的元结构的系统的探索加以解决。此外，随着用户的指导和反馈，我们可以为一个特定的挖掘任务选择最好的元路径或它们的加权组合。

关键词：异构信息网络；元路径；相似性搜索；关系预测；用户指导

引 言

真实世界的物理和抽象的数据对象是相互关联的，形成一个庞大互连网络。通过这些结构化数据对象和这些对象之间的交互成多种类型，如网络成为半结构化的异构信息网络。用于处理大数据的现实世界的应用，包括相互连接的社交媒体和社交网络，科学，工程或医疗信息系统，在线电子商务系统，和大多数数据库系统，可以被结构化为异构信息网络。

不同于对象和链接被看做相同类型或无类型的节点或链路的同构信息网络，在我们的模型中，异构信息网络是半结构化和类型，即节点和链接被构造一组类型，形成了网络架构。

例如在像书目数据库DBLP（http://www.informatik.uni-trier.de/?ley/db/）和PubMed（http://www.ncbi.nlm.nih.gov/pubmed/），论文通过作者，期刊和条件连在一起。Flickr（http://www.flickr.com/），一个社交网络，照片是通过用户，组，标签和评论连接在一起。不同种类的知识都可以从这样一个信息网络视图中导出，如发现集群和层次结构

[1-3]

，排名[1,3,4]主题分析[5,6]分类[7，8],相似性搜索[9,10],以及关系预测。这些功能有助于在几

- 1 -

异构信息网络中基于元路径的搜索与挖掘

乎每个行业的无处不在的在线数据库和其他联机或脱机的系统的新知识的产生。例如，不同的研究领域和为作者和会议排序可以通过这样的分析

在书目数据库发现，这对用户更好地理解数据，并获得宝贵的知识将是有益的。

目前大多数网络的研究都是基于同构网络。为了将同质信息网络为基础的方法适用到异构信息网络，我们必须将异构网络成看出同质的，或者干脆忽略与节点和链路相关的类型信息。不幸的是，这两种方法会导致严重的信息丢失。因此，利用异构节点和链路的语义含义直接提供挖掘方法对异构信息网络来说是有必要的。由于对象通过在异构信息网络不同的语义含义连接，我们建议充分利用异构信息网络的网络架构。网络架构提供了信息网络的元结构，它提供了搜索网络和挖掘的指导和帮助分析和了解网络中的对象和关系的语义。更具体地讲，一个元路径为基础的方法被提出。元的路径是一种定义在在网络的架构的路径， 它是两个对象类型之间的关系的序列，并定义对象之间的新的或现有的关系所限定的路径。

在这篇文章中，我们介绍了在异构信息网络三种类型的挖掘任务，即相似性搜索，关系的预测和聚类。在文章的最后，我们讨论了一些沿着这个方向发展的研究前沿。

1 异构信息网络和元路径

信息网络表示现实世界的抽象，着眼于对象之间的对象和相互作用。事实证明，这个抽象级别中不仅表示和存储有关的真实世界的基本信息，拥有极大的权力，同时也通过探索链接的作用，提供一个从中挖掘知识的有用工具。在形式上，我们定义了一个信息网络，如下所示。

1.1 定义1 信息网络

信息网络被定义为一个有向图，G?(V,?)，与对象类型映射函数?:???，链接类型映射函数?:??R，每个对象??V属于一个特殊的对象类型?(?)??。每一个链接e??属于一个特殊的关系?(e)?R，并且如果两个链路都属于相同的关系式，两个链路共享相同的起始对象类型以及该结束的对象类型。

给定一个复杂的异构信息网络，为更好地理解对象类型和在网络中的链路类型，有必要提供其元层（即，模式级别）描述。因此，我们提出网络架构的概念来描述一个网络的元结构。

- 2 -

异构信息网络中基于元路径的搜索与挖掘

1.2 定义2 网络架构

网络架构表示为TG?(?,R)的有向图，其中，A是对象的类型，R是关系属性集合，是一个象类型映射函数?:???，链接类型映射函数?:??R的异构网络G?(V,?)的元模板。

异构信息网络的网络架构指定对象之间的关系的约束集和关系类型化。这些限制使得异构信息网络半结构化，并且引导了网络的语义搜索。

符合网络架构的信息网络是调用网络架构的一个网络实例。 异构信息网络无处不在现实世界中，我们提供了以下几个例子。

（1）书目信息网络：一个数目信息网络网络，比如从DBLP获得的计算机科学书目信息网络，是一个典型的异构网络，包含四种类型的实体对象：文章（P），期刊（V），作者（A），术语（T）。对于每一个文章，它有链接到一组作者，期刊，以及一组术语，属于一组链路类型。它可能还包含一些论文引文信息，那就是，这些论文对于那些引用它的文章有链接。对于这样的书目网络和一个实例网络的网络结构描述示如图1.1。

（2）Twitter的信息网络：作为社交媒体的Twitter也可以被看作是一个信息网络，包含的对象类型，例如用户，推特，标签，和关系（或链接）类型，如用户之间，用户和推特之间，推特与推特之间，推特和主题标签之间。

（3）Flickr的信息网络：照片共享网站Flickr的可以被看作是一个信息网络，包含了一组对象类型：图像，用户，标签，群组和注释，以及一组关系类型，如用户和图像之间的上传，图像和标签之间的包含关系，图像和组的属于关系，用户和评论之间。

（4）医疗卫生信息网络：一个医疗系统可以建模为一个医疗信息网络，包含了一组对象类型，如医生，病人，疾病，治疗和设备，以及一组关系类型，例如用于供治疗和疾病之间，已病人和疾病，病人和医生之间的访问关系。

在异构信息网络，对象可以通过不同类型的关系进行连接。在参考文献[9]中，我们建议使用元路径，系统地捕获两个对象类型，它被正式定义如下的关系式。

- 3 -