异构信息网络中基于元路径的搜索与挖掘
1.3 定义3 元路径
元路径P是定义在网络架构TG?(?,R)的，以A1?A2?...?Al?1，它表示了一个A1到Al?1之间复杂的关系R?R1?R2?...?Rl，其中?是关系的运算符。
对于图1.1中所示的书目网络架构，我们在图1.1b和1.1c列出的图元的路径的两个例子，其中的箭头明确地示出了一个关系的方向。我们说一个在网络G中符合元路径P的路径p=(a1a2...al)，我们称这些为元路径的实例，表示为p?P。路径实例的例子已经
R1R2Rl
图1.1：符合架构的数目网络架构和书目网络实例
- 4 -
异构信息网络中基于元路径的搜索与挖掘
如表1.1所示，在这里我们列出了两个作者和荟萃路径，这些路径实例属于之间的可能路径实例。
除了指出元路径我们感兴趣的是，我们还需要考虑如何量化两个对象之间的连接下一个给定的元路径。通常情况下，我们可以使用的路径数数，随机游走为基础的措施，或PathSim[9]量化元路径，这些措施更多的讨论可以在参考文献 [9,11,12]中找到。类似地，对应于传统的数据集，它可以在许多挖掘任务中可以用在信息网络中基于元路径的 度量。
图1.2 数目网络架构和元路径
表1.1：异构网络中的路径实例和元路径
在接下来的几节中，我们将演示基于元路径的方法如何可以在三个非常关键的挖掘功能，即相似性搜索，关系的预测和聚类中使用。
- 5 -
异构信息网络中基于元路径的搜索与挖掘
2 相似性搜索
在信息网络中的相似性搜索的目的是找到一个给定节点最相似或最邻近的节点。链接在决定节点，如个性化的PageRank [13]和SimRank [14]之间的相似性发挥了显著作用。然而，对于一个异构网络信息时，相似性度量可以根据不同的语义定义。然后，我们建议使用元路径捕获两个对象类型之间的关系类型的不同的语义，并提出了相应的基于元路径的相似性搜索框架。
2.1 基于元路径的相似性搜索架构
相似性搜索在网络的分析中具有重要作用。通过考虑在网络中不同的链路路径（即元路径），可以在异构网络中的信息推导出相似的各种语义。例如，表2.1中，通过使用不同的元路径，可以发现与 一个非常著名的数据挖掘研究员Christos Faloutsos最相似的不同的作者。例如，通过使用作者-论文-作者元路径，我们可以发现Christos Faloutsos的学生或合作者；通过作者-论文-期刊-论文-作者元路径，我们可以找到具有类似的研 究领域的其他的研究人员。
表2.1 不同元路径下最与Christos Faloutsos相似的前十位
- 6 -
异构信息网络中基于元路径的搜索与挖掘
通过以不同的方式定量的元路径，我们可以进一步定义具有不同性质的相似度测量。在文献 [9]中介绍了基于元路径的相似性度量PathSim，与以随机行走为基础的相似度量比较，它在查找对等节点中能够产生更好的结果。文献[15]介绍了另一中度量HeteSim，它计算不同类型的对象之间的相关程度。
2.2 PathSim：寻找相似的节点
虽然有几个类似的度量，如个性化PageRank和SimRank，他们对于要么高度可见的物体或高度集中的对象有效，但无法捕捉同行相似的语义。例如，路径数和随机游走为基础的相似性总是青睐具有比较大的度的对象，基于成对的随机游走的相似性有利于浓缩物，即大部分的链接，进入到物体的一小部分。然而，在许多情况下，在网络中发现类似的对象是要找到类似的同行，如基于各自的领域和声誉发现类似的作者，根据他们的电影风格和生产力发现相似的演员，并根据它们的功能和人气找到同类产品。
这促使我们提出了一个新的，基于元路径的相似性度量，称为PathSim，捕捉同行相似的精妙之处。根据直觉，两个类似的对等对象不应只强连接，而且还分享媲美的知名度。为对等体之间的关系应该是对称的，我们只限于PathSim对称元的路径。这是很容易看到，往返的元路径路径P?(PlPl)总是对称的。
定义4：PathSim：基于元路径的相似性度量 给定一个对称的元路径P，两个相同类型之间的PathSim：s(x,y)?2??px?y:px?y?Px?x:px?x?P?1???p???py?y:py?y?P，其中px?y是x,y
之间的一个实例，px?x是x,y之间的一个实例，py?y是y,y之间的一个实例。
给定一个元路径，这个定义向我们展示了：s（x,y）的一定有两部分：（1）通过路径之间的数量定义的连通性；（2）它们的可见性，其中一个根据P的可见性被定义的平衡。请注意，我们做的算多次出现的路径实例作为路径实例的权重，这是路径实例中的所有链接的权重的乘积。
表2.2列出了三项措施，在数据库和结果信息系统（DBIS）区域，通过元路径路径APVPA（基于他们共同的期刊）查询在数据库领域年轻的研究员Anhai Doan前5最相似的作者。P-PageRank返回最相似的作者他们为高度排列的作者;SimRank返回一组作者，都集中于少数与Anhai Doan具有相同的期刊;而PathSim返回Patel, Deshpande, Yang, and Miller，他们具有非常相似的出版记录，并在数据库中和Anhai Doan一样也是在冉冉升起的新星。显然，在这样的网络中，PathSim捕获了相似的对等节点所需的语义。
- 7 -
异构信息网络中基于元路径的搜索与挖掘
2.3 用户引导的相似性搜索
到目前为止，我们已经看到，不同的元路径意味着不同的相似的语义。但是，如何
才能选择一个特定的搜索任务的最佳元路径或它们的组合？现在，我们介绍了元路径何 可以帮助用户引导的相似性搜索。
如该图2.2所示，不同的用户可能偏好不同的相似性度量，即使对于相同的查询实体。鉴于DBLP网络，它们共享相同的格式的相似性查询可以具有不同的语义含义。在图2.2，无论是查询1和查询10目标是找到与Christos Faloutsos具有相似关系的作者，但是，如果我们用同样的排名函数来回答这两个查询，结果可能不理想。在查询1，隐藏的相似性语义是通过两个例子Jimeng Sun” 和 “Hanghang Tong”。人类的知识判断，作者都是数据挖掘研究人员和卡内基梅隆大学（CMU）Faloutsos的学生。当用户发出查询1，他们可能会寻找卡内基梅隆大学其它的与Faloutsos定期合作的数据挖掘研究人员。然而，在查询1'我们可以从用户的指导，查询很可能寻找其他类似Faloutsos的有名的数据挖掘研究人员。在IMDB（http://www.imdb.com/）数据集，查询2代表搜索有关同一主题（即蝙蝠侠）的电影，同时查询2'代表一个搜索大约在同一时间，在同类型制作的电影。
表2.2 DBIS中和Anhai Doan最相似的前五位
为了提供个性化的相似性搜索，研究文献[10]可满足用户的不同的搜索意图，我们会要求用户提供几个例子，连同查询实体。整个系统可以分为离线和在线组件。在离线的一部分，用不同的基于元路径的排名模式进行培训。在在线部分，查询的意图会被识别和查询将被分派到相应的排序模型。最后选定的相似度排名模式将返回所有其他类似的对象查询实体，给出的查询与指导为例。
- 8 -
相关推荐：
loading