Extract Subgraph Enumeration(ESU)

Motif와 graphlets을 찾기 위해선 두가지 문제를 해결해야한다

1. Enumerating : k-size의 subgraph를 만드는 것

2. Counting : subgraph를 세는 것

하지만 이러한 것을 푸는 과정에서 NP-Problem에 맞닥뜨린다. NP-Problem은 비결정론적 문제로 한마디로 푸는데 너무 오래 걸린다는 단점이 있다. 따라서 이러한 문제를 맞닥뜨리지 않기 위해선 notif 사이즈가 작아야한다.

## Extract Subgraph Enumeration(ESU)

이를 설명하기 전에 기본 개념을 잡고 가자

\( V_{subgraph} \) : 현재까지 찾아진 subgraph의 집합

\( V_{extraction} \) : 구조화된 subgraph에서 생성할 수 있는 후보집합

ESU의 idea는 node v에서 neighbor들을 추가하는 방식이다.

이 방식에 조건은 다음과 같다.

1. node별로 id를 부여하고, 자기 노드 id 보다 큰 값들만 \( V_{extraction} \)에 추가

2. 기존에 있는 id는 추가하지 않는다(무조건 새로운 node)

이렇게 추가하는 방식을 recursive하게 동작을 하고 depth k를 정해서 depth가 다다를 때 까지 동작한다.

예시를 보면서 알아보자

ESU

첫번째로 node1에 대해서 보자. node1과 연결된 자신보다 큰 아이디를 가진 노드는 3이다. 따라서 V_subgraph에 1이 추가가 되고, V_extension에 3이 추가가 된다. 다음 트리에서 {1,3} 은 input으로 들어간 값을 말하고, node3과 연결된 이웃 중에 큰 index를 가진 값을 고른다. 그림에선 2가 있었는데 3보다 작으므로 삭제가 되어야한다.

따라서 {1,3,4} 의 노드로 이루어진 subgraph 하나, {1,3,5}로 이루어진 subgraph 하나가 도출이 된다.

{2},{3}은 {1}{3}과 동일하므로 넘어간다.

{3}{4,5}는 3과 연결된 노드 중 가장 큰 것들이 4,5이므로 들어간다. 다음으로 input 값에 3,4,5가 있으므로 {3,4} 조합으로 넣는다. 왜냐하면 3,5로 하면 그래프가 안만들어지기 때문이다. 따라서 {3,4},{5}로 넣어서 다음과 같은 그래프를 생성하게 된다

따라서 이러한 과정을 거친 결과는 다음과 같다.

ESU 결과