Chp_3_4 Network Measures

3.4 유사성의 정의 (Similarity)

이번장에서는, 네트워크에서 두개 노드에 대한 유사성을 측정해 볼것이다.
소셜미디어에서, 이 두개노드는 네트워크 상에서 친구 관계를 의미하거나 연관된 제품들을 표시할수 있다.
이 연결된 두개의 항목의 유사성을 계산하는데는 소속된 네트워크의 특징에 따라 계산하거나 각 개인이 만들어내는 컨텐츠에 따라 다르게 계산할수 있다, 이를 전자는 "네트워크 유사성" 후자는 "컨텐츠 유사성" 이라 한다.

"컨텐츠 유사성"은 챕터 5에서 다루게 된다.

이장에서는, 두개의 연결된 노드의 네트워크 정보에 따라 유사성을 계산하게 된다.
네트워크 정보를 사용한다면, 두개 노드의 유사성을 계산할때는 구조적 동일성(structural equivalence)과 일반적 동일성(regular equivalence)을 사용하게 된다.


3.4.1 구조적 동일성(Structural Equivalence)

구조적 동일성 계산에서, 2개의 노드가 공통으로 관계되어 있는 이웃 노드를 살펴볼것이다, 이웃 노드의 크기를 통해 두개의 노드의 유사성을 확인할수 있다

예를들면, 2명의 남자 형제가 누나, 엄마, 아빠, 조부모 등등이 있는 형태이다.
이런 상황은 유사성을 가짐을 보여준다, 반면에 두명의 임의의 남성,여성의 개인은 공통점이 적고 유사하지 않다(서로 남남이니까).
이 장에서의 유사성은 측정은 두개의 노드의 이웃간 중첩 사항을 기반으로 이루어진다.
각각 N(Vi)와 N(Nj)를 노드 Vi와 Vj의 이웃이라 할때를 생각해보면.
이 상황에서, 유사성 측정은 다음과 같이 이루어 진다

대형 네트워크에서, 이 값은 급격하게 증가하게 된다, 이유는 노드가 많은 이웃을 공유하기 때문이다.
일반적으로, 유사성은 한정된 값을 가지는데 0~1 사이의 값을 가진다.
jasccard 유사성, 코사인 유사성등 다양한 정규화 절차가 발동할 수 있다.

일반적으로, Vi의 이웃의 정의는 Vi 자체는 제외하고 정의내린다.
이것은 앞어 말한 유사점들과 관련된 문제들로 이어진다, 왜냐하면 노드가 연결되어 있고 공유하지 않으면 유사성이 0이 되기 때문이다
노드가 그들의 이웃에 포함 된다고 가정하고 해결할수 있다.

예시 3.14.


그림 3.14의 그래프를 생각해보자
노드 v2와 v5의 유사성 값을 확인해보면

그림 3.14 : 유사성 계산을 위한 단순한 그래프.

Vi와 Vj 사이의 유사성을 구하는 더 흥미로운 방법은 (시그마)(vi, vj)를 임의의 이웃을 선택해서 계산해 보는것이다.
두 값에 차이가 클수록, vi와 vj ((시그마)(vi,vj)) 사이에 관찰된 유사성은 의미가 있게 된다.
노드 Vi와 Vj 그리고 차수 di,dj 에 대해, 기대값은 (didj/n) 이고 이떄 n은 노드의 개수를 의미한다.
di/n 이 vi에 이웃에 해당하는 값이 될수 있고, vj가 dj의 이웃일때 didj/n 이 겹치기때문이다.
(시그마)(vi,vj)를 다음과 같이 적을수 있는데

그러므로, 유사성 측정은 무작위 기대치를 빼서 계산하게 된다:

일때

는 기본적으로 Ai, Aj 사이의 공분산이다.

공분산은 분산의 곱을 이용하면 정규화 시킬수 있는데,

