基于距離度量的多樣性圖排序方法

　　有效結(jié)合查詢相關(guān)性和多樣性的擴展相關(guān)性是多樣性圖排序問題的一種優(yōu)化目標．基于擴展相關(guān)性的多樣性圖排序可建模為一個子模函數(shù)優(yōu)化問題，貪心子模優(yōu)化算法可近似求解該問題．然而，擴展相關(guān)性不能直接度量節(jié)點間的不相似性．子模優(yōu)化算法是串行算法不能充分利用諸如Spark等集群計算平臺有效提高算法效率．針對這些問題，本文提出一種描述節(jié)點間不相似性的距離度量．基于此距離度量，將多樣性圖排序問題建模為一個在查詢相關(guān)節(jié)點集上構(gòu)造的帶權(quán)完全圖的最大和K -dispersion優(yōu)化問題，提出了求解該問題的多項式時間2一近似算法，鑒于不同節(jié)點對的距離度量計算是相互獨立的，進一步地提出了基于MapReduce編程模型的并行化多樣性圖排序算法，最后，在真實圖數(shù)據(jù)集上驗證了本文提出算法的高效性和有效性．