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

有效结合查询相关性和多样性的扩展相关性,是多样性图排序问题的一种优化目标.基于扩展相关性的多样性图排序可建模为一个子模函数优化问题,贪心子模优化算法可近似求解该问题.然而,扩展相关性不能直接度量节点间的不相似性.子模优化算法是串行算法,不能充分利用诸如Spark等集群计算平台有效提高算法效率.针对这些问题,提出一种描述节点间不相似性的距离度量.基于该距离度量,将多样性图排序问题建模为一个在查询相关节点集上构造的带权完全图的最大和k-dispersion优化问题.提出了求解该问题的多项式时间2-近似算法.鉴于不同节点对的距离度量计算是相互独立的,进一步提出了基于MapReduce编程模型的并行化多样性图排序算法.最后,在真实图数据集上验证了所提出算法的高效性和有效性.

多样性图排序的研究现状及展望

排序是信息检索、数据挖掘以及社会网络分析的基础工作之一。在线社交网络和社会媒体的快速发展积累了大量的图数据——由表示实体的节点和表示实体间关系的连边构成。图数据中节点之间连接关系复杂,通常缺少显式的全序结构,使得图排序在图数据分析中显得尤为重要。图排序算法主要包括2大类,面向节点中心度的图排序算法和面向节点集合多样性的图排序算法。与传统的图排序不同,多样性图排序考虑排序和聚类的融合,体现为节点集合对网络整体的覆盖程度。近年来,多样性图排序得到了广泛的关注,取得了一系列研究进展,研究成果成功应用到了搜索结果排序、文档自动摘要、信息推荐系统和影响最大化等诸多场景中。文章评述了多样性图排序的研究现状及主要进展,将现有的多样性图排序方法按照研究思路的不同分为边际效益最大化、竞争随机游走、聚类与排序互增强3类,分别评述了每类方法的优势和不足。最后指出,设计有效的评价指标和标准测试集、克服多样性图排序面临的精度和速度的矛盾等是多样性图排序未来的研究重点。