SimRank

SimRank 是一種基於圖的拓撲結構信息來衡量任意兩個對象間相似程度的模型，該模型由 MIT 實驗室的 Glen Jeh 和 Jennifer Widom教授在2002年首先提出^[1]。SimRank相似度的核心思想為：如果兩個對象和被其相似的對象所引用（即它們有相似的入鄰邊結構），那麼這兩個對象也相似。近年來已在信息檢索領域引起廣泛關注，成功應用於網頁排名、協同過濾、孤立點檢測、網絡圖聚類、近似查詢處理等。

介紹

結構相似度（Structural Similarity）是一種通過網絡圖的拓撲結構信息（如網頁連結關係）來衡量對象間相似程度的普適模型，它在信息檢索領域裏已有廣泛的應用，如搜尋引擎優化、協同過濾推薦、文檔聚合分類等。2002 年，MIT 實驗室的Glen Jeh和Jennifer Widom教授提出了一種全新的基於網頁連結結構的模型來評估網絡圖中任意兩個對象（結點）之間相似度，即 SimRank 模型^[1].

SimRank 模型定義兩個頁面的相似度是基於如下遞歸的思想：如果指向結點${\displaystyle a}$和指向結點${\displaystyle b}$的結點相似，那麼${\displaystyle a}$和${\displaystyle b}$也認為是相似的。這個遞歸定義的初始條件是：每個結點與它自身最相似。如果用記號${\displaystyle {\mathcal {I}}(a)}$表示所有指向結點${\displaystyle a}$的結點集合（即入鄰點集合），用${\displaystyle s(a,b)}$表示兩個對象間的SimRank相似度，則SimRank的數學定義式可以表示如下：

(1) 當${\displaystyle a=b}$時，${\displaystyle s(a,b)=1}$.

(2) 當${\displaystyle {\mathcal {I}}(a)=\emptyset }$或者${\displaystyle {\mathcal {I}}(b)=\emptyset }$時，${\displaystyle s(a,b)=0}$.

(3) 其他情況下，

${\displaystyle s(a,b)={\frac {C}{\left|{\mathcal {I}}(a)\right|\left|{\mathcal {I}}(b)\right|}}\sum _{i=1}^{\left|{\mathcal {I}}(a)\right|}\sum _{j=1}^{\left|{\mathcal {I}}(b)\right|}s({\mathcal {I}}_{i}(a),{\mathcal {I}}_{j}(b))}$

其中，${\displaystyle 0<C<1}$是一個阻尼係數.

與傳統的文本相似度（Textual Similarity）相比，SimRank 相似度的計算完全基於網絡圖的拓撲結構，其遞歸的定義方式能使SimRank相似度的值捕捉到圖結構的整體信息。此外，SimRank 相似度能比較任意兩個結點間的相似度問題，相比之下Google PageRank只能衡量每個結點的重要性。

矩陣形式

假設 ${\displaystyle \mathbf {S} }$為SimRank相似度矩陣，其元素${\displaystyle [\mathbf {S} ]_{a,b}}$表示相似度值${\displaystyle s(a,b)}$. ${\displaystyle \mathbf {W} }$是一個按列歸一化的圖鄰接矩陣，其元素${\displaystyle [\mathbf {W} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}}$，若存在一條有向邊${\displaystyle a\to b}$；否則為${\displaystyle 0}$. 於是，SimRank方程式可以用矩陣的形式表示如下：

${\displaystyle {\mathbf {S} }=C\cdot (\mathbf {W} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {W} })+(1-C)\cdot {\mathbf {I} },}$

其中，${\displaystyle \mathbf {I} }$是一個單位矩陣.

SimRank計算

由於 SimRank 相似度是${\displaystyle s(a,b)}$是通過遞歸定義的，因此可能依賴於圖中其他結點對的相似度，這給計算網絡圖中結點間的相似度值帶來很大的困難，尤其當整個圖的結點數很多點，SimRank具有很高的時間複雜度。現有的 SimRank 相似度計算方法主要分兩大類：

（1）SimRank 確定性計算

這類方法主要基於不動點迭代來求解 SimRank 的值，其優點是計算精度較高，但時間複雜度相當大。對於一個網絡圖${\displaystyle G=(V,E)}$來說，傳統的直接迭代法^[1]計算所有結點對的相似度需要${\displaystyle O(K{|E|}^{2})}$的時間複雜度和${\displaystyle O({|V|}^{2})}$的內存，其中${\displaystyle K}$為總的迭代次數。文獻^[2]和^[3]是當前計算所有結點對SimRank相似度的最有效算法。

（2）SimRank 隨機算法^[4]

該方法主要基於蒙特卡羅法模擬，將兩結點間 SimRank 的相似度${\displaystyle s(a,b)}$表示為兩個隨機遊走者分別從結點${\displaystyle a}$和${\displaystyle b}$出發到最後相遇的總時間${\displaystyle \tau (a,b)}$的期望函數，即

${\displaystyle {s(a,b)}=\mathbb {E} (C^{\tau (a,b)})}$

這種方法計算每一個結點對的時間和內存複雜度均為${\displaystyle O(|V|)}$，但帶有一定的隨機性，因此精度較低。

其他相關

• PageRank

參考文獻

1. G. Jeh and J. Widom. SimRank: a measure of structural-context similarity. In KDD'02: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543. ACM Press, 2002. 存档副本 (PDF). [2008-10-02]. （原始內容 (PDF)存檔於2008-05-12）.
2. D. Lizorkin, P. Velikhov, M. Grinev and D. Turdakov. Accuracy Estimate and Optimization Techniques for SimRank Computation. In VLDB '08: Proceedings of the 34th International Conference on Very Large Data Bases, pages 422--433. 存档副本 (PDF). [2008-10-25]. （原始內容 (PDF)存檔於2009-04-07）.
3. W. Yu, X. Lin, W. Zhang. Towards Efficient SimRank Computation on Large Networks. In ICDE '13: Proceedings of the 29th IEEE International Conference on Data Engineering, pages 601--612. 存档副本 (PDF). [2014-05-09]. （原始內容 (PDF)存檔於2014-05-12）.
4. D. Fogaras and B. Racz. Scaling link-based similarity search. In WWW '05: Proceedings of the 14th international conference on World Wide Web, pages 641--650, New York, NY, USA, 2005. ACM. [1] （頁面存檔備份，存於互聯網檔案館）