Structure Role in Network

## Role

role이란 다른 말로 function(기능)이다. 직관적인 예로 먹이 사슬에서 각각의 종들의 역할을 생각하면 된다. 또 다른 예로는 회사에서 회장이 맡은 임무, 부장이 맡은 임무, 인턴이 맡은 임무 등을 생각하면 된다.

대표적인 Role의 종류는 다음 3가지와 같다.

- Hub : Center of stars

- community : members of cliques(= edge들을 많이 포함하고 있는 노드들의 집단에서의 노드)

- outlier : 떨어진 애들

여기서 community는 직관적으로도 알 수 있겠지만 dense하게 밀집되어있다.

example of role

 

## Role vs Group

Role과 Group의 공통점은 노드들의 집합이라는 점이다.

하지만 role은 구조적으로 비슷한 위치에 있는 노드들을 말한다. 이 떄 노드들이 직접적으로 연결이 안될 수도 있다. 

반면에 group은 무조건 직접적인 연결이 반드시 존재해야한다.

이를 쉽게 실생활 예로 들면

Role : 교수, 직원 . communities : AI Lab, System Lab 을 말한다

Role에 대해서 자세히 설명하자면 structurally equivalence(구조적으로 동일)한 집단을 말한다.

이는 다시 말하면 두 노드가 같은 role을 가질 떄, 다른 노드들과 같은 relation을 가져야한다는 것이다.

Graph의 그림으로 생각하면 in-degree == out-degree가 되어야한다. 즉, 이것이 structurally equivalence 이다.

example of role

 

## ROIX

그러면 이러한 role들을 어떻게 자동으로 추출할 수 있을까? 이러한 Role을 자동적으로 찾기 위한 알고리즘이 ROIX이다.

이의 특징은 비지도 학습이고, input 값으로 인접행렬만 넣으면 O(N) 시간 복잡도라는 매우 빠른 시간 내로 계산이 되는 알고리즘이다.

또한, 한 노드의 역할들(mixed membership)을 정의하고 각각의 feature들을 알려준다.

ROIX flow

이 flow chart를 중심으로 다시 봐보자

첫번쨰로 input으로 인접행렬을 넣는다. 그리고 recursive 하게 feature들을 추출한다.(추후 자세히) 이렇게 추출한 feature들을 node와 feature 들의 matrix로 만들고 role을 추출한다.

그리고 마지막으로 output으로 각 node들의 role에 대한 matrix와 role과 feature들에 대한 matrix가 2개가 나온다.

자세히 한 번 알아보자

 

## Recursive feature extraction

recursive feature extraction

recursive feature extraction의 matrix를 한 번 보자

위 그림에서 Local은 자신과 관련성이 있는 edge들을 말하고, Egonet은 자신의 이웃들끼리의 관련성을 말한다.

Local feature는 한 node의 degree의 값이다. 그리고 이게 feature의 한 컬럼으로 들어간다.

Egonet feature는 자신과 연결된 노드들의 (ex. edge의 개수)평균 값이다.

따라서 이 둘을 합쳐 Neighborhood feature라고 정의하고 이는 자신을 중심으로 자신과 주변이 어떤 관계를 맺고 있는 가를 나타낸다. 이는 인접행렬에서 계산된 값이다.

그리고 Recursive 부분은 local과 egonet의 정보를 바탕으로 처음에 자신이 A이고 B가 이웃이었다면 다음엔 자신이 B이고 이웃이 또 다른 노드과 되는 것이다. 따라서 이웃의 이웃까지 다 계산하는 과정을 반복적으로 이뤄낸다..

즉, local + egonet을 mean sum 하여 recursive feature를 계산하는 것이다.

이로 인해 Recursive feature는 내가 연결하고 있는 다른 노드가 어떤 구조로 연결이 되어 있는가를 파악할 수 있다.

이렇게 생성된 하나의 matrix에선 recursive하게 생성하기 때문에 같은 값이 나올 가능성이 있다.

따라서 이를 해결하기 위해 person correlation 값을 계산 후 높은 것을 제거한다.

 

이 후 role extraction을 통해 raw가 유사한 node들 끼리 clustering을 진행하여 비슷한 role 끼리 묶여지게 role을 추출하여 최종 matrix를 return 한다.

이러한 ROIX는 co-authorship 분야에서 쓰여 논문 저자들간의 관계 모델링이나 co-purchasing book 에서 edge filtering을 수행하면서 적용된다.