シムランク

フリー百科事典『ウィキペディア』より

SimRankは、シンプルで直感的なグラフ理論モデルに基づく汎用的な類似度尺度です。SimRankは、オブジェクト間の関係性を持つあらゆるドメインに適用でき、オブジェクトが出現する構造的コンテキストの類似度を、他のオブジェクトとの関係性に基づいて測定します。実質的に、SimRankは、「2つのオブジェクトは、類似のオブジェクトによって参照されている場合、類似しているとみなされる」という尺度です。SimRankは広く採用されていますが、さまざまな要因の影響を受ける不合理な類似度スコアを出力する可能性があり、証拠重み係数の導入、^[¹^]、 SimRankによって無視される追加の用語の挿入^[²^]、またはPageRankベースの代替手段の使用など、いくつかの方法で解決できます。^[³^]

導入

多くのアプリケーションでは、オブジェクト間の「類似性」の尺度が必要です。分かりやすい例としては、従来のテキストコーパスやワールドワイドウェブにおける「類似文書検索」クエリが挙げられます。より一般的には、類似性の尺度は、例えばレコメンデーションシステムにおける協調フィルタリングなど、オブジェクトのクラスタリングに使用できます。レコメンデーションシステムでは、「類似」するユーザーやアイテムがユーザーの嗜好に基づいてグループ化されます。

オブジェクトのさまざまな側面を使用して類似性を判断できますが、通常はドメインと、そのドメインでの類似性の適切な定義によって異なります。ドキュメントコーパスでは、一致するテキストが使用される場合があり、協調フィルタリングでは、共通の好みによって類似のユーザーが識別される場合があります。 SimRank は、多くの関心領域で見つかるオブジェクト間の関係を活用する一般的なアプローチです。たとえばWebでは、2 つのページ間にハイパーリンクがある場合、それらのページは関連しています。同様のアプローチは、科学論文とその引用、または相互参照情報を含むその他のドキュメントコーパスに適用できます。レコメンデーションシステムの場合、アイテムに対するユーザーの好みは、ユーザーとアイテムの関係を構成します。このような領域は、ノードがオブジェクトを表し、エッジが関係を表すグラフとして自然にモデル化されます。

SimRankアルゴリズムの背後にある直感は、多くのドメインにおいて、類似のオブジェクトは類似のオブジェクトによって参照されるというものです。より正確には、オブジェクトとがそれぞれオブジェクトとから参照されている場合、およびとが類似しているとみなされます。つまり、オブジェクトはそれ自体と最大限に類似しているということです。^[⁴^] $a$ $b$ $c$ $d$ $c$ $d$

SimRank は構造的コンテキストの類似性のみを決定する汎用アルゴリズムであることに注意することが重要です。SimRank は、オブジェクト間に十分な関連関係があり、少なくとも何らかの類似性の概念を関係性に基づいているあらゆるドメインに適用されます。言うまでもなく、他のドメイン固有の側面の類似性も重要です。これらは、全体的な類似性の尺度として、関係構造的コンテキストの類似性と組み合わせることができます (また、組み合わせるべきです)。たとえば、Web ページの場合、SimRank は従来のテキストの類似性と組み合わせることができます。同じ考え方が科学論文やその他の文書コーパスにも適用されます。推薦システムの場合、アイテム間の既知の類似性 (両方のコンピューター、両方の衣類など) やユーザー間の類似性 (同じ性別、同じ支出レベルなど) が組み込まれている場合があります。この場合も、これらの類似性を、嗜好パターンに基づいて計算された類似性スコアと組み合わせて、全体的な類似性の尺度を生成できます。

基本的なSimRank方程式

有向グラフのノードについて、の入近傍と出近傍の集合をそれぞれと表します。の場合には、個々の入近傍はと表され、の場合には、個々の出近傍はと表されます。 $v$ $I(v)$ $O(v)$ $v$ $I_{i}(v)$ $1\leq i\leq \left|I(v)\right|$ $O_{i}(v)$ $1\leq i\leq \left|O(v)\right|$

オブジェクトとの類似性をで表す。前述の動機に従い、について再帰方程式が書ける。の場合にはがと定義される。そうでない場合、 $a$ $b$ $s(a,b)\in [0,1]$ $s(a,b)$ $a=b$ $s(a,b)$ $1$

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

