基于距离度量的多样性图排序方法-李劲 , 岳昆 , 蔡娇 , 张志坚 , 刘惟一.pdf

上善若水

15页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(3):599−613 [doi: 10.13328/j.cnki.jos.005455] http://www.jos.org.cn

基于距离度量的多样性图排序方法

∗

李

劲

1,2

岳

昆

蔡

娇

张志坚

刘惟一

(云南大学软件学院,云南昆明 650091)

(云南省软件工程重点实验室,云南昆明 650091)

(云南大学信息学院,云南昆明 650091)

通讯作者: 岳昆, E-mail: kyue@ynu.edu.cn

摘要: 有效结合查询相关性和多样性的扩展相关性,是多样性图排序问题的一种优化目标.基于扩展相关性的

多样性图排序可建模为一个子模函数优化问题,贪心子模优化算法可近似求解该问题.然而,扩展相关性不能直接度

量节点间的不相似性.子模优化算法是串行算法,不能充分利用诸如 Spark 等集群计算平台有效提高算法效率.针对

这些问题,提出一种描述节点间不相似性的距离度量.基于该距离度量,将多样性图排序问题建模为一个在查询相关

节点集上构造的带权完全图的最大和 k-dispersion 优化问题.提出了求解该问题的多项式时间 2-近似算法.鉴于不同

节点对的距离度量计算是相互独立的,进一步提出了基于 MapReduce 编程模型的并行化多样性图排序算法.最后,

在真实图数据集上验证了所提出算法的高效性和有效性.

关键词: 图数据;个性化 PageRank;多样性图排序;最大和 k-dispersion;MapReduce

中图法分类号: TP311

中文引用格式: 李劲,岳昆,蔡娇,张志坚,刘惟一.基于距离度量的多样性图排序方法.软件学报,2018,29(3):599−613. http://

www.jos.org .cn/1000-9825/5455 .htm

英文引用格式: Li J, Yue K, Cai J, Zhang ZJ, Liu WY. Distance metric based diversified ranking on large graphs. Ruan Jian Xue

Bao/Journal of Software, 2018 ,29(3):599−613 (in Chinese). http://www.jos.org.cn/1000-9825/5455.htm

Distance Metric Ba sed Diversi fied Ranki ng on Lar ge Grap hs

LI Jin

1,2

, YUE Kun

, CAI Jiao

, ZHANG Zhi-Jian

, LIU Wei-Yi

(School of Software, Yunnan University, Kun ming 650091, Ch ina)

(Key Laboratory of Software Engineering of Yunnan Pro vince, Kunming 650091, China)

(School of Information Science and Engineering, Yunnan Univ ersity, Kunming 650091, Chin a)

Abstra ct : Expansion relevance which combines both relevance and diversity into a single function is resorted to a submodular

optimization objective that can be solved by applying the classic cardinality constrained monotone submodular maximization. Howev er,

expansion relevance do not directly capture th e dis-similarity over a pair of nodes. Existing su bmodular algorithms are sequential and not

easy to take full advantage of the power of distributed cluster computing platform, such as Spark, to significantly improve the efficiency

∗ 基金项目: 国家自然科学基金(61562091, 61472345); 第二批“云岭学者”培养项目(C6153001); 云南省应用基础研究计划

(2014FA023, 2016FB110); 云南大学中青年骨干教师培养计划项目; 云南大学青年英才培育计划(WX173602); 云南大学数据驱动

的软件工程科技创新团队项目(2017HC012)

Foundation item: National Natural Science Foundation of China (61562091, 61472345); Program for the Second Batch of Yunling

Scholar of Yunnan Province (C6153001); Natural Science Foundation of Yunnan Province (2014FA023, 2016FB110); Foundation of

Backbone Teacher Development of Yunnan University (WX173602); Program for Excellent Young Talents of Yunnan University

(XT412003); Project of Data Driven Software Engineeringinnovation Team of Yunnan University, Yunnan Province (2017HC012)

本文由基于图结构的大数据分析与管理技术专刊特约编辑林学民教授、杜小勇教授、李翠平教授推荐.

收稿时间: 2017-08-02; 修改时间: 2017-09-05; 采用时间: 2017-11-07; jos 在线出版时间: 2017-12-05

CNKI 网络优先出版: 2017-12-06 16:36:55, http://kns.cnki.net/kcms/d etail/11.2560.TP.20171206.1636.031.html

600

Journal of Software 软件学报 Vol.29, No.3, March 2018

of algorithm. To tackle this issue, in this paper, a distance metric, which is defined by a sum function of personalized PageRank scores

over the symmetry difference of neighbors of a pair of nodes, is first introduced to capture the pairwise dis-si milarity over pairs of nodes .

Then, the problem of diversified ranking on graphs is formulated as a max-sum k-dispersion problem with metrical edge weight. A

