심랭크

SimLrank는 단순하고 직관적인 그래프-이론적 모델을 바탕으로 한 일반적인 유사성 측도다.SimLrank는 다른 개체와의 관계를 기반으로 객체가 발생하는 구조적 맥락의 유사성을 측정하는 객체 대 객체 관계가 있는 모든 영역에 적용할 수 있다.효과적으로 SimLrank는 "두 개의 물체가 유사한 물체가 참조될 경우 유사하다고 간주된다"고 하는 조치다.심랭크가 널리 채택되고 있지만, 서로 다른 요인에 의해 영향을 받는 불합리한 유사성 점수를 산출할 수 있으며, 증거 가중치 도입,^[1] 심랭크가^[2] 무시하는 추가 용어 삽입, 페이지랭크 기반의 대안 활용 등 여러 가지 방법으로 해결할 수 있다.^[3]

소개

많은 애플리케이션은 객체 간의 "유사성"을 측정해야 한다.한 가지 분명한 예가 전통적인 텍스트 기업이나 월드 와이드 웹에서 "찾아가는 유사 문서" 질의다.보다 일반적으로 유사성 측정은 사용자 선호도에 따라 "비슷한" 사용자와 항목을 그룹화하는 추천자 시스템에서 협업 필터링과 같은 개체 군집화에 사용할 수 있다.

일반적으로 그 영역에 대한 유사성의 적절한 정의와 도메인에 따라 개체의 다양한 측면을 사용하여 유사성을 결정할 수 있다.문서 말뭉치에서는 일치하는 텍스트를 사용할 수 있으며, 협업 필터링을 위해 유사한 사용자를 공통 환경설정으로 식별할 수 있다.SimLrank는 많은 관심 영역에서 발견되는 객체 대 객체 관계를 이용하는 일반적인 접근방식이다.예를 들어, 웹에서는 두 페이지 사이에 하이퍼링크가 있으면 두 페이지가 연관되어 있다.유사한 접근방식은 과학 논문과 인용문 또는 상호 참조 정보가 있는 다른 문서 말뭉치에 적용될 수 있다.추천인 시스템의 경우, 사용자가 항목을 선호하는 것은 사용자와 항목의 관계를 구성한다.이러한 도메인은 자연스럽게 그래프로 모델링되며, 노드는 객체를 나타내고 가장자리는 관계를 나타낸다.

SimRrank 알고리즘 뒤에 숨겨진 직관은 많은 도메인에서 유사한 물체가 유사한 물체에 의해 참조된다는 것이다.보다 정확히 말하면, 개체 $a{\displaystyle }$ ${\displaystyle a}$과 b ${\displaystyle b}$이$($가) 각각 개체 $c{\displaystyle }$ ${\$$displaystyle$ $c$$}$과 $d{\displaystyle }$ ${\displaystyle d}$에서 가리키는 경우, 개체 $a$가 유사한 것으로 간주된다$$.기본적인 사례는 물체가 자신과 최대적으로 유사하다는 것이다.^[4]

SimLrank는 구조적인 맥락의 유사성만을 결정하는 일반적인 알고리즘이라는 점에 유의해야 한다.SimRrank는 최소한 관계 유사성의 개념에 기초하기 위해 개체 사이에 충분한 관련 관계가 있는 모든 영역에 적용된다.분명히, 다른 영역별 측면의 유사성도 중요하다. 이러한 유사성 측정은 전체 유사성 측도를 위해 관계 구조-컨텍스트 유사성과 결합될 수 있고, 결합되어야 한다.예를 들어, 웹 페이지의 경우 SimLrank는 전통적인 텍스트 유사성과 결합될 수 있다; 같은 생각이 과학 논문이나 다른 문서 회사에 적용된다.추천 시스템의 경우, 사용자 간의 유사성(예: 동일한 성별, 동일한 지출 수준)뿐만 아니라 품목 간(예: 양쪽 컴퓨터, 양쪽 의류 등)에 대해 알려진 유사성이 내장되어 있을 수 있다.다시 말하지만, 이러한 유사성은 전체적인 유사성 측정을 생성하기 위해 선호도 패턴을 기반으로 계산된 유사성 점수와 결합될 수 있다.

기본 심랭크 방정식