ここで、はとの間の定数です。ここで少し技術的な問題として、またはは入近傍を持たない場合があります。この場合、との間に類似性を推測する方法がないため、類似性はに設定され、したがって、またはの場合には、上記の式の和はと定義されます。 $C$ $0$ $1$ $a$ $b$ $a$ $b$ $s(a,b)=0$ $0$ $I(a)=\emptyset$ $I(b)=\emptyset$

SimRankの行列表現

との間の任意の定数が与えられたとき、を類似度行列とし、その要素は類似度スコアを表すものとし、を列正規化された隣接行列とし、その要素はからへの辺が存在する場合に、そうでない場合は 0 であるとする。行列表記法を用いると、SimRankは次のように定式化できる。 $C$ $0$ $1$ $\mathbf {S}$ $[\mathbf {S} ]_{a,b}$ $s(a,b)$ $\mathbf {A}$ $[\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}$ $a$ $b$

{\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\mathbf {I} }\},

ここでは単位行列です。 $\mathbf {I}$

SimRankの計算

グラフのSimRank方程式の解は、固定点への反復によって得られます。をのノード数とします。各反復において、エントリを保持できます。ここで、は反復におけるとの間のスコアです。に基づいて、を順に計算します。から開始します。ここで、各は実際のSimRankスコアの下限値です。 $G$ $n$ $G$ $k$ $n^{2}$ $s_{k}(*,*)$ $s_{k}(a,b)$ $a$ $b$ $k$ $s_{k+1}(*,*)$ $s_{k}(*,*)$ $s_{0}(*,*)$ $s_{0}(a,b)$ $s(a,b)$

s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{if }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{if }}a\neq b{\mbox{ }}.\end{cases}}

を計算するには、基本的なSimRank方程式を使用して次の式を取得します。 $s_{k+1}(a,b)$ $s_{k}(*,*)$

s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))

については、についてはとなる。つまり、各反復において、 SimRank基本方程式に従って、前回の反復におけるの近傍点の類似度スコアを用いての類似度を更新する。値はの増加に伴って減少しない。^[⁴^]では、値がSimRank基本方程式を満たす限界、すなわちSimRankスコアに収束することが示された。つまり、すべての、について、となる。 $a\neq b$ $s_{k+1}(a,b)=1$ $a=b$ $k+1$ $(a,b)$ $(a,b)$ $k$ $s_{k}(*,*)$ $k$ $s(*,*)$ $a,b\in V$ $\lim _{k\to \infty }s_{k}(a,b)=s(a,b)$

当初のSimRank提案では、減衰係数と固定の反復回数を選択することが提案されていました。しかし、最近の研究^[⁵^]では、与えられた値と反復計算されたSimRankスコアの精度は一般的に比較的低いことが示されました。より正確な計算結果を保証するために、後者の論文では、より小さな減衰係数（特に）を使用するか、より多くの反復回数を行うことが提案されています。 $C=0.8$ $K=5$ $C$ $K$ $C=0.6$

コシムランク

CoSimRankはSimRankの派生版であり、局所的な定式化も可能という利点があります。つまり、CoSimRankは単一のノードペアに対して計算できます。^{[ 6 ]}を類似度行列とし、その要素は類似度スコアを表します。を列正規化された隣接行列とします。行列表記法では、CoSimRankは次のように定式化されます。 $\mathbf {S}$ $[\mathbf {S} ]_{a,b}$ $s(a,b)$ $\mathbf {A}$

{\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },

ここでは単位行列です。単一のノードペアのみの類似度スコアを計算するには、を標準基底のベクトルとします。つまり、- 番目の要素が 1 で、その他の要素はすべて 0 です。この場合、CoSimRank は次の 2 つのステップで計算されます。 $\mathbf {I}$ $p^{(0)}(i)=e_{i}$ $e_{i}$ $i$

$p^{(k)}=Ap^{(k-1)}$
$s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle$

ステップ1は、Personalized PageRankの簡略版と見ることができます。ステップ2では、各反復におけるベクトル類似度を合計します。行列表現とローカル表現はどちらも同じ類似度スコアを計算します。CoSimRankは、を変更することで、ノードセットの類似度を計算するためにも使用できます。 $p^{(0)}(i)$

