| 1 |
1
간선에 정점들 간 관계를 나타내는 라벨이 부여된 그래프에서, 정점들 간 관련도를 측정하는 방법에 있어서,상기 그래프에 포함되는 정점들 사이를 서퍼(surfer)가 이동함에 따라 서퍼의 라벨이 변경되는 규칙을 학습하는 단계;상기 그래프의 인접 행렬을 각각의 간선 라벨에 대해서 정규화하는 단계; 및상기 규칙을 학습한 결과와 상기 정규화된 인접 행렬을 이용하고, 반복적 기법을 통해 점수 행렬을 산출하는 단계를 포함하며,상기 서퍼의 라벨이 변경되는 규칙을 학습하는 단계는,상기 그래프로부터 라벨 전이 삼각형들을 추출하고, 상기 추출된 라벨 전이 삼각형들을 이용하여 라벨 전이 확률을 산출하는 것을 특징으로 하며,상기 라벨 전이 삼각형은 세 개의 정점들과, 상기 정점들을 서로 연결하며 각각 라벨이 부여된 간선들로 이루어진 단위 그래프이며,상기 라벨 전이 확률은 제1 라벨을 갖는 서퍼가 제2 라벨이 부여된 간선을 따라 이동할 경우 상기 서퍼의 라벨이 제3 라벨로 변경될 확률을 의미하는, 방법
|
| 2 |
2
제1항에 있어서,상기 서퍼의 라벨이 변경되는 규칙을 학습하는 단계는,상기 그래프의 간선에 부여된 라벨을 반영한 인접 행렬 및 라벨 가중치를 입력받는 단계;상기 그래프로부터 상기 라벨 전이 삼각형들을 추출하여 열거하는 단계; 및상기 라벨 전이 삼각형과 상기 라벨 가중치를 기반으로 최대 가중 우도 추정을 적용하여 각각의 간선 라벨에 대한 라벨 전이 확률 행렬을 산출하는 단계를 포함하는 것을 특징으로 하는 방법
|
| 3 |
3
제2항에 있어서,상기 정규화하는 단계는,상기 그래프의 간선에 부여된 라벨을 반영한 인접 행렬을 입력받는 단계;각각의 간선 라벨에 대해서 준-인접 행렬을 산출하는 단계;상기 인접 행렬로부터 연결 차수 행렬을 산출하는 단계; 및상기 연결 차수 행렬을 이용하여 각각의 간선 라벨에 대한 준-행-정규화 행렬을 산출하는 단계를 포함하는 것을 특징으로 하는 방법
|
| 4 |
4
제3항에 있어서,상기 반복적 기법을 통해 점수 행렬을 산출하는 단계는,상기 각각의 간선 라벨에 대한 준-행-정규화 행렬 및 라벨 전이 확률 행렬, 시작 정점, 재시작 확률 및 수렴 문턱값을 입력받는 단계;상기 시작 정점에 따라서 시작 행렬을 생성하고, 상기 점수 행렬을 상기 시작 행렬로 초기화하는 단계;상기 준-행-정규화 행렬, 상기 라벨 전이 확률 행렬 및 상기 시작 행렬을 이용하여 점수 행렬 계산을 반복적으로 수행하는 단계;상기 수렴 문턱값을 기준으로 상기 점수 행렬이 수렴하는지 여부를 판단하는 단계; 및상기 점수 행렬이 수렴한다면, 수렴된 점수 행렬을 출력하는 단계를 포함하는 것을 특징으로 하는 방법
|
| 5 |
5
제1항에 기재된 방법을 수행하는 프로그램이 기록된 컴퓨터 판독 가능한 기록 매체
|
| 6 |
6
관련도 측정 장치에 의해 수행되며, 제1항에 기재된 방법을 수행하기 위해 매체에 저장된 컴퓨터 프로그램
|
| 7 |
7
간선에 정점들 간 관계를 나타내는 라벨이 부여된 그래프에서, 정점들 간 관련도를 측정하기 위한 장치에 있어서,관련도 측정의 대상이 되는 그래프에 대한 정보를 수신하기 위한 통신부;상기 그래프의 정점들 간 관련도를 측정하기 위한 프로그램이 저장되는 저장부; 및상기 프로그램을 실행함으로써 그래프의 정점들 간 관련도를 측정하는 제어부를 포함하며,상기 제어부는, 상기 그래프에 포함되는 정점들 사이를 서퍼(surfer)가 이동함에 따라 서퍼의 라벨이 변경되는 규칙을 학습하고, 상기 그래프의 인접 행렬을 각각의 간선 라벨에 대해서 정규화하고, 상기 규칙을 학습한 결과와 상기 정규화된 인접 행렬을 이용하고 반복적 기법을 통해 점수 행렬을 산출하며,상기 제어부는 상기 서퍼의 라벨이 변경되는 규칙을 학습함에 있어서, 상기 그래프로부터 라벨 전이 삼각형들을 추출하고, 상기 추출된 라벨 전이 삼각형들을 이용하여 라벨 전이 확률을 산출하는 것을 특징으로 하며,상기 라벨 전이 삼각형은 세 개의 정점들과, 상기 정점들을 서로 연결하며 각각 라벨이 부여된 간선들로 이루어진 단위 그래프이며,상기 라벨 전이 확률은 제1 라벨을 갖는 서퍼가 제2 라벨이 부여된 간선을 따라 이동할 경우 상기 서퍼의 라벨이 제3 라벨로 변경될 확률을 의미하는, 장치
|
| 8 |
8
제7항에 있어서,상기 제어부는,상기 그래프의 간선에 부여된 라벨을 반영한 인접 행렬 및 라벨 가중치를 입력받으면, 상기 그래프로부터 상기 라벨 전이 삼각형들을 추출하여 열거하고, 상기 라벨 전이 삼각형과 상기 라벨 가중치를 기반으로 최대 가중 우도 추정을 적용하여 각각의 간선 라벨에 대한 라벨 전이 확률 행렬을 산출하는 것을 특징으로 하는 장치
|
| 9 |
9
제8항에 있어서,상기 제어부는,상기 그래프의 간선에 부여된 라벨을 반영한 인접 행렬을 입력받으면, 각각의 간선 라벨에 대해서 준-인접 행렬을 산출한 후, 상기 인접 행렬로부터 연결 차수 행렬을 산출하고, 상기 연결 차수 행렬을 이용하여 각각의 간선 라벨에 대한 준-행-정규화 행렬을 산출하는 것을 특징으로 하는 장치
|
| 10 |
10
제9항에 있어서,상기 제어부는,상기 각각의 간선 라벨에 대한 준-행-정규화 행렬 및 라벨 전이 확률 행렬, 시작 정점, 재시작 확률 및 수렴 문턱값을 입력받으면, 상기 시작 정점에 따라서 시작 행렬을 생성하고, 상기 점수 행렬을 상기 시작 행렬로 초기화한 후, 상기 준-행-정규화 행렬, 상기 라벨 전이 확률 행렬 및 상기 시작 행렬을 이용하여 점수 행렬 계산을 반복적으로 수행하여, 상기 수렴 문턱값을 기준으로 상기 점수 행렬이 수렴한다면 수렴된 점수 행렬을 출력하는 것을 특징으로 하는 장치
|
