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

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