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

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