| 1 |
1
원본 그래프(original graph)의 속성을 가지는 샘플 그래프를 얻기 위한 그래프 샘플링 장치에 있어서, 상기 그래프 샘플링 장치는: 샘플 그래프의 에지의 총수 보다 많은 에지를 갖는 부분 그래프를 원본 그래프로부터 추출하는 단계; 상기 원본 그래프 및 부분 그래프 중 하나 이상의 속성에 기초하여 상기 부분 그래프에서 제거될 에지를 선택하는 단계; 및선택된 에지를 제거하여 상기 샘플 그래프를 획득하는 단계를 수행하도록 구성된 그래프 샘플링 장치
|
| 2 |
2
제1항에 있어서, 상기 원본 그래프의 속성은 원본 그래프의 도수 및 군집 계수 중 하나 이상을 포함하는 것을 특징으로 하는 그래프 샘플링 장치
|
| 3 |
3
제1항에 있어서, 상기 부분 그래프를 원본 그래프로부터 추출하는 단계는, 샘플링 비율에 따라서 상기 원본 그래프에서 부분 그래프에 추출될 노드를 탐색하는 단계; 및 탐색된 노드 사이를 에지로 연결하여 상기 부분 그래프를 유도하는 단계(inducing)를 포함하는 것을 특징으로 하는 그래프 샘플링 장치
|
| 4 |
4
제3항에 있어서, 상기 추출될 노드를 탐색하는 단계는, 상기 원본 그래프 상에서 탐색을 시작할 현재 노드에 연결된 분기에서 특정 분기 방향의 노드를 탐색한 이후 다음 분기 방향으로 노드를 탐색하는 단계를 포함하되, 상기 특정 분기 방향의 노드는 현재 노드에 연결된 노드에서 가장 높은 도수를 갖는 노드인 것을 특징으로 하는 그래프 샘플링 장치
|
| 5 |
5
제1항에 있어서, 상기 제거될 에지를 선택하는 단계는, 상기 부분 그래프에 포함된 에지에 대한 에지 가중치를 산출하는 단계; 상기 에지 가중치에 기초하여 군집 계수의 감소 경향에 기초한 제1 그룹 및 제2 그룹을 결정하는 단계; 및제거될 에지를 선택하기 위해, 상기 부분 그래프의 군집 계수와 샘플 그래프의 군집 계수에 기초하여 제1 그룹 또는 제2 그룹에서 제거될 에지를 선택하는 단계를 포함하는 그래프 샘플링 장치
|
| 6 |
6
제5항에 있어서, 상기 제1 그룹은 제2 그룹의 에지를 제거하는 경우 부분 그래프의 군집 계수가 보다 많이 감소되는 에지를 포함하는 것을 특징으로 하는 그래프 샘플링 장치
|
| 7 |
7
제5항에 있어서, 제1 에지 보다 큰 에지 가중치를 갖는 제2 에지를 제거할 경우, 제1 에지를 제거하는 경우 보다 부분 그래프의 군집 계수의 감소량이 큰 것을 특징으로 하는 그래프 샘플링 장치
|
| 8 |
8
제7항에 있어서, 상기 부분 그래프에서 닫힌 삼중 구조(closed triplet)를 형성하게 하는 제1 및 제2 노드를 연결하는 에지에 대한 에지 가중치는 다음의 수학식에 의해 산출되며, [수학식] 여기서, k는 부분 그래프의 노드의 총수를 나타내는 것을 특징으로 하는 그래프 샘플링 장치
|
| 9 |
9
제5항에 있어서, 상기 부분 그래프의 군집 계수의 감소 상태를 판단하는 단계는, 상기 부분 그래프의 실시간 군집 계수 및 예측된 군집 계수를 산출하는 단계; 실시간 값과 예측된 값을 비교하여, 상기 부분 그래프의 실시간 군집 계수가 예측된 군집 계수 보다 크고 상기 부분 그래프의 군집 계수가 원본 그래프의 군집 계수 보다 큰 경우, 군집 계수의 감소가 보다 큰 에지 가중치를 갖는 에지를 제거 대상으로 선택하는 단계; 실시간 값과 예측된 값을 비교하여, 상기 부분 그래프의 실시간 군집 계수가 예측된 군집 계수 보다 작거나, 또는 상기 부분 그래프의 군집 계수가 원본 그래프의 군집 계수 보다 작은 경우, 군집 계수의 감소가 보다 작은 에지 가중치를 갖는 에지를 제거 대상으로 선택하는 단계;를 포함하는 것을 특징으로 하는 그래프 샘플링 장치
|
| 10 |
10
제9항에 있어서,상기 다음 부분 그래프의 군집 계수의 예측은 다음의 수학식에 의해 산출되며, [수학식] 여기서, edel은 이미 제거된 에지의 수를 나타내고, CCorg는 원본 그래프의 군집 계수를 나타내며, slope는 다음의 수학식으로 표현되며, [수학식] 여기서, eextra는 제거될 에지의 총수를 나타내는 것을 특징으로 하는 그래프 샘플링 장치
|
| 11 |
11
제1항에 있어서, 상기 에지를 제거하는 단계에서 제거되는 에지는 하나이며, 초기 부분 그래프의 에지의 총수와 상기 이전 샘플 그래프의 에지의 총수 간의 차이에 기초하여 상기 제거하는 단계를 반복하는 단계를 더 수행하도록 구성된 그래프 샘플링 장치
|
| 12 |
12
제1항에 있어서, 상기 반복하는 단계는,제거된 에지의 엔드 노드 및 엔드 노드의 공통된 친구 노드의 지역 군집 계수(local clustering coefficient)를 산출하는 단계; 상기 지역 군집 계수 및 에지가 제거되기 이전의 군집 계수에 기초하여 선택된 에지가 제거된 부분 그래프의 군집 계수를 산출하는 단계; 및 상기 부분 그래프의 군집 계수를 에지가 제거된 부분 그래프의 군집 계수로 업데이트하는 단계를 포함하는 것을 특징으로 하는 그래프 샘플링 장치
|
