Chapter3. Motifs and Structural Roles in Networks

투빅스 12기 이승현

Motifs and Structural Roles in Networks

Subnetworks

• Subnetworks은 subgraphs라고도 하며 네트워크의 부분 집합입니다.

• 이러한 부분 그래프들을 이용해 네트워크를 구분할 수 있습니다.

Case Example of Subgraphs

• 아래 예시는 노드 개수가 3일 때, 방향 그래프일 때 나올 수 있는 동형그래프가 아닌(non-isomorphoic) 모든 부분그래프입니다.

• 어플리케이션별로 자주 나타나는 부분그래프의 Z-score로 평가한 것입니다. 크기가 클수 자주 해당 패턴이 등장합니다.

  • Q. Z-score인데 크기가 왜 커야 좋은 걸까요?

Subgraphs, Motifs, and Graphlets

Network Motifs

• Network Motifs는 아래와 같은 특징이 있습니다.

  • Pattern : 부분그래프에서 발견됩니다.

  • Recurring : 많이 발생합니다.

  • Significant : 랜덤으로 발생시킨 네트워크 보다 더 자주 패턴이 발생합니다.

• 이러한 Motifs는 네트워크를 이해하고 연산의 작동을 예측하는데 도움을 줍니다.

자주 발생하는 패턴

높은 빈도로 발생하는 패턴

Significance of a Motif

• 무작위로 생성된 그래프보다 Motif는 네트워크에서 더 잘 표현됩니다. 이를 Overrepresented 되었다고 표현합니다.

• Z-score를 통해 우리는 통계적으로 significance를 지표화하 Motif를 계산할 수 있습니다.

• Network significance profile(SP) : 위 부분그래프 Z-score를 모아놓은 벡터의 크기가 1을 가지도록 정규합니다.

• SP는 subgraph의 상대적인 significance를 비교할수 있게 합니다.

• 다른 사이즈의 네트워크 비교에 효과적입니다.

• 일반적으로 더 큰 네트워크 일수록 높은 Z-score를 가집니다.

  • Q. Why?

핵심 : Z-score를 비교하려면 필연적으로 Random Graph를 생성해야합니다.

(G-real)은 주어지니까요!

Configuration Model - Random 그래프 만들기.

• 우리는 그래서 주어진 차수 Sequence로부터 무작위 그래프를 생성하는 것이 목표입니다.

• 실제 그래프 G와 무작위 그래프 G-rand는 같은 차수 Sequence를 가지고 있습니다.

Alternative for Spokes : Switching

• graph G가 주어지면 switching step이란걸 발생시킵니다.

• 두개의 간선을 무작위로 고르고 도착 정점을 교체해버립니다. (단 교체 할때, 자기를 가리키거나 두 정점간 간선이 여러개인 경우는 발생하지 않습니다.)

Detecting Motifs

• Swtiching 을 통해 발생한 Random graph와 실제 그래프에서 우리는 subgraph의 개수, N-real, N-rand를 세고 Z-score를 계산합니다.

• 높은 Z-score일수록 Subgraph i는 G 네트워크의 motif, 부분 패턴을 잘 나타냅니다.

Graphlets: Node feature vectors

Graphlets이란?

• 비동형 그래프인 서브그래프들입니다. 아래 그림을 예시로 들 수 있습니다.

Graphlet Degree Vector

• graphlets을 이용해서 노드를 기준으로한 부분 그래프 평가지표를 얻을 수 있습니다.

• graphlet degree vector(GDV)는 노드가 속해있는 graphlet을 셉니다.

• automorphism orbit은 부분 그래프의 대칭성 까지 고려하게 해줍니다.

정점 v를 기준으로 했을 때 a를 기준으로한 부분그래프는 2번, b 는 1번, c는 0번!, d는 2번이라는 것을 알 수 있습니다. c가 0번인게 헷갈릴 수 있지만 이는 b번에 속하는 모양이라는 것을 알 수 있습니다.

Finding Motifs and Graphlets

하지만 k 크기의 motifs/graphlets을 찾는 것은 2가지 문제점이 있습니다. 하나는 Eumerating, 즉 모든 K 크기의 부분그래프를 발생시키는 것과 각 서브그래프의 개수를 세는 Counting에서 NP-complete 문제라는 것입니다.

따라서 우리는 Network-centric한 접근으로 이를 어느 정도 해소할 수 있는 알고리즘을 사용할 수 있습니다. (완전탐색이 아니라 지식 기반의 휴리스틱한 접근이라는 뜻입니다.)

• Exact subgraph enumeration(ESU) [Wernicke 2006]

• Kavosh [Kashani et al. 2009]

• Subgraph sampling [Kashtan et al. 2004]

Exact Subgraph Enumeration(ESU)

• ESU 알고리즘은 node v로 시작해서 점점 정점의 집합에 다른 정점을 추가해 나가는 기법입니다.