지시된 그래프에서$$ $노드{\displaystyle }$ v$${\$displaystyle v$}의 경우 v {\displaystyle $v$과(와) ${\displaystyle$ I$(v)}$ 및 $O{\displaystyle (와}$) ${\displaystyle O(v)}$을(와${\displaystyle )}$ 각각 v ${\displaystystyle v$의 인접 및 아웃네이버 $집합$으로 나타낸다.Individual in-neighbors are denoted as ${\displaystyle I_{i}(v)}$, for ${\displaystyle 1\leq i\leq \left I(v)\right }$, and individual out-neighbors are denoted as ${\displaystyle O_{i}(v)}$, for ${\displaystyle 1\leq i\leq \left O(v)\right }$.

Let us denote the similarity between objects ${\displaystyle a}$ and ${\displaystyle b}$ by ${\displaystyle s(a,b)\in [0,1]}$. Following the earlier motivation, a recursive equation is written for ${\displaystyle s(a,b)}$. If ${\displaystyle a=b}$ then ${\$$displaystyle s(a$$,$$b)}$는 $1{\displaystyle \mathrm{}}$ {\$displaystyle$ 1}($으)$로 정의된다$.$ 그렇지 않으면

${\displaystyle s(a,b)={\frac {C}{\\좌측 I(a)\우측 \{i=1}^{i=1^{{i=1}\좌측 I(a)\우측 _{j=1}^{j=1}^{{i}(a), 우측 }s,I_{j}(b)}$

여기서 $C{\displaystyle }$ ${\displaystyle C}$은(는) $0{\displaystyle \mathrm{}}$ ${\displaystyle 0$$}$과(와) $(\displaystyle$ 1) 사이의 상수$.$ 여기서 약간 기술적으로 볼 $때{\displaystyle }${\$displaystyle a$} $또는$ b$${\$displaysty b}$은(는) 인접하지 않을 수 있다$$.Since there is no way to infer any similarity between ${\displaystyle a}$ and ${\displaystyle b}$ in this case, similarity is set to ${\displaystyle s(a,b)=0}$, so the summation in the above equation is defined to be ${\displaystyle 0}$ when ${\displaystyle I(a)=\emptyset }$ or ${\displaystyle I}$${\displaystyle (b}$)${\displaystyle }$= ${\displaystyle \mathrm{\varnothing }}$ ${\displaystyle I(b)=\emptyset$ $\}.$

SimLrank의 행렬 표현

Let ${\displaystyle \mathbf {S} }$ be the similarity matrix whose entry ${\displaystyle [\mathbf {S} ]_{a,b}}$ denotes the similarity score ${\displaystyle s(a,b)}$, and ${\displaystyle \mathbf {A} }$ be the column normalized adjacency matrix whose entry ${\displaystyle [\mathbf{A}{]}_{a,b}=\frac{1}{}}$${\displaystyle \frac{}{}}$$I$$$(${\displaystyle \frac{b}{}}$) ${\displaystyle \frac{\{\backslash }{}}$$displaystyle$ $[\mathbf {A}$$$$]_{a,b}={\tfrac {1}{{\$tfrac {1$}{{\mathcal{I}(b)}}}}}}}},$ 그 밖의 경우 0$.$그 다음, 매트릭스 표기법에서 SimLrank는 다음과 같이 공식화될 수 있다.

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

여기서 $I{\displaystyle \mathbf{}}$ ${\$은$($는) ID 행렬이다.

SimLrank 계산

그래프 $G{\displaystyle }$ ${\displaystyle G}$에 대한 SimRrank 방정식의 해법은 고정점까지 반복하여 얻을 수 있다$$.Let ${\displaystyle n}$ be the number of nodes in ${\displaystyle G}$. For each iteration ${\displaystyle k}$, we can keep ${\displaystyle n^{2}}$ entries ${\displaystyle s_{k}(*,*)}$, where ${\displaystyle s_{k}(a,b)}$ gives the score between ${\displayst$$yle a}$ and ${\displaystyle b}$ on iteration ${\displaystyle k}$. We successively compute ${\displaystyle s_{k+1}(*,*)}$ based on ${\displaystyle s_{k}(*,*)}$. We start with ${\displaystyle s_{0}(*,*)}$ where each ${\displaystyle s_{0$$}(a,b)}$은(는) 실제 SimRrank 점수 $s{\displaystyle }$ ${\displaystyle (,}$ ${\displaystyle b}$) ${\displaystyle s(a,b)}$에 대한 하한이다$.$

${\displaystyle s_{0}(a,b)={\mbox}{{\mbox{{}}}}{{\mbox{{}}}{{}}a=b{\mbox{}}},\0{\mbox{},{}}}}}}}, {\mbox{}}}}}\end{case}}}$

