| 1 |
1
대용량 그래프 데이터베이스에서 링크를 예측하는 방법에 있어서,상기 대용량 그래프 데이터베이스는 다수개의 그래프 그룹으로 분리되어 분산되어 있으며,상기 그래프 그룹을 구성하는 각 버텍스를 기준 버텍스로 하여 상기 기준 버텍스에 인접한 인접 버텍스로 상기 기준 버텍스의 에지 차수를 에지 차수 관리부가 송신하는 단계;상기 인접 버텍스에서 계산된 상기 기준 버텍스와 상기 인접 버텍스 사이의 인접 유사도를 확장 유사도 계산부가 수신하는 단계;상기 인접 버텍스로부터 비인접 유사도 및 시작 버텍스 식별자를 구비하는 비인접 메시지를 상기 기준 버텍스에서 수신하는 경우, 상기 비인접 유사도와 상기 인접 유사도를 곱하여 상기 비인접 유사도의 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도를 상기 확장 유사도 계산부가 계산하는 단계; 및상기 확장 유사도의 크기에 기초하여 상기 기준 버텍스에 링크로 연결할 시작 버텍스를 예측부가 예측하는 단계를 포함하는 것을 특징으로 하는 링크 예측 방법
|
| 2 |
2
제 1 항에 있어서, 상기 링크 예측 방법에서상기 인접 버텍스로부터 비인접 메시지를 더 이상 수신하지 않을 때까지 상기 비인접 유사도의 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도를 계산하는 것을 특징으로 하는 링크 예측 방법
|
| 3 |
3
제 2 항에 있어서, 동일한 시작 버텍스와 상기 기준 버텍스 사이에 다수의 확장 유사도가 계산되는 경우, 상기 동일한 시작 버텍스와 상기 기준 버텍스 사이의 다수 확장 유사도 중에서 가장 높은 확장 유사도를 상기 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도로 결정하는 것을 특징으로 하는 링크 예측 방법
|
| 4 |
4
제 2 항에 있어서, 상기 인접 유사도는 상기 인접 버텍스에서 상기 기준 버텍스의 차수와 상기 인접 버텍스의 차수로부터 계산되는 것을 특징으로 하는 링크 예측 방법
|
| 5 |
5
제 4 항에 있어서, 상기 인접 버텍스(vn)와 상기 기준 버텍스(vs) 사이의 상기 인접 유사도(S(n))는 아래의 수학식(1)에 의해 계산되며,[수학식 1]여기서 deg(vi)는 버텍스(vi)의 에지 차수인 것을 특징으로 하는 링크 예측 방법
|
| 6 |
6
제 4 항에 있어서, 상기 비인접 유사도는상기 시작 버텍스로부터 상기 인접 버텍스까지 순차적으로 인접하고 있는 버텍스 사이의 인접 유사도를 곱하여 계산되는 것을 특징으로 하는 링크 예측 방법
|
| 7 |
7
제 1 항 내지 제 6 항 중 어느 한 항에 있어서,상기 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도에 기초하여 상기 기준 버텍스의 인접 버텍스를 제외하고 가장 큰 확장 유사도를 가지는 시작 버텍스를 상기 기준 버텍스에 링크로 연결할 시작 버텍스로 예측하는 것을 특징으로 하는 링크 예측 방법
|
| 8 |
8
대용량 그래프 데이터베이스에서 링크를 예측하는 장치에 있어서,다수개의 그래프 그룹으로 분리되어 있는 상기 대용량 그래프 데이터베이스 중 1개의 그래프 그룹이 분산 저장되어 있는 그래프 데이터베이스; 및예측 모듈을 포함하며상기 예측 모듈은기준 버텍스에 인접한 인접 버텍스로 상기 기준 버텍스의 에지 차수를 송신하고 상기 인접 버텍스로부터 상기 인접 버텍스의 에지 차수를 수신하는 에지 차수 관리부;상기 인접 버텍스의 에지 차수와 상기 기준 버텍스의 에지 차수에 기초하여 상기 인접 버텍스와 상기 기준 버텍스 사이의 인접 유사도를 계산하는 인접 유사도 계산부;상기 인접 버텍스로부터 수신한 비인접 유사도 및 시작 버텍스 식별자에 기초하여 상기 비인접 유사도와 상기 인접 유사도를 곱하여 상기 비인접 유사도의 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도를 계산하는 확장 유사도 계산부; 및상기 확장 유사도의 크기에 기초하여 상기 기준 버텍스에 링크로 연결할 시작 버텍스를 예측하는 예측부를 포함하는 것을 특징으로 하는 링크 예측 장치
|
| 9 |
9
삭제
|
| 10 |
10
제 8 항에 있어서, 상기 확장 유사도 계산부는상기 인접 버텍스로부터 비인접 메시지를 더 이상 수신하지 않을 때까지 상기 비인접 유사도의 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도를 계산하는 것을 특징으로 하는 링크 예측 장치
|
| 11 |
11
제 10 항에 있어서, 상기 확장 유사도 계산부는동일한 시작 버텍스와 상기 기준 버텍스 사이에 다수의 확장 유사도가 계산되는 경우, 상기 동일한 시작 버텍스와 상기 기준 버텍스 사이에 다수의 확장 유사도 중에서 가장 높은 확장 유사도를 상기 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도로 결정하는 것을 특징으로 하는 링크 예측 장치
|
| 12 |
12
제 10 항에 있어서, 상기 인접 유사도는 상기 인접 버텍스에서 상기 기준 버텍스의 차수와 상기 인접 버텍스의 차수로부터 계산되는 것을 특징으로 하는 링크 예측 장치
|
| 13 |
13
제 12 항에 있어서, 상기 인접 버텍스(vn)와 상기 기준 버텍스(vs) 사이의 상기 인접 유사도(S(n))는 아래의 수학식(2)에 의해 계산되며,[수학식 2]여기서 deg(vi)는 버텍스(vi)의 에지 차수인 것을 특징으로 하는 링크 예측 장치
|
| 14 |
14
제 12 항에 있어서, 상기 비인접 유사도는상기 시작 버텍스로부터 상기 인접 버텍스까지 순차적으로 인접하고 있는 버텍스 사이의 인접 유사도를 곱하여 계산되는 것을 특징으로 하는 링크 예측 장치
|
| 15 |
15
제 8 항, 제 10 항 내지 제 14 항 중 어느 한 항에 있어서,상기 시작 버텍스와 상기 기준 버텍스 사이의 확장 유사도에 기초하여 상기 기준 버텍스의 인접 버텍스를 제외하고 가장 큰 확장 유사도를 가지는 시작 버텍스를 상기 기준 버텍스에 링크로 연결할 시작 버텍스로 예측하는 것을 특징으로 하는 링크 예측 장치
|