SimRankに関するさらなる調査

FogarasとRacz ^{[ 7 ]}は、モンテカルロ法を用いた確率計算によってSimRankの計算を高速化することを提案した。
Antonellisら^{[ 8 ]}は、SimRank方程式を拡張し、(i)インシデントノードの証拠係数と(ii)リンクの重みを考慮に入れた。
Yuら^{[ 9 ]}は、異なる部分和の間で小さな共通部分を共有する細粒度メモ化法を介してSimRank計算をさらに改善しました。
チェン氏とジャイルズ氏はSimRankの限界と適切な使用例について議論した。^{[ 3 ]}

部分和のメモ化

リゾーキンら^{[ 5 ]}は、 SimRankの計算を高速化するための3つの最適化手法を提案した。

必須ノードの選択により、事前スコアがゼロのノードペアの一部の計算が省略される場合があります。
部分和メモ化は、類似度の合計の一部をキャッシュして後で再利用することで、異なるノードペア間の類似度の繰り返し計算を効果的に削減できます。
類似度のしきい値設定により、計算されるノードペアの数をさらに削減できます。

特に、部分和メモ化に関する2つ目の観察結果は、からへのSimRankの計算を大幅に高速化する上で極めて重要な役割を果たします。ここで、は反復回数、はグラフの平均次数、はグラフ内のノード数です。部分和メモ化の中心的な考え方は、以下の2つのステップで構成されています。 ${\mathcal {O}}(Kd^{2}n^{2})$ ${\mathcal {O}}(Kdn^{2})$ $K$ $d$ $n$

まず、部分和は次のように記される。 $I(a)$

{\text{Partial}}_{I(a)}^{s_{k}}(j)=\sum _{i\in I(a)}s_{k}(i,j),\qquad (\forall j\in I(b))

そして、次のように反復的に計算される。 $s_{k+1}(a,b)$ ${\text{Partial}}_{I(a)}^{s_{k}}(j)$

s_{k+1}(a,b)={\frac {C}{|I(a)||I(b)|}}\sum _{j\in I(b)}{\text{Partial}}_{I(a)}^{s_{k}}(j).

したがって、、、の結果は、後で最初の引数として指定された頂点の類似度を計算するときに再利用できます。 ${\text{Partial}}_{I(a)}^{s_{k}}(j)$ $\forall j\in I(b)$ $s_{k+1}(a,*)$ $a$

参照

ページランク

引用

^ I. Antonellis、H. Garcia-Molina、C.-C. Chang. Simrank++: クリックグラフのリンク解析によるクエリ書き換え。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、408-421ページ。 [1]
^ W. Yu, X. Lin, W. Zhang, L. Chang, J. Pei. 「More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks. VLDB '13 : Proceedings of the 39th International Conference on Very Large Data Bases」13～24ページ。 [2]
^ ^a ^b H. Chen、CL Giles「ASCOS++：SimRank問題に対処するための重み付きネットワークの非対称類似度尺度」ACM Transactions on Knowledge Discovery from Data (TKDD) 10.2 2015. [3]
^ ^a ^b G. JehとJ. Widom. SimRank: 構造的コンテキスト類似度の尺度. KDD'02 : Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543. ACM Press , 2002. 「アーカイブコピー」（PDF）。 2008年5月12日にオリジナル（PDF）からアーカイブ。 2008年10月2日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)
^ ^a ^b D. Lizorkin、P. Velikhov、M. Grinev、D. Turdakov. SimRank計算における精度推定と最適化手法。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、422～433ページ。「アーカイブコピー」（PDF）。 2009年4月7日にオリジナル（PDF）からアーカイブ。 2008年10月25日閲覧。 {{cite web}}: CS1 maint: archived copy as title (link)
^ S. RotheとH. Schütze. CoSimRank: 柔軟かつ効率的なグラフ理論的類似度尺度. ACL '14 : 計算言語学協会第52回年次会議議事録（第1巻：長編論文）, 1392-1402ページ. [4]
^ D. FogarasとB. Racz. リンクベース類似検索のスケーリング. WWW '05 : Proceedings of the 14th international conference on World Wide Web, pages 641--650, New York, NY, USA, 2005. ACM . [5]
^ アントネッリス、イオアニス、ヘクター・ガルシア・モリーナ、チ・チャオ・チャン。「Simrank++：クリックグラフのリンク分析によるクエリ書き換え」VLDB Endowment 1.1 論文集 (2008): 408-421. arXiv : 0712.0499
^ W. Yu、X. Lin、W. Zhang. 大規模ネットワークにおける効率的なSimRank計算に向けて. ICDE '13 : Proceedings of the 29th IEEE International Conference on Data Engineering、601--612ページ.「アーカイブコピー」（PDF）。 2014年5月12日時点のオリジナル（PDF）からのアーカイブ。 2014年5月9日閲覧。 {{cite web}}: CS1 maint: archived copy as title (link)

