2.2 Neighborhood Overlap Detection

링크를 찾아내기 위한 방법론들. $G = (V, E)$ 로 node와 엣지로 표현되는 그래프에서

$u, v \in V$의 가장 간단한 similarity measure는

$S[u, v] = |N(u)\cap N(v)|$로, $N(v)$는 node $v$의 이웃노드이다. 즉, 두 노드가 공유하는 이웃노드의 개수로 두 노드간의 유사도를 계산할 수 있다.

$S \in \mathbb{R}^{|V| \times |V|}$ → similarity matrix

2.2.1 Local Overlap Measures

Sorensen Index

$S_{sorensen}[u, v] = \frac {2|N(u) \cap N(v)|}{d_u + d_v}$

2.2에서 소개한 가장 간단한 형태의 measure는 edge의 개수가 많을 수록 similarity가 높아지는 되는 경향이 있었다. 그래서 Sorensen Index에서는 node u, v의 degree의 개수를 합한 값을 나누어 주어 Normalize 하여 similarity의 edge가 많은 노드에서 커지는 경향을 줄였다.

Salton Index

$S_{salton}[u, v] = \frac{2|N(u) \cap N(v)|}{\sqrt{d_vd_u}}$

Jaccard Overlap

$S_{jaccard}[u, v] = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|}$

Resource Allocation(RA) index

$S_{RA}[v_1, v_2] = \underset{u\in N(v_1) \cap N(v_2)}{\sum} \frac 1 {d_u}$

Adamic Adar(AA) index

$S_{AA}[v_1, v_2] = \underset{u\in N(v_1) \cap N(v_2)}{\sum} \frac 1 {log(d_u)}$

2.2.2 Global Overlap Measures

Local overlap measures 의 단점은 1 hop neighbor 만 고려하여 global한 overlap을 잡아내지 못한다는 것이다. 예를 들면 두 노드간에 전혀 overlap이 존재하지 않지만 같은 커뮤니티에 존재하는 경우에 Local overlap measure로는 두 노드간의 similarity를 계산 할 수 없다.

Katz Index

단순하게 node u에서 v로 모든 length의 path의 개수가 몇개가 존재하는지를 샌 것이다.

$S_{katz}[u, v] = \overset{\infty}{\underset{i=1}{\sum}}\beta^iA^i[u, v]$

여기서 $\beta \in \mathbb{R}^+$는 사용자 정의의 paramemter로 $\beta < 1$ 이면 hop이 증가할 때, 패널티가 붙게 되는 구조이다.

$\infty$ 하게 $S_{katz}$를 구하는 방법은 아래의 Theorem을 참조해야 한다.

Theroem
Let $X$ be a real-valued square matrix and let $\lambda_1$ denote the largest eigenvalue of $X$, then,
$(I - X)^{-1} = \overset{\infty}{\underset{i=0}{\sum}}X^i$
if and only if $\lambda_i < 1$ and $(I - X)$ is non-singular

proof

Let $s_n = \overset{n}{\underset{i=0}{\sum}}X^i$ then we have that

$Xs_n = X\sum_{i=1}^n X^i = \sum_{i =0}^{n+1}X^i$

and

$s_n - Xs_n = \overset{n}{\underset{i=0}{\sum}}X^i - \overset{n+1}{\underset{i=1}{\sum}}X^i$

$s_n(I - X) = I - X^{n+1}$

$s_n = (I-X^{n+1})(I - X)^{-1}$

and if $\lambda_1 < 1$ we have that $\lim_{n \to \infty}X^n = 0$ so

$\lim_{n\to \infty} = \lim_{n\to \infty}(I - X^{n})$

이에 따라 $\overset{\infty}{\underset{i=1}{\sum}}\beta^iA^i[u,v] = (I - \beta A)^{-1} - I$ 이다.

잘은 모르겠지만 일단 $\underset{i=1}{\overset{\infty}{\sum}}X^i = (I - X)^{-1}$이라는 것을 알고 있으면 유용할 듯 하다.