이건 개인 상호관계 계수라고 한다.
값의 특징은, 다른 2개의 측정방식과는 다르게, 범위는 -1부터 1까지 이다.
양의 계수는 vi가 vk와 친구가 될때 vj도 vk와 친구가 될 가능성이 있음을 의미한다.
음의 값은 반대임을 나타낸다( vi와 vk가 친구일경우 vj와 vk가 친구가 될 가능성은 낮음)
값이 0일때는 vi와 vj의 친구가 되는 선형 사이에 선형관계가 없음을 나타낸다.



3.4.2 정규 동등성 정의 (Regular Equivalence)
정규 동등성은, 구조적 동등성과 다르게, 각 개인이 공유하는 이웃에 대해서는 살펴보지 않고, 하지만 이웃들이 얼마나 비슷한지 유사한지 살펴본다.
예를들면,운동선수들은 비슷하지만 그게 그들이 직접 알고있기 때문은 아니다, 하지만 그들은 비슷한 사람들을 알고 있기 때문이다, 코치,트레이너,그리고 다른 선수들이다.


같은 주장은 개인들이 직접 서로를 알지 못할수도 있지만 매우 유사한 개인들과 접촉하고 있는 다른 직업이나 산업에 적용된다.

정규 동등성은 이웃의 유사성을 비교함으로써 유사성을 평가하며 이웃의 중복은 비교하지 않는다.
이를 공식화 하는 한가지 방법은 노드 vi와 vj가 유사한 이웃 vk와 vl을 많이 가지고 있을때 유사한것을 고려하는 것이다.
이 컨셉은 그림 3.15(a) 에서 볼수있다.

비슷하게, 그림 3.15: 정규 동등성을 보면.
실선은 엣지를 의미한다, 그리고 대쉬선은 두 노드간 유사점을 의미한다.
정규 동등성을 보면, 노드 Vi와 Vj사이의 유사성은 인접노드 vk와 vl사이의 유사성 또는 (b)인접 노드 vk와 노드 vk사이의 유사성으로 대체된다.
비슷하게,이 공식은 자기 중심적이라고 볼수 있는데 i와 j 를 해결하기 위해 k와 l이 필요하고, k와 l을 해결하기 위해 이웃이 필요한 방식이다.

따라서, 이 공식을 풀기 위해 vj가 vi의 이웃 vk와 비슷할때 노드 vi가 노드 vj와 비슷하다고 가정한다.
이건 그림 3.15(b)를 보여준다.
공식으로 보면

백터 형식에서, 우린 다음과 같이 볼수있다,

노드는 높은 친밀성을 지닌다.
이 공식으로 이것을 확실히 할수 있는데, 이 벡터 형식에 ID메트릭스를 추가할수 있다.
ID 매트릭스를 추가하면 자체 유사성을 나타내는 모든 대각선 항목에 1이 추가됨 (시그마)regular(vi; vi)

수식을 정리하면 다음과 같이 이루어진다

규칙적 동등성 유사성을 찾는데 사용할 수 있다.
방정식 3.69를 보면 Katz centrality (방정식 3.21) 방정식과 유사함을 알수있다.
Katz 중심도 에서,우리는 융합을 위어 어떻게 선택하는지에 따라 주의해야한다.

일반적인 관행은 (alpha) <1=>와 같은 알파, 여기서 람다는 A의 가장 큰 고유값이다.


예시 3.15. 그림 3.14의 그래프를 인접 행렬로 만들면 다음과 같다

가장큰 고유값 A는 2.43 임을 알수있다.

으로 설정했다, 그리고 계산하면 다음과같은 인접행렬이 나오게된다.

이 행렬의 모든 행 또는 열은 다른 노드와 노드의 유사성을 보여준다.
노드 V1이 노드 V2및 V3와 가장 유사하다는것을 알수있다.
더 나아가서, 노드 V2와 V3 는 이 그래프에서 높은 유사성을 지님을 볼수있다