出典

Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (2009-12-01). 「実世界ネットワークにおけるリンクベースの類似度計算のための効率的なアルゴリズム」 . 2009 第9回 IEEE 国際データマイニング会議. pp. 734– 739. doi : 10.1109/ICDM.2009.136 . ISBN 978-1-4244-5242-2. S2CID 9799597 .

SimRankは、シンプルで直感的なグラフ理論モデルに基づく汎用的な類似度尺度です。SimRankは、オブジェクト間の関係性を持つあらゆるドメインに適用でき、オブジェクトが出現する構造的コンテキストの類似性を、他のオブジェクトとの関係性に基づいて測定します。実質的に、SimRankは「2つのオブジェクトは、類似のオブジェクトによって参照されている場合、類似しているとみなされる」という尺度です。SimRankは広く採用されていますが、さまざまな要因の影響を受ける不合理な類似度スコアを出力する可能性があり、証拠重み係数の導入^[1] 、 SimRankでは無視される追加の用語の挿入^[2] 、またはPageRankベースの代替手段の使用など、いくつかの方法で解決できます。^[3]

導入

多くのアプリケーションでは、オブジェクト間の「類似性」の尺度が必要です。分かりやすい例としては、従来のテキストコーパスやワールドワイドウェブにおける「類似文書検索」クエリが挙げられます。より一般的には、類似性の尺度は、例えばレコメンデーションシステムにおける協調フィルタリングなど、オブジェクトのクラスタリングに使用できます。レコメンデーションシステムでは、「類似」するユーザーやアイテムがユーザーの嗜好に基づいてグループ化されます。

オブジェクトのさまざまな側面を使用して類似性を判断できますが、通常はドメインと、そのドメインでの類似性の適切な定義によって異なります。ドキュメントコーパスでは、一致するテキストが使用される場合があり、協調フィルタリングでは、共通の好みによって類似のユーザーが識別される場合があります。 SimRank は、多くの関心領域で見つかるオブジェクト間の関係を活用する一般的なアプローチです。たとえばWebでは、2 つのページ間にハイパーリンクがある場合、それらのページは関連しています。同様のアプローチは、科学論文とその引用、または相互参照情報を含むその他のドキュメントコーパスに適用できます。レコメンデーションシステムの場合、アイテムに対するユーザーの好みは、ユーザーとアイテムの関係を構成します。このような領域は、ノードがオブジェクトを表し、エッジが関係を表すグラフとして自然にモデル化されます。

SimRankアルゴリズムの背後にある直感は、多くのドメインにおいて、類似のオブジェクトは類似のオブジェクトによって参照されるというものです。より正確には、オブジェクトとは、それぞれオブジェクトとから参照されている場合、類似しているとみなされます。また、とは、それ自体が類似しています。基本ケースは、オブジェクトがそれ自体と最大限に類似していることです。^[4] $a$ $b$ $c$ $d$ $c$ $d$