Leicht, Holme, and Newman (LHN) Similarity

Katz index의 단점은 node degree에 편중될 수 밖에 없다는 점이 없다. 이 문제를 해결하기 위해 Leicht et al.[2016]이 제안한 metric이 있다. 이 metric은 실제 두 노드간의 path의 수와 path수의 기대값의 비율을 고려하였다.

$\frac{A^i}{\mathbb{E}[A^i]}$

$\mathbb{E}[A^i]$를 계산하기 위해서는 configuration model이라는 random graph을 가정한 모델을 사용해야 한다.

$\mathbb{E}[A[u, v]] = \frac {d_ud_v}{2m}$

위의 공식이 의미하는 바는 $m = |E|$일 때, 노드 u에서 노드 u가가진 edge들로 출발 했을 때, 노드 v에 도착할 확률은 $\frac{d_v}{2m}$이라는 것이다. 위의 식은 두 노드간에 1홉으로 연결될 확률을 의미하지만 2홉 일 경우에는 어떻게 표현될까?

$\mathbb{E}[A^2[v_1, v_2]] = \frac {d_{v_1} d_{v_2}}{(2m)^2}\underset{u\in V}{\sum}(d_u - 1)d_u$

복잡해 보이지만 이 식을 쪼개보면 $v_1$ 에서 어떤 다른 노드 $u$를 경유해서 노드 $v_2$에 도달하는 확률을 의미한다. 먼저 $v_1$에서 $u$로 가는 것은 맨 처음 1홉에 으로 두 노드로 도달하는 것과 같다. 즉, $\frac {d_{v_1}d_u}{2m}$이다. 그리고 노드 $u$에서 노드 $v_2$ 로 가는 것은 이미 $u$는 사용 되었으니 하나를 빼어 $\frac {(d_u-1)d_{v_2}}{2m}$이다.

그러나 홉 수가 늘어나면 쫓아갈 수가 없게 된다. 그래서 긴 홉의 path의 수의 기대값을 얻기 위해서 가장 큰 고유백터가 늘어나는 path의 숫자를 추정할 수 있다는 것을 활용한다.

$p_i \in \mathbb{R}^{|V|}$ 벡터가 있고, 이 벡터가 어떤 노드 u와 다른 노드간의 length-i에서 path의 개수를 의미한다고 하자. 그러면 우리는 i가 커지는 것을 생각할 수 있고, $Ap_i = \lambda_1p_{i-1}$를 얻는다. 이 $p_i$는 결과적으로 어떤 고유벡터로 수렴할 것이다.(pagerank를 생각하자) 한마디로 두 노드간의 path의 숫자는 $\lambda_1$에 매 iteration마다 의존적이다. 이를 수식으로 표현하면

$\mathbb{E}[A^i[u, v]] = \frac{d_ud_v\lambda^{i-1}}{2m}$

위의 수식에서 $i=1$로 놓으면 1홉의 path수의 기대값이 된다. path의 수는 $\lambda$에 의존적임으로 $\lambda^{i-1}$을 곱해주게 되는 것이다. 이제 이 수식을 Katz index에 넣어주면 LHN similarity가 완성이 된다.

$S_{LNH}[u, v] = I[u, v] + \frac{2m}{d_ud_v}\underset{i=1}{\overset{\infty}{\sum}}\beta^i\lambda^{1-i}_1A^i[u, v]$

가 된다. (Katz index구하는 방법을 다시 떠올려 보자.) 이 수식에 따르면 기대되는 path의 수보다 더 더 많은 path가 있을 경우에 더 높은 similarity를 주게 된다. 수식을 위에서 언급했던 $\sum_i^{\infty}A^i = (I - A)^{-1}$ 을 적용하면 아래와 같은 수식이 마지막으로 구할 수 있다.

$S_{LNH} = 2\alpha m\lambda_1D^{-1}(I -\frac {\beta}{\lambda_1}A)^{-1}D^{-1}$

참고로 $D$는 degree diagonal matrix이다.