polynomial time 2-approximate algorithm is proposed to solve the problem. Considering the computational independence of different

pairs of nodes, a MapReduce algorithm is further developed to boost the efficiency of the process. Finally, extensive experiments are

conducted on real network d atasets to verify th e effectiveness and efficiency of the proposed algorith m.

Key words: graph data; personalized PageRank; div ersified graph r anking; max-sum k-dispersion; MapReduce

当前,各种在线社交网络应用的快速发展累积了大量的图数据.图数据由节点和边组成,且节点之间往往存

在复杂的连接关系,通常缺少显式的全序结构,使得图排序(graph rankin g)成为图数据挖掘、分析的重要手段

[1]

PageRank

[2]

是图中节点重要性度量的常用方法,其基本思想是:节点重要性由其邻接节点重要性决定,被重

要节点连接的节点,重要性越高.一般来说,PageRank 值度量了图中节点的全局重要性或权威度,但 PageRank 值

却不能很好地度量图上节点间的相似性.为此,研究者进一步提出了个性化 PageRank(personalized PageRank,简

称 PPR)

[3]

.但如文献[4, 5]指出:在使用 PPR 方法进行相似性查询时,其返回的 top-k 结果只考虑查询相关性

(relevance) 而忽略了多样性(diver sity). 然而在实际图排序应用环境中,用户的查询意图很难准确描述,往往具有

不确定性、模糊性以及多义性.因此,PPR 方法仍不能很好地满足图排序应用的要求.

当用户真实的查询意图难以准确获取时,对查询结果进行多样性处理,是信息检索系统解决此难题的有效

方法

[6]

.为提供高质量的查询结果,提高用户查询的满意度,提出能够有效折中相关性和多样性的图排序算法,是

图数据挖掘、分析领域面临的研究挑战.为此,近年来许多学者提出了一系列的多样性图排序方法

[4,5,7−10]

目前,已有的多样性图排序方法主要分为以下两类.

(1) 基于优化的方法

[7−9]

这一类方法通过建立目标函数来刻画相关性和多样性,并将问题建模为该目标函数的优化问题,进而提出

相应的优化算法.代表性工作有:Tong 等人

[7]

提出一个目标函数,可以在考虑节点中心度和多样性的条件下综合

评价集合的质量,但是该目标函数没有考虑图数据固有的拓扑结构特征,不能很好地解决多样性图排序的评价

问题.Li 等人

[8]

将多样性图排序建模为一个双目标优化问题,其中,用排序结果集的 PPR 值之和作为相关性度量,

并提出扩展率(expansion ratio )来度量排序结果的多样性.Kucukt unc 等人

[9]

改进了文献[8]的工作,将相关性和扩

展率进行融合,进一步提出了扩展相关性(expansion relevance)来度量排序结果的多样性.上述方法多样性度量

指标不尽相同,但最终的目标函数均证明为非负、单调的子模函数(submodular function).因此,虽然多样性图排

序问题是 NP-hard 的,但采用贪心算法可在多项式时间近似求解该问题;

(2) 基于随机游动的方法

[4,5,10]

随机游动是度量图上节点重要性的有效方法,然而常规的随机游动方法未考虑节点之间的连接关系,因此

排序结果多样性差.为此,相关学者提出了改进的随机游动方法来增强排序结果的多样性.代表性的研究工作有

DivRank

[4]

、GSparse

[5]

、GrassHopper

[10]

.这类方法在随机游动过程中充分考虑了节点间的连接关系,通过引入

节点间的竞争机制,让彼此相连的节点相互竞争,实现排序结果的多样性.然而,这类方法要么计算效率低,难以

适用于大规模网络,要么缺少明确的优化目标,不具备可解释性

[1]

综上,面对大规模图数据的多样性图排序工作,在优化目标、计算效率方面仍存在研究挑战.具体地:

首先,多样性度量指标是多样性图排序建模的核心问题.文献[8]提出了扩展率度量多样性,文献[9 ] 将相关

性和多样性进行融合,进一步提出扩展相关性.实际上,扩展相关性就是一种以节点 PPR 值为权重的带权扩展

率.采用扩展率或者扩展相关性对多样性进行建模的基本思想是:任意两个节点的共同邻居越少,两个节点越不

相似.节点集中,节点间不相似程度越高,则节点集的扩展率或者扩展相似性越大.然而,扩展率和扩展相关性的

定义并非直接基于结点间的不相似性来描述节点集的多样性.换言之,具有高扩展率或高扩展相关性的节点集,

其内部节点间的不相似性未必高.

下面举例说明此问题.先给出扩展率的形式化描述

[8]

.令 G=〈V,E〉是一个图,其中,V 是节点集,E 边集.令 S⊆V

of 15

免费下载

软件学报计算机技术

关注

评论