Scalable Similarity Search for SimRank相似性評價度量

1、Scalable Similarity Search for SimRankScalable Similarity Search for SimRank論文方向：相似度評價算法論文級別：SIGMOD會議，CCF推薦A類基于SimRank模型的可擴展相似性搜索目 錄論文背景簡介SimRank論文主要工作總結(jié)123SimRank什么是SimRank1SimRank 是一種基于圖的拓撲結(jié)構(gòu)信息來衡量任意兩個對象間相似程度兩個對象間相似程度的模型，該模型由 MIT 實驗室的 Glen Jeh 和 Jennifer Widom教授在2002年首先提出。SimRank相似度的核心思想為：如果兩個對象和被其

2、相似的對象所引用（即它們有相似的入鄰邊結(jié)構(gòu)），那么這兩個對象也相似。SimRank模型定義SimRank2SimRank 模型定義兩個頁面的相似度是基于如下遞歸的公式：網(wǎng)頁排名協(xié)同過濾近似查詢網(wǎng)絡(luò)圖聚類SimRankSimRank的應(yīng)用3論文主要工作論文摘要1由Jeh和Widom教授提出的SimRank模型提供了一個很好的相似性指數(shù)，并且已經(jīng)成功應(yīng)用于許多提到的應(yīng)用之中。迄今為止，盡管已經(jīng)提出了很多算法來計算SimRank，但是沒一個算法能夠擴展到一個具有十億數(shù)量級的圖之中來。由此項事實激勵我們考慮以下的SimRank相似性搜索問題：給定一個查詢節(jié)點u，查找對于u來說擁有最高SimRank指數(shù)

3、的前k個節(jié)點v，該指數(shù)可表述為s(u,v)。我們提出了一個高效且可擴展的計算SimRank搜索問題的算法。在十億級別邊的圖中，該算法可以在 幾秒之內(nèi)計算出給定節(jié)點u的的top-20相似性節(jié)點。論文主要工作四大要素2 線性遞歸表達式s(u, v) = euDev +c(Peu)DPev +c2(P2eu)DP2ev + 兩個上界值xy max xew xy |x| |y| SimRank指數(shù)的距離衰減特性 蒙特卡羅模擬論文主要工作SimRank線性遞歸公式變換3論文主要工作top-k相似性搜索算法4預(yù)處理構(gòu)建原圖的二分圖，由蒙特卡羅模擬確定二分圖的邊。第一次篩選出候選節(jié)點。計算兩個相似度界限。查

4、詢由兩個相似度界限剪除冗余節(jié)點。運用適應(yīng)性選樣加速篩選節(jié)點，一次設(shè)置隨機游走的次數(shù)較少，第二次篩選出候選點后進行二次精確計算SimRank值，選出前K個點?？偨Y(jié)論文的創(chuàng)新點 提出SimRank的線性遞歸表達式，結(jié)合蒙特卡羅模擬方法、距離的衰減特性、適應(yīng)性選樣技術(shù)使得搜索的時間復(fù)雜度獨立于圖的規(guī)模，空間復(fù)雜度控制在可接受范圍。 根據(jù)實際需要，進一步簡化算法為top-k相似性搜索，為實際運用提供指導(dǎo)。 由于算法獨立于圖的規(guī)模的特性，方便進行并行計算。使得計算超大規(guī)模的圖的SimRank值成為可能。首次擴展到十億級別的超大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)中來?？偨Y(jié)論文不足之處與其他可行工作 未能建立蒙特卡羅步數(shù)、衰減系數(shù)與精度的關(guān)系的數(shù)學(xué)分析模型 算法的預(yù)處理步驟是建立二分圖，能否找到空間復(fù)雜度更優(yōu)的替代數(shù)據(jù)結(jié)構(gòu)完成篩選點的步驟，這樣就可以擴展到更大的圖 算法的核心是基于線性遞歸表達式的，而論文的實驗數(shù)據(jù)都是大規(guī)模的稀疏圖，若是稠密圖，精度會有較大影響 節(jié)點間的相似度不僅與它們之間的鏈接有關(guān)還與其中的內(nèi)容有關(guān)，當(dāng)把節(jié)點間的內(nèi)容也放進相似度評價后，如何把本文的線性遞歸表達式與內(nèi)容評價融合起來是一個值得研究的問題總結(jié)體會 SimR