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

• 作者: 刘惟一 岳昆 张志坚 李劲 蔡娇
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 图数据 个性化PageRank 多样性图排序 最大和k-dispersion MapReduce
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 基于图结构的大数据分析与管理技术专刊
• 页码范围: 599-613
• 页数: 15页
• 分类号: TP311
• 字数: 10646字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005455

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惟一	云南大学信息学院	58	425	10.0	17.0
2	岳昆	云南大学信息学院	77	317	10.0	13.0
3	李劲	云南大学软件学院	17	91	5.0	9.0
5	张志坚	云南大学信息学院	2	22	2.0	2.0
6	蔡娇	云南大学软件学院	7	15	1.0	3.0