SimRank は構造的コンテキストの類似性のみを決定する汎用アルゴリズムであることに注意することが重要です。SimRank は、オブジェクト間に十分な関連関係があり、少なくとも何らかの類似性の概念を関係性に基づいているあらゆるドメインに適用されます。言うまでもなく、他のドメイン固有の側面の類似性も重要です。これらは、全体的な類似性の尺度として、関係構造的コンテキストの類似性と組み合わせることができます (また、組み合わせるべきです)。たとえば、Web ページの場合、SimRank は従来のテキストの類似性と組み合わせることができます。同じ考え方が科学論文やその他の文書コーパスにも適用されます。推薦システムの場合、アイテム間の既知の類似性 (両方のコンピューター、両方の衣類など) やユーザー間の類似性 (同じ性別、同じ支出レベルなど) が組み込まれている場合があります。この場合も、これらの類似性を、嗜好パターンに基づいて計算された類似性スコアと組み合わせて、全体的な類似性の尺度を生成できます。

基本的なSimRank方程式

有向グラフのノードについて、の入近傍と出近傍の集合をそれぞれと表します。の場合には、個々の入近傍はと表され、の場合には、個々の出近傍はと表されます。 $v$ $I(v)$ $O(v)$ $v$ $I_{i}(v)$ $1\leq i\leq \left|I(v)\right|$ $O_{i}(v)$ $1\leq i\leq \left|O(v)\right|$

オブジェクトとの類似性をで表す。前述の動機に従い、について再帰方程式が書ける。の場合にはがと定義される。そうでない場合、 $a$ $b$ $s(a,b)\in [0,1]$ $s(a,b)$ $a=b$ $s(a,b)$ $1$

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

ここで、はとの間の定数です。ここで少し技術的な問題として、またはは入近傍を持たない場合があります。この場合、との間に類似性を推測する方法がないため、類似性はに設定され、したがって、またはの場合には、上記の式の和はと定義されます。 $C$ $0$ $1$ $a$ $b$ $a$ $b$ $s(a,b)=0$ $0$ $I(a)=\emptyset$ $I(b)=\emptyset$

SimRankの行列表現

との間の任意の定数が与えられたとき、を類似度行列とし、その要素は類似度スコアを表すものとし、を列正規化された隣接行列とし、その要素はからへの辺が存在する場合に、そうでない場合は 0 であるとする。行列表記法を用いると、SimRankは次のように定式化できる。 $C$ $0$ $1$ $\mathbf {S}$ $[\mathbf {S} ]_{a,b}$ $s(a,b)$ $\mathbf {A}$ $[\mathbf {A} ]_{a,b}={\tfrac {1}{|{\mathcal {I}}(b)|}}$ $a$ $b$

{\mathbf {S} }=\max\{C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} }),{\mathbf {I} }\},

ここでは単位行列です。 $\mathbf {I}$

SimRankの計算

グラフのSimRank方程式の解は、固定点への反復によって得られます。をのノード数とします。各反復において、エントリを保持できます。ここで、は反復におけるとの間のスコアです。に基づいて、を順に計算します。から開始します。ここで、各は実際のSimRankスコアの下限値です。 $G$ $n$ $G$ $k$ $n^{2}$ $s_{k}(*,*)$ $s_{k}(a,b)$ $a$ $b$ $k$ $s_{k+1}(*,*)$ $s_{k}(*,*)$ $s_{0}(*,*)$ $s_{0}(a,b)$ $s(a,b)$

s_{0}(a,b)={\begin{cases}1{\mbox{ }},{\mbox{ }}{\mbox{if }}a=b{\mbox{ }},\\0{\mbox{ }},{\mbox{ }}{\mbox{if }}a\neq b{\mbox{ }}.\end{cases}}

を計算するには、基本的なSimRank方程式を使用して次の式を取得します。 $s_{k+1}(a,b)$ $s_{k}(*,*)$

s_{k+1}(a,b)={\frac {C}{\left|I(a)\right|\left|I(b)\right|}}\sum _{i=1}^{\left|I(a)\right|}\sum _{j=1}^{\left|I(b)\right|}s_{k}(I_{i}(a),I_{j}(b))

については、についてはとなる。つまり、各反復において、 SimRank基本方程式に従って、前回の反復におけるの近傍点の類似度スコアを用いての類似度を更新する。値はの増加に伴って減少しない。^[4]では、値がSimRank基本方程式を満たす限界、すなわちSimRankスコアに収束することが示された。つまり、すべての、について、となる。 $a\neq b$ $s_{k+1}(a,b)=1$ $a=b$ $k+1$ $(a,b)$ $(a,b)$ $k$ $s_{k}(*,*)$ $k$ $s(*,*)$ $a,b\in V$ $\lim _{k\to \infty }s_{k}(a,b)=s(a,b)$

