Graphlets

## Graphlets

graphlets은 subgraph와 비슷한 개념이다. non-isomorphic subgraph이다.(모양에 초점). 

subgraph는 하나하나의 그래프를 본것이지만 graphlets은 subgraph의 집합이라고 생각하면 된다.

 

graphlets은 노드에 숫자가 써져있다. 이 말은 node의 관점에서 역할을 나눈다는 것이고 node의 역할 하나하나에 초점을 맞춘 것이다.

graphlets

반면에 motif는 building block 관점에서 정의한 거시적인 개념이 크다.(구조 중심)

 

graphlets과 motif는 모두 해당 그래프가 어떤 local structure를 기반으로 구성되어 있는지 판단할 수 있다는 것이다.

## Graph Degree Vector(GDV)

이는 노드 역할에 대한 vector를 나타낸다. 위 그림에서 있는 숫자들은 모두 각각의 노드들의 역할을 나타내는데 이 역할은 overlap 되어서 가질 수 있다. 즉, 0번 역할을 하는게 1번 역할을 할 수도 있다는 것이다.

따라서 \( node_i \) 가 해당 역할을 하면 += 1을 해주는 것이다.

예를 들어 벡터의 길이는 73개라 가정하고(5-node graphlets) 벡터를 나타내면 (2,1,....0,0,1) 이런 식으로 벡터가 구성될 수 있다는 것이다.

이러한 GDV는 각 node들의 역할이 얼마나 중첩되어 있는지를 알 수 있다.

GDV를 측정하는 방법에는 Automorphsim Orbit이 있다. 이 개념은 간단하다. 하나의 subgraph에서 node_i와 node_j 역할이 동일한지 측정하는 것이다.

Automorphsim Orbit

그래프 G에서 node_v의 역할에 대해서 봐보자. a,b,c,d 는 graphlet에 있는 각각의 노드 역할 번호이다.

따라서 이를 기반으로 역할이 비슷한 것을 추출하면 a:2, b:1, c:0, d:2 이런 식으로 나오게 된다

 

다음에는 Graphlet과 motif를 찾는 방법에 대해서 알아보겠다