异质数据网络的挖掘算法与应用研究

数据网络用节点和属性描述数据对象的特征信息，用边描述对象间的关系信息。例如，Facebook上的所有用户形成了一个社交网络。在这个网络中，每个用户用一个节点表示，它们的一些信息，如姓名、性别、年龄、注册时间等，构成了他们的属性，而用户和用户之间的朋友关系则形成了节点之间的边。这类网络中节点和边的类型单一，通常称其为同质网络。相关学者指出［1，2］ ，目前大多数数据网络分析方法是将网络假设为同质的（即网络中节点和边的类型单一）。虽然同质假设下的网络分析方法取得了一些有影响力的成果（例如PageRank算法［3］），但是，忽略了网络中隐含的重要语义信息［4］ 。

现实世界的网络通常是异质的，异质网络包含了不同类型的节点和边，以描述现实中不同类型的对象和关系。例如，一个生物网络（图9-1）的节点可以包括疾病、药物、副作用、靶点基因等。而网络中的不同路径代表了节点之间的不同关系，诠释了不同的语义信息，在度量对象之间相似性的时候需要考虑这些信息。因为语义不同，在不同路径上返回的数据分析结果是不同的。以药物分析为例，可以是分析具有相同副作用的药物，如可他敏（diphenhydramine）和扑尔敏（chlorpheniramine）都可能引起嗜睡（somnolence）；也可以是分析能够治愈同种疾病的药物，如氨茶碱（aminophylline）和柳丁氨醇（salbutamol）都能治疗哮喘（asthma）。

例如，DBLP是一个文献网站，用来提供计算机领域科学文献的索引服务。如图9-2a所示，其主要包含四类对象，即论文（P）、作者（A）、会议（C）和主题词（T）。不同类型对象之间的关系类型也不同，如作者与论文之间是发表与被发表的关系，会议与论文之间是录用与被录用的关系，论文之间是引用与被引用的关系，等等。作者之间可以通过路径“作者—论文—作者”（APA）或路径“作者—论文—会议—论文—作者”（APCPA）相连，文献［2］将这些路径称为元路径。给定一条路径，可以计算出路径起始类型中不同对象之间的相似度，然后基于该相似度进行各种挖掘分析，如找出最相似的对象对等。不同路径可以得到不同的结果，具体而言，对于路径AP（图9-3a），它代表了作者之间的相似度由作者和论文之间的关系决定，也即两个作者合作的论文；而对于路径APC（图9-3b），它代表了作者之间的相似度由作者和会议之间的关系决定，也即两个作者共同参与的会议。表9-1给出了在这两条路径下的前五对最相似作者。在路径AP下，最相似的作者Divyakant Agrawal和Amr El Abbadi合作了239篇论文，多于次相似的作者Wynne Hsu和Mong-Li Lee（合作了92篇论文）；在路径APC下，无论是Jiawei Han和Hans-Peter Kriegel，还是Jiawei Han和Christos Faloutsos，他们并没有合作过很多文章，然而他们却参加过许多相同的会议，如Jiawei Han和Hans-Peter Kriegel在一些相同的会议上发表了超过110篇的论文^[1]。

图9-1　一个异质生物网络示例

图9-2　文献网络和社会网络示例

图9-3　文献网络中的连接路径示例

表9-1　不同路径下最相似的五对作者

(www.xing528.com)

再如，Flickr是一家提供数字照片存储、分享方案的网络社区平台，它主要包含四类对象，即图片（I）、用户（U）、标签（T）和组（G），以及六种关系，即用户与图片之间上传与被上传的关系、标签与图片之间标注与被标注的关系和组与图片之间包含与属于的关系等，如图9-2b所示。图片之间可以通过路径ITI（图9-4a）或路径ITIGITI（图9-4b）相连，对应的相似度衡量依据是两张图片共享的标签或所在的组。对于第二条路径ITIGITI来说，只要两张图片属于很多相同的组，它们的相似度就很高，而不管它们是否有很多相同的标签。

图9-4　Flickr中的连接路径示例

Jiawei Han、Philip S.Yu等形式化地定义了这种具有多类型、半结构化的异质数据网络模型［1，2，4，5］，开创了异质数据网络挖掘这一新的研究方向，并在这一新视角下，展开了一系列的异质网络挖掘算法研究，包括聚类［6， 7，8］、分类［9，10，11］ 、相似性查询［4，12］、关系影响力分析［13］、异常分析［14，15］等。下面给出异质数据网络的形式化定义：

定义9.1（网络）：给定一个网络模式SG = （Λ， Υ），其中Λ= ｛A｝表示所有类型组成的集合，Υ= ｛R｝表示所有关系组成的集合。一个网络定义为有向图G= （V， E）和上面的两个映射：节点到类型的映射φ： V→Λ和边到关系的映射φ： E→Υ，即，对于图中的每一个节点v∈V，有φ（v） ∈ Λ；对于图中的每一条边e∈ E，有φ（e） ∈ Υ。当节点的类型数或边的关系数大于1，即|Λ|＞1或| Υ |1时，将网络称为异质网络；否则，称为同质网络。＞

图9-1和图9-2给出了三个异质网络的网络模式，使用|A|表示属于某一类型A的节点的个数，即，|A|=| ｛v∈V |φ（v） =A｝ |；使用|R|表示属于某一关系R的边的条数，即，|R|=| ｛e ∈ E| （e）=R｝ |。给定从类型A到类型B的关系R，，则对于R的逆关系R—1，成立。

定义9.2（连接路径）：给定一个异质网络G和相应的网络模式SG=（Λ，Υ），连接路径定义为一条在，即类型A1和类型Al之间的复合关系R=R1 R2…Rl—1上的路径P，其中表示关系之间的复合运算。A1和Al分别称为连接路径P的起始类型和终止类型。P的长度是P中包含的关系数，即l—1。如果任意两种类型之间的关系唯一，那么可以用一个由类型名组成的序列来表示连接路径P，即P=（A1， A2， …， Al）。

连接路径P= （A1 ， A2 ， … ， Al）可以用来寻找类型A1中相似的对象对，对象之间的相似度由类型Al中的连接结果决定。考虑图9-5中的例子，可以用长度为1的连接路径C（化合物）→S（副作用（）简称为CS，C是起始类型，S是终止类型）来描述“化合物引起副作用”这一关系。从而，基于CS的自相似性连接就会返回能引发相似副作用的化合物对。将节点a1和al之间一条具体的路径p = （a1 ， a2 ， … ， al）称为连接路径P = （A1，A2， …， Al）的一个路径实例，其中，对于每个节点ai，有φ（ai） = Ai；同时，每条边ei =（ai ， ai+1）属于P中对应的关系R，可记为p∈P。两条连接路径P1 = （A1 ， A2 ， … ，Al）和P2=（A′1 ， A ′2， … ， A ′k）是可连接的，当且仅当Al = A′1，连接后的结果表示为P=（P1P2），即（A1，A2， …， AlA′2， …， A′k）。一个简单的路径连接示例如图9-5c所示：路径CTF可由路径CT和路径TF连接得到。

图9-5　SLAP中的连接路径示例