当初のSimRank提案では、減衰係数と固定の反復回数を選択することが提案されていました。しかし、最近の研究^[5]では、与えられた値と反復計算によって得られるSimRankスコアの精度は一般的に比較的低いことが示されました。より正確な計算結果を保証するために、後者の論文では、より小さな減衰係数（特に）を使用するか、より多くの反復計算を行うことが提案されています。 $C=0.8$ $K=5$ $C$ $K$ $C=0.6$

コシムランク

CoSimRankはSimRankの派生版であり、局所的な定式化も可能という利点があります。つまり、CoSimRankは単一のノードペアに対して計算できます。^[6]を類似度行列とし、その要素は類似度スコアを表します。を列正規化された隣接行列とします。行列表記法を用いると、CoSimRankは以下のように定式化できます。 $\mathbf {S}$ $[\mathbf {S} ]_{a,b}$ $s(a,b)$ $\mathbf {A}$

{\mathbf {S} }=C\cdot (\mathbf {A} ^{T}\cdot {\mathbf {S} }\cdot {\mathbf {A} })+{\mathbf {I} },

ここでは単位行列です。単一のノードペアのみの類似度スコアを計算するには、を標準基底のベクトルとします。つまり、- 番目の要素が 1 で、その他の要素はすべて 0 です。この場合、CoSimRank は次の 2 つのステップで計算されます。 $\mathbf {I}$ $p^{(0)}(i)=e_{i}$ $e_{i}$ $i$

$p^{(k)}=Ap^{(k-1)}$
$s(i,j)=\sum _{k=0}^{\infty }C^{k}\langle p^{(k)}(i),p^{(k)}(j)\rangle$

ステップ1は、Personalized PageRankの簡略版と見ることができます。ステップ2では、各反復におけるベクトル類似度を合計します。行列表現とローカル表現はどちらも同じ類似度スコアを計算します。CoSimRankは、を変更することで、ノードセットの類似度を計算するためにも使用できます。 $p^{(0)}(i)$

SimRankに関するさらなる調査

FogarasとRacz ^[7]は、モンテカルロ法を用いた確率計算によってSimRankの計算を高速化することを提案した。
Antonellisら^{[8]は、SimRank方程式を拡張し、(i)}インシデントノードの証拠係数と(ii)リンクの重みを考慮に入れた。
Yuら^[9]は、異なる部分和の間で小さな共通部分を共有する細粒度メモ化法を介してSimRank計算をさらに改善しました。
チェン氏とジャイルズ氏はSimRankの限界と適切な使用例について議論した。^[3]

部分和のメモ化

Lizorkinら^[5]はSimRankの計算を高速化するための3つの最適化手法を提案した。

必須ノードの選択により、事前スコアがゼロのノードペアの一部の計算が省略される場合があります。
部分和メモ化は、類似度の合計の一部をキャッシュして後で再利用することで、異なるノードペア間の類似度の繰り返し計算を効果的に削減できます。
類似度のしきい値設定により、計算されるノードペアの数をさらに削減できます。

特に、部分和メモ化に関する2つ目の観察結果は、からへのSimRankの計算を大幅に高速化する上で極めて重要な役割を果たします。ここで、は反復回数、はグラフの平均次数、はグラフ内のノード数です。部分和メモ化の中心的な考え方は、以下の2つのステップで構成されています。 ${\mathcal {O}}(Kd^{2}n^{2})$ ${\mathcal {O}}(Kdn^{2})$ $K$ $d$ $n$

まず、部分和は次のように記される。 $I(a)$

{\text{Partial}}_{I(a)}^{s_{k}}(j)=\sum _{i\in I(a)}s_{k}(i,j),\qquad (\forall j\in I(b))

そして、次のように反復的に計算される。 $s_{k+1}(a,b)$ ${\text{Partial}}_{I(a)}^{s_{k}}(j)$

s_{k+1}(a,b)={\frac {C}{|I(a)||I(b)|}}\sum _{j\in I(b)}{\text{Partial}}_{I(a)}^{s_{k}}(j).

