Overlap Measures

pDestiny·2022년 10월 2일
0

Network Science

목록 보기
10/10
post-thumbnail

2.2 Neighborhood Overlap Detection

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

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

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

SRV×VS \in \mathbb{R}^{|V| \times |V|} → similarity matrix

2.2.1 Local Overlap Measures

Sorensen Index

Ssorensen[u,v]=2N(u)N(v)du+dvS_{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

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

Jaccard Overlap

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

Resource Allocation(RA) index

SRA[v1,v2]=uN(v1)N(v2)1duS_{RA}[v_1, v_2] = \underset{u\in N(v_1) \cap N(v_2)}{\sum} \frac 1 {d_u}

Adamic Adar(AA) index

SAA[v1,v2]=uN(v1)N(v2)1log(du)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의 개수가 몇개가 존재하는지를 샌 것이다.

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

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

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

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

proof

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

Xsn=Xi=1nXi=i=0n+1XiXs_n = X\sum_{i=1}^n X^i = \sum_{i =0}^{n+1}X^i

and

snXsn=i=0nXii=1n+1Xis_n - Xs_n = \overset{n}{\underset{i=0}{\sum}}X^i - \overset{n+1}{\underset{i=1}{\sum}}X^i

sn(IX)=IXn+1s_n(I - X) = I - X^{n+1}

sn=(IXn+1)(IX)1s_n = (I-X^{n+1})(I - X)^{-1}

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

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

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

잘은 모르겠지만 일단 i=1Xi=(IX)1\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수의 기대값의 비율을 고려하였다.

AiE[Ai]\frac{A^i}{\mathbb{E}[A^i]}

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

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

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

E[A2[v1,v2]]=dv1dv2(2m)2uV(du1)du\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

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

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

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

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

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

SLNH[u,v]=I[u,v]+2mdudvi=1βiλ11iAi[u,v]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를 주게 된다. 수식을 위에서 언급했던 iAi=(IA)1\sum_i^{\infty}A^i = (I - A)^{-1} 을 적용하면 아래와 같은 수식이 마지막으로 구할 수 있다.

SLNH=2αmλ1D1(Iβλ1A)1D1S_{LNH} = 2\alpha m\lambda_1D^{-1}(I -\frac {\beta}{\lambda_1}A)^{-1}D^{-1}

참고로 DD는 degree diagonal matrix이다.

profile
Bioinformatician

0개의 댓글