$s{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle \ast }$,${\displaystyle }$${\displaystyle \ast }$)에서$$ $s{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$ + 1${\displaystyle {}_{}}$( , ${\displaystyle b}$) ${\displaystyle s_{k$$+1}(a,b)}$을(를$)$ 계산하려면 기본 SimLrank 방정식을 사용하여 다음을 얻는다$.$

${\displaystyle 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)}$

$a{\displaystyle }$${\displaystyle }$= ${\displaystyle b}$ ${\displaystyle a\neq$ b$}$의 경우$$${\displaystyle {및}_{}}$ $s{\displaystyle {}_{}}$ k${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ a${\displaystyle }$,${\displaystyle b}$) = ${\displaystyle 1}$ ${\displaystyle s_{k+1}(a,b)=1}$의 경우$$ a =${\displaystyle }$b ${\displaystyle a=b$즉, 각 ${\displaystyle \mathrm{반복}}$ $k{\displaystyle }$+ 1 ${\displaystyle k+1}$에서 기본 SimRrank 방정식에 따라$$ ${\displaystyle \mathrm{이전}}$ 반복 $k{\displaystyle }$ ${\displaystyle k}$에서 ${\displaystyle (,}$ b )${\displaystyle(a,b)}$의 인접성 점수를 사용하여$$ $(,{\displaystyle b}$ )${\displaystystyle$ k$}$의 유사성을 업데이트한다$.$$값{\displaystyle }$ s ${\displaystyle k_{}}$ ${\displaystyle \ast }$ ,${\displaystyle )}$ ) ${\displaystyle s_{k}(*,*)}$은(는$)$ k {\$displaystyle k}$이(가) 증가함에 따라 감소하지 않는다$$.It was shown in ^[4] that the values converge to limits satisfying the basic SimRank equation, the SimRank scores ${\displaystyle s(*,*)}$, i.e., for all ${\displaystyle a,b\in V}$, ${\displaystyle \lim _{k\to \infty }s_{k}(a,b)=s(a,b)}$.

