1. introduction


G가 웹사이트끼리 하이퍼링크를 뜻한다면, Univ에 의해 링크되고 있는 ProfA오 ProfB는 비슷할 것이다. 마찬가지로 StudentA와 StudentB도 비슷할 것이다.

G를 기반으로 pair를 노드로 가지는 G2를 만든 후, 노드끼리의 SimRank라는 것을 계산하도록 한다.


일단 SimRank를 구하기 위해서는 G의 두 노드사이의 similarity가 필요하다.

domain에 관계없이 어떤 것이든 관계성이 있는 것에 적용될 수 있는 알고리즘을 생각했다는게 중요하다.


3. basic graph
 
I(v)는 노드 v의 in-neighborhoods
O(v)는 노드 v의 out-nieghborhoods
 
4. SimRank
 
4.1. Motivation
비슷한 object에 의해 reference되고 있는 두 object는 비슷할 것이다-가 기본 전제.
그렇다면 동일한 object의 simrank에는 1을 부여할 수 있을 것이다.
앞으로 sim rank를 구하는 공식을 살펴보자.
 
4.2 Basic SimRank Equation
- a랑 b랑 같으면 s(a,b)=1
- 그렇지 않으면
 

 

 
 
 
  
 
즉, 주변 것들의 유사도를 모두 합쳐서 평균낸 것에 C를 곱한 것이다.
 
  • similarity 를 propagating 시키기 위해 G2 그래프를 만드는데, <a,b><c,d> 두 노드에서 a->c b->d의 edge가 이전에 있었으면 G2에서 edge가 있다.
  • 그래프에서 ProfA,ProfA와 같이 영향을 주지 않는 singleton node와 ProfA,StudentA와 같은 similarity 0인 노드는 포함되어있지 않다.
  • 만약 x가 c와 d를 가리키고 있다면 s(x,x)=1이지만 s(c,d)= Cs(x,x)가 되어야 한다. C는 confidence level or decay factor.

4.3 Bipartite SimRank


A가 sugar,frosting,eggs를 사고, B가 frosting,eggs,flour를 샀다면 둘은 비슷하다고 할수 있다.

왜냐하면 A와 B가 둘다 frosting과 eggs를 샀기 때문이다.

또한 sugar와 flour자체도 비슷하기 때문이다.

왜냐하면 비슷한 구매자인 A와 B가 모두 구매했기 때문이다.

즉 아이템간 유사도와 구매자의 유사도는 서로 reinforce한다.




References



티스토리툴바