1 |
1
그래프 상에 존재하는 노드들을 각 노드의 차수 순으로 정렬하여 상기 정렬된 노드들 중에서 차수가 높은 k개의 노드를 허브 노드로 추출하는 단계;상기 추출한 허브 노드가 엣지로 연결된 경우, 상기 엣지로 연결된 허브 노드 간의 차수 변화를 고려하여 차수가 높은 순으로 허브 노드를 제거하는 단계;상기 제거한 허브 노드로부터 분해되는 스포크(spoke) 노드를 식별하는 단계;상기 제거한 허브 노드의 차수를 고려하여 그래프 상에 상기 스포크 노드를 배열하는 단계; 및상기 스포크 노드를 배열한 그래프의 압축을 처리하는 단계;를 포함하는 그래프 압축 처리 방법
|
2 |
2
제1항에 있어서,상기 제거하는 단계는,상기 추출한 허브 노드 중에서 어느 하나의 허브 노드를 제거할 경우, 상기 어느 하나의 허브 노드와 연결된 허브 노드의 차수 변화를 고려하여 허브 노드의 제거 순서를 결정하고, 상기 결정한 제거 순서를 기초로 허브 노드를 제거하는 그래프 압축 처리 방법
|
3 |
3
제1항에 있어서,상기 배열하는 단계는, 상기 제거한 허브 노드의 차수, 및 상기 스포크 노드의 크기를 고려하여 그래프 상에 상기 스포크 노드를 배열하는 그래프 압축 처리 방법
|
4 |
4
제1항에 있어서,상기 식별하는 단계는,상기 제거한 허브 노드로부터 분해되는 스포크 노드와 자이언트 커넥티드 컴퍼넌트 노드(Giant Connected-Component, GCC)를 식별하고, 상기 자이언트 커넥티드 컴퍼넌트 노드 내에서의 허브 노드를 제거하는 단계를 더 포함하는 그래프 압축 처리 방법
|
5 |
5
제1항에 있어서,상기 식별하는 단계는,상기 허브 노드로부터 분해되는 스포크 노드와 자이언트 커넥티드 컴퍼넌트 노드를 식별하고, 상기 자이언트 커넥티드 컴퍼넌트 노드 내의 노드의 개수가 상기 제거한 허브 노드의 개수보다 작거나 또는 동일할 때까지 상기 자이언트 커넥티드 컴퍼넌트 노드 내에서의 허브 노드를 제거하는 단계를 더 포함하는 그래프 압축 처리 방법
|
6 |
6
그래프 상에 존재하는 노드의 차수를 이용하여 추출한 허브 노드를 포함하는 허브 노드 집합을 생성하는 단계;상기 허브 노드 집합에 포함된 허브 노드 간의 연결을 고려하여 허브 노드의 제거 순서를 계산하는 단계;상기 제거 순서에 따라 상기 허브 노드 집합에 포함된 허브 노드를 제거하는 단계;상기 제거한 허브 노드로부터 분해되는 스포크 노드의 배열 순서를 결정하는 단계; 및상기 배열 순서에 따라 스포크 노드를 배열한 그래프의 압축을 처리하는 단계를 포함하는 그래프 압축 처리 방법
|
7 |
7
제6항에 있어서,상기 계산하는 단계는,상기 허브 노드 집합에 포함된 어느 하나의 허브 노드를 제거하는 경우, 상기 어느 하나의 허브 노드와 연결된 허브 노드의 차수 변화를 고려하여 허브 노드의 제거 순서를 계산하는 그래프 압축 처리 방법
|
8 |
8
제6항에 있어서,상기 계산하는 단계는,상기 허브 노드 집합에 포함된 허브 노드 간의 연결, 및 허브 노드의 차수를 고려하여 허브 노드의 제거 순서를 계산하는 그래프 압축 처리 방법
|
9 |
9
제6항에 있어서,상기 결정하는 단계는,상기 제거한 허브 노드로부터 분해되는 스포크 노드와 자이언트 커넥티드 컴퍼넌트 노드를 식별하고, 상기 자이언트 커넥티드 컴퍼넌트 노드 내에서의 허브 노드를 제거하는 단계를 더 포함하는 그래프 압축 처리 방법
|
10 |
10
제6항에 있어서,상기 결정하는 단계는,상기 제거한 허브 노드로부터 분해되는 스포크 노드와 자이언트 커넥티드 컴퍼넌트 노드를 식별하고, 상기 자이언트 커넥티드 컴퍼넌트 노드 내의 노드의 개수가 상기 제거한 허브 노드의 개수보다 작거나 또는 동일할 때까지 상기 자이언트 커넥티드 컴퍼넌트 노드 내에서의 허브 노드를 제거하는 단계를 더 포함하는 그래프 압축 처리 방법
|
11 |
11
그래프 상에 존재하는 노드들을 각 노드의 차수 순으로 정렬하여 상기 정렬된 노드들 중에서 차수가 높은 k개의 노드를 허브 노드로 추출하는 추출부;상기 추출한 허브 노드가 엣지로 연결된 경우, 상기 엣지로 연결된 허브 노드 간의 차수 변화를 고려하여 차수가 높은 순으로 허브 노드를 제거하는 제거부;상기 제거한 허브 노드로부터 분해되는 스포크(spoke) 노드를 식별하는 식별부;상기 제거한 허브 노드의 차수를 고려하여 상기 스포크 노드를 배열하는 배열부; 및상기 스포크 노드를 배열한 그래프의 압축을 처리하는 처리부;를 포함하는 그래프 압축 처리 장치
|
12 |
12
제11항에 있어서,상기 제거부는,상기 추출한 허브 노드 중에서 어느 하나의 허브 노드를 제거할 경우, 상기 어느 하나의 허브 노드와 연결된 허브 노드의 차수 변화를 고려하여 허브 노드의 제거 순서를 결정하고, 상기 결정한 제거 순서를 기초로 허브 노드를 제거하는 그래프 압축 처리 장치
|
13 |
13
그래프 상에 존재하는 노드의 차수를 이용하여 추출한 허브 노드를 포함하는 허브 노드 집합을 생성하는 생성부;상기 허브 노드 집합에 포함된 허브 노드 간의 연결을 고려하여 허브 노드의 제거 순서를 계산하는 계산부;상기 제거 순서에 따라 상기 허브 노드 집합에 포함된 허브 노드를 제거하는 제거부;상기 제거한 허브 노드로부터 분해되는 스포크 노드의 배열 순서를 결정하는 결정부; 및상기 배열 순서에 따라 스포크 노드를 배열한 그래프의 압축을 처리하는 처리부를 포함하는 그래프 압축 처리 장치
|
14 |
14
제13항에 있어서,상기 계산부는,상기 허브 노드 집합에 포함된 어느 하나의 허브 노드를 제거하는 경우, 상기 어느 하나의 허브 노드와 연결된 허브 노드의 차수 변화를 고려하여 허브 노드의 제거 순서를 계산하는 그래프 압축 처리 장치
|