원래의 SimLrank 제안에서는 수행할 붕괴 $인자{\displaystyle }$ C${\displaystyle }$= 0${\displaystyle .8}$ ${\displaystyle C=0.8}$과 고정 숫자 $K{\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle K=5}$을(를) 선택할 것을 제안했다.그러나, 최근의 $연구$는 C ${\displaystyle C}$과 K$${\$displaystyle K}$의 주어진 값이 일반적으로$$ 반복적으로 계산된 SimLank 점수의 상대적으로 낮은 정확도를 암시한다는 것을 보여주었다.보다 정확한 연산 결과를 보장하기 위해 후자 논문은 더 작은 붕괴 계수($특히{\displaystyle }$ C${\displaystyle }$= 0${\displaystyle .6}$ $[\displaystyle C=0.6$를 사용하거나 더 많은 반복을 취할 것을 제안한다.

코심랭크

CoSimLrank는 SimLrank의 변종이며, 로컬 공식도 가지고 있다는 장점이 있다. 즉, CoSimLrank는 단일 노드 쌍에 대해 계산될 수 있다.^[6]$S{\displaystyle \mathbf{}}$ ${\$을(를) 유사성 매트릭스로 하고$$$,{\displaystyle {}_{}}$[$],$ b {\$displaystyle$ [\$mathbf$ {$S} ]_${$a$$,b$$}$ 항목이 유사성 점수 $(,$b ${\displaystyle )}$를 나타내고$,$ $A{\displaystyle \mathbf{}}$ ${\$displaystystyle \mathbf {A}을($으$) 열 정규화 매트릭스탠리듬)로$$$$ 표시한다.그 다음, 행렬 표기에서 CoSimLrank는 다음과 같이 공식화될 수 있다.

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

여기서 $I{\displaystyle \mathbf{}}$ ${\$은$($는) ID 행렬이다.단일 노드 쌍의 유사성 점수만 계산하려면 $p{\displaystyle {}^{}}$( ${\displaystyle 0{}^{}}$)${\displaystyle {}^{}}$( i${\displaystyle }$)${\displaystyle }$= e ${\displaystyle i_{}}${\$displaystyle$ p$^{0)}(i)=e_{i$}를 표준 기준의 벡터(즉$$, $e{\displaystyle }$ ${\displaystyle e_$${i$$})$로 하고$,$ 다른 모든 항목은 0으로 한다.그러면 CoSimLrank는 두 단계로 계산할 수 있다.

1. ${\displaystyle p^{{(k)}=Ap^{(k-1)}}}}$
2. ${\displaystyle s(i,j)=\sum _{k=0}^{\nothy }{k}\langle p^{(k)}(i),p^{(k)}(j)\angle }}}}}$

1단계는 개인화된 PageLack의 단순화된 버전을 볼 수 있다.2단계는 각 반복의 벡터 유사성을 요약한다.행렬과 로컬 표현 둘 다 동일한 유사성 점수를 계산한다.$또한{\displaystyle {}^{}}$ CoSimLrank는 p${\displaystyle {}^{}}$( ${\displaystyle 0^{}}$)${\displaystyle {}^{}}$( ${\displaystyle i}$) ${\displaystyle p^{(0)}(i)}$을(를) 수정하여 노드 집합의 유사성을 계산하는 데도 사용할 수 있다$.$

심랭크에 대한 추가 연구

• 포가라스와 라츠는 몬테카를로 방법을 사용한 확률론적 계산을 통해 심랭크 연산 속도를 높일 것을 제안했다.
• 안토넬리스 외 ^[8]연구진확장된 SimRrank 방정식은 (i) 사건 노드에 대한 증거 인자 및 (ii) 연결 가중치를 고려한다.
• Yu 등은 ^[9]미세한 메모화 방법을 통해 SimLrank 연산을 더욱 개선하여 서로 다른 부분 합계의 작은 공통 부분을 공유했다.
• Chen과 Giles는 SimRrank의 한계와 적절한 사용 사례를 논의했다.^[3]

부분 합계 메모화

Lizorkin 외.^[5]는 SimLrank의 연산 속도를 높이기 위한 세 가지 최적화 기법을 제안했다.

1. 필수 노드를 선택하면 a-priori 영점수를 갖는 노드 쌍의 일부 계산이 제거될 수 있다.
2. 부분 합계 메모는 유사성 합계의 일부를 나중에 재사용할 수 있도록 캐싱함으로써 서로 다른 노드 쌍 사이의 유사성에 대한 반복적인 계산을 효과적으로 줄일 수 있다.
3. 유사성에 대한 임계값 설정은 계산할 노드 쌍의 수를 더 줄일 수 있다.

In particular, the second observation of partial sums memoization plays a paramount role in greatly speeding up the computation of SimRank from ${\displaystyle {\mathcal {O}}(Kd^{2}n^{2})}$ to ${\displaystyle {\mathcal {O}}(Kdn^{2})}$, where ${\displaystyle K}$ is the number of iterrations, $d{\displaystyle }$ ${\displaystyle d}$은(는) 그래프의 평균 수준이고 $n{\displaystyle }$ ${\displaystyle n}$은(는) 그래프에 있는 노드 수입니다.부분 합계 메모화의 중심 개념은 다음 두 단계로 구성된다.

첫째, ${\displaystyle I}$(${\displaystyle }$) ${\displaystyle I(a)}$에 대한 부분 합계는 다음과 같이 메모된다$$.

${\displaystyle {\textial}_{I(a)}^{s_{k}}=\sum _{i\in I(a)s_{k}(i,j),\qquad(\all j\in I(b)}$

${\displaystyle \mathrm{그리고}}$ $s{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$+ ${\displaystyle 1}$ (${\displaystyle {}_{}}$,${\displaystyle }$b${\displaystyle }$) ${\displaystyle s_{k+1}(a,$${\displaystyle b}$$)}$은(는) ${\displaystyle {}_{}^{}}$ (${\displaystyle {}_{}^{}}$) ${\displaystyle {k_{}}_{}^{}}$( )${\displaystyle {\partial}_{I(a)^{k}}}}(j)$에서 반복적으로$$ 계산된다.

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

Consequently, the results of ${\displaystyle {\text{Partial}}_{I(a)}^{s_{k}}(j)}$, ${\displaystyle \forall j\in I(b)}$, can be reused later when we compute the similarities ${\displaystyle s_{k+1}(a,*)}$ for a given vertex ${\displaystyle a}$ as the제1논쟁

참고 항목

• 페이지랭크

인용구

원천

• Cai, Y.; Cong, G.; Jia, X.; Liu, H.; He, J.; Lu, J.; Du, X. (2009-12-01). "Efficient Algorithm for Computing Link-Based Similarity in Real World Networks". 2009 Ninth IEEE International Conference on Data Mining: 734–739. doi:10.1109/ICDM.2009.136. ISBN 978-1-4244-5242-2.