• 재귀적 구조를 가지며 이러한 구조가 tree처럼 생겨 ESU-Tree 구조라고 합니다.

• 아래 예시를 보며 설명하겠습니다.

1~5번의 정점을 가진 그래프 G가 있고 우리는 ESU-Tree의 깊이를 k=3이라고 합시다. 처음 정점을 1-5번에 가질 수 있습니다. 우리는 1번을 선택했다고 합시다. 1번에서 갈 수 있는 정점은 3번이기 때문에 3번을 선택합니다. 따라서 정점의 집합 V는 {1,3}이 되고 V-extension은 3번에서 갈 수 있는 정점인 {2, 4, 5} 가 됩니다.

{2, 4, 5}에서 각각 점을 뽑아서 {1, 3}에 포함시키면 파생되는 그래프의 종류가 3가지인 것을 알 수 있습니다. 위 그림에서 주의할 점은 ({3}, {4, 5})를 보시면 3번 정점에서 왜 1,2번을 제외했냐라고 생각할 수도 있지만 이 알고리즘의 규칙상 {3}번보다 더 큰 {4, 5}만 고려합니다. 따라서 {4}, {5} 역시 가지수가 작습니다.

Use ESU-Tree to Count Subgraphs

ESU Tree 를 이용해서 부분 그래프를 만들면 동형 그래프를 셀 수 있습니다.

• 따라서 부분그래프의 개수를 구할 때는 위상학적으로 같은지 판별하는 과정이 필요한데 이때 Mckay's nauty algorithm을 사용합니다.

Structural Roles in Networks

Roles은 네트워크안에서 정점의 함수를 뜻합니다. 예시로는 생테계상에서의 종, 회사에서의 개인의 역할 정도로 들 수 있습니다.

Roles versus Groups in Networks

• Role은 네트워크 상에서 비슷한 위치, 기능을 하는 정점들의 collection, 자료구조입니다.

• 이는 group과 communites와 는 다릅니다. 이는 연결된 다른 노드들의 개념에 다 가깝습니다.

• 예를 들어 태양계로 비유하면 다른 은하계들의 항성들끼리는 같은 Role지만 같은 은하에 있지는 않으므로 같은 Community 라 보기 어렵습니다. 반대로 태양과 지구는 다른 은하에 비해 가까우므로 Community라 볼 수 있지만 각각 항성, 행성이기 때문에 같은 Role이라 보긴 어렵습니다.

Roles : More Formally

• Structural equivalence : 노드 u, v가 모든 다른 노드들에 대하여 같은 관계를 가지고 있으면 노드 u, v는 구조적으로 동등하다.

Discovering Structural Roles in Networks

Roles를 가지고 아래와 같은 Task를 할 수 있습니다.

Structural Role Discovery Method

• RoIX : 네트워크의 구조적인 role를 자동적으로 찾게 해줍니다. [Henderson, et al. 2011b]

  • 비지도 학습 접근법입니다.

  • 사전 지식이 필요하지 않습니다.

  • 각 정점들에 roles에 혼합된 역할을 할당합니다.

  • 간선들에 대하여 Scaling을 진행합니다.

• RoIX는 Node와 Node의 인접행렬로부터 재귀적으로 피처를 추출해 Node x Feature 행렬로 바꿔주고 이를 Role Extraction을 통해 Node x Role 행렬과 Role x Matrix 행렬로 바꿔줍니다.

Recursive Feature Extraction

• Recursive Feature Extraction은 인접행렬을 Node Feature 행렬로 바꿔 줍니다.

Neighborhood는 이웃한 정점간의 연결 패턴을 나타내고, Recursive 피처는 어떤 종류의 정점에 연결되어있는지를 나타냅니다.

• 따라서 새로운 recursive feature를 생성하기 위해 노드의 피처를 Aggregate, 모으는 것이 핵심입니다.

• Neighborhood Feature

  • Local Features : 정점들의 차수에 대한 특징

    • directed, in-out-degree, total degree

    • weighted feature versions

  • Egonet Features : node들의 egonet으로 계산합니다.

    • Egonet은 이웃한 정점으로부터의 부분그래프에 있는 정점들, 간선들을 포함합니다.

    • Ex) Egonet 간선에 있는지, Egonet 입구인지 아닌지.

mean과 sum 2가지 방식의 aggregation function을 사용해서 재귀적으로 늘려갑니다. 예를 들면 이웃한 정점으로부터 가중치가 없는 차수의 피처를 평균내서 새로운 피처에 추가합니다.이러한 방식의 피처 추가는 지수승으로 시간 복잡도가 증가하기 때문에 상관계수가 높은 피처만 고르는 등의 pruning technique이 필요합니다.

Application : Structural Similarity

Role distribution을 비교하면서 구조적인 유사도를 비교할 수 있습니다.