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

来源：软件学报杂志2018年第3期北京时间：

作者：李劲,岳昆,蔡娇,张志坚,刘惟一

单位：李劲，云南大学 软件学院, 云南 昆明 650091;云南省软件工程重点实验室, 云南 昆明 65009111,岳昆，云南大学 信息学院, 云南 昆明 65009102,蔡娇，云南大学 软件学院, 云南 昆明 65009103,张志坚，云南大学 信息学院, 云南 昆明 65009104,刘惟一，云南大学 信息学院, 云南 昆明 65009105

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

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

基金资助：国家自然科学基金（61562091，61472345）；第二批"云岭学者"培养项目（C6153001）；云南省应用基础研究计划（2014FA023，2016FB110）；云南大学中青年骨干教师培养计划项目；云南大学青年英才培育计划（WX173602）；云南大学数据驱动的软件工程科技创新团队项目（2017HC012）