したがって、、、の結果は、後で最初の引数として指定された頂点の類似度を計算するときに再利用できます。 ${\text{Partial}}_{I(a)}^{s_{k}}(j)$ $\forall j\in I(b)$ $s_{k+1}(a,*)$ $a$

参照

ページランク

引用

^ I. Antonellis、H. Garcia-Molina、C.-C. Chang. Simrank++: クリックグラフのリンク解析によるクエリ書き換え。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、408--421ページ。[1]
^ W. Yu, X. Lin, W. Zhang, L. Chang, J. Pei. 「More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks. VLDB '13 : Proceedings of the 39th International Conference on Very Large Data Bases」13～24ページ。[2]
^ ab H. Chen、CL Giles。「ASCOS++：SimRank問題に対処するための重み付きネットワークの非対称類似度尺度」ACM Transactions on Knowledge Discovery from Data (TKDD) 10.2 2015.[3]
^ ab G. JehとJ. Widom. SimRank: 構造的コンテキスト類似度の尺度. KDD'02 : Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543. ACM Press , 2002. 「アーカイブコピー」（PDF）。 2008年5月12日にオリジナル（PDF）からアーカイブ。 2008年10月2日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)
^ ab D. Lizorkin、P. Velikhov、M. Grinev、D. Turdakov. SimRank計算における精度推定と最適化手法。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、422～433ページ。「アーカイブコピー」（PDF）。 2009年4月7日にオリジナル（PDF）からアーカイブ。 2008年10月25日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)
^ S. RotheとH. Schütze. CoSimRank: 柔軟かつ効率的なグラフ理論的類似度尺度. ACL '14 : 計算言語学協会第52回年次会議議事録（第1巻：長編論文）, 1392-1402ページ. [4]
^ D. FogarasとB. Racz. リンクベース類似検索のスケーリング. WWW '05 : Proceedings of the 14th international conference on World Wide Web, pages 641--650, New York, NY, USA, 2005. ACM . [5]
^ アントネッリス、イオアニス、ヘクター・ガルシア・モリーナ、チ・チャオ・チャン。「Simrank++：クリックグラフのリンク分析によるクエリ書き換え」VLDB Endowment 1.1 論文集 (2008): 408-421. arXiv : 0712.0499
^ W. Yu、X. Lin、W. Zhang. 大規模ネットワークにおける効率的なSimRank計算に向けて. ICDE '13: Proceedings of the 29th IEEE International Conference on Data Engineering、601--612ページ. 「アーカイブコピー」（PDF）。 2014年5月12日時点のオリジナル（PDF）からのアーカイブ。 2014年5月9日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)

出典

Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (2009-12-01). 「実世界ネットワークにおけるリンクベースの類似度計算のための効率的なアルゴリズム」. 2009年第9回 IEEE 国際データマイニング会議. pp. 734– 739. doi :10.1109/ICDM.2009.136. ISBN 978-1-4244-5242-2. S2CID 9799597。

Original text

Rate this translation

Your feedback will be used to help improve Google Translate

[simrank_plusplus-1] I. Antonellis、H. Garcia-Molina、C.-C. Chang. Simrank++: クリックグラフのリンク解析によるクエリ書き換え。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、408-421ページ。 [1]

[2] W. Yu, X. Lin, W. Zhang, L. Chang, J. Pei. 「More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks. VLDB '13 : Proceedings of the 39th International Conference on Very Large Data Bases」13～24ページ。 [2]

[:0-3] H. Chen、CL Giles「ASCOS++：SimRank問題に対処するための重み付きネットワークの非対称類似度尺度」ACM Transactions on Knowledge Discovery from Data (TKDD) 10.2 2015. [3]

[jeh_widom-4] G. JehとJ. Widom. SimRank: 構造的コンテキスト類似度の尺度. KDD'02 : Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543. ACM Press , 2002. 「アーカイブコピー」（PDF）。 2008年5月12日にオリジナル（PDF）からアーカイブ。 2008年10月2日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)

[lizorkin-5] D. Lizorkin、P. Velikhov、M. Grinev、D. Turdakov. SimRank計算における精度推定と最適化手法。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、422～433ページ。「アーカイブコピー」（PDF）。 2009年4月7日にオリジナル（PDF）からアーカイブ。 2008年10月25日閲覧。 {{cite web}}: CS1 maint: archived copy as title (link)

[cosimrank-6] S. RotheとH. Schütze. CoSimRank: 柔軟かつ効率的なグラフ理論的類似度尺度. ACL '14 : 計算言語学協会第52回年次会議議事録（第1巻：長編論文）, 1392-1402ページ. [4]

[fogaras_racz-7] D. FogarasとB. Racz. リンクベース類似検索のスケーリング. WWW '05 : Proceedings of the 14th international conference on World Wide Web, pages 641--650, New York, NY, USA, 2005. ACM . [5]

[8] アントネッリス、イオアニス、ヘクター・ガルシア・モリーナ、チ・チャオ・チャン。「Simrank++：クリックグラフのリンク分析によるクエリ書き換え」VLDB Endowment 1.1 論文集 (2008): 408-421. arXiv : 0712.0499

[yu_icde13-9] W. Yu、X. Lin、W. Zhang. 大規模ネットワークにおける効率的なSimRank計算に向けて. ICDE '13 : Proceedings of the 29th IEEE International Conference on Data Engineering、601--612ページ.「アーカイブコピー」（PDF）。 2014年5月12日時点のオリジナル（PDF）からのアーカイブ。 2014年5月9日閲覧。 {{cite web}}: CS1 maint: archived copy as title (link)

[simrank_plusplus-1] I. Antonellis、H. Garcia-Molina、C.-C. Chang. Simrank++: クリックグラフのリンク解析によるクエリ書き換え。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、408--421ページ。[1]

[2] W. Yu, X. Lin, W. Zhang, L. Chang, J. Pei. 「More is Simpler: Effectively and Efficiently Assessing Node-Pair Similarities Based on Hyperlinks. VLDB '13 : Proceedings of the 39th International Conference on Very Large Data Bases」13～24ページ。[2]

[:0-3] H. Chen、CL Giles。「ASCOS++：SimRank問題に対処するための重み付きネットワークの非対称類似度尺度」ACM Transactions on Knowledge Discovery from Data (TKDD) 10.2 2015.[3]

[jeh_widom-4] G. JehとJ. Widom. SimRank: 構造的コンテキスト類似度の尺度. KDD'02 : Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543. ACM Press , 2002. 「アーカイブコピー」（PDF）。 2008年5月12日にオリジナル（PDF）からアーカイブ。 2008年10月2日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)

[lizorkin-5] D. Lizorkin、P. Velikhov、M. Grinev、D. Turdakov. SimRank計算における精度推定と最適化手法。VLDB '08 : Proceedings of the 34th International Conference on Very Large Data Bases、422～433ページ。「アーカイブコピー」（PDF）。 2009年4月7日にオリジナル（PDF）からアーカイブ。 2008年10月25日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)

[cosimrank-6] S. RotheとH. Schütze. CoSimRank: 柔軟かつ効率的なグラフ理論的類似度尺度. ACL '14 : 計算言語学協会第52回年次会議議事録（第1巻：長編論文）, 1392-1402ページ. [4]

[fogaras_racz-7] D. FogarasとB. Racz. リンクベース類似検索のスケーリング. WWW '05 : Proceedings of the 14th international conference on World Wide Web, pages 641--650, New York, NY, USA, 2005. ACM . [5]

[8] アントネッリス、イオアニス、ヘクター・ガルシア・モリーナ、チ・チャオ・チャン。「Simrank++：クリックグラフのリンク分析によるクエリ書き換え」VLDB Endowment 1.1 論文集 (2008): 408-421. arXiv : 0712.0499

[yu_icde13-9] W. Yu、X. Lin、W. Zhang. 大規模ネットワークにおける効率的なSimRank計算に向けて. ICDE '13: Proceedings of the 29th IEEE International Conference on Data Engineering、601--612ページ. 「アーカイブコピー」（PDF）。 2014年5月12日時点のオリジナル（PDF）からのアーカイブ。 2014年5月9日閲覧。{{cite web}}: CS1 maint: archived copy as title (link)

[

[

[

[

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]