컴퓨터 장치에서 실행되는 그래프 매칭(graph matching) 방법에 있어서,상기 컴퓨터 장치는 메모리에 포함된 컴퓨터 판독가능한 명령들을 실행하도록 구성된 적어도 하나의 프로세서를 포함하고,상기 그래프 매칭 방법은,상기 적어도 하나의 프로세서에 의해, 커뮤니티 구조(community structure)를 이용한 파티션 트리(partition tree)를 기초로 저차 다항 시간(low-order polynomial time) 내 그래프 매칭을 수행하는 단계를 포함하는 그래프 매칭 방법.

제1항에 있어서,상기 수행하는 단계는,커뮤니티 간 주어진 정보의 통계적 계산을 통해 상기 파티션 트리를 만드는 단계를 포함하는 그래프 매칭 방법.

제1항에 있어서,상기 수행하는 단계는,한 커뮤니티와 다른 커뮤니티 간의 선(edge)의 수를 나타내는 차수(degree) 정보를 이용하여 상기 파티션 트리를 만드는 단계를 포함하는 그래프 매칭 방법.

제1항에 있어서,상기 수행하는 단계는,커뮤니티 정보를 이용하여 시그니처 벡터(signature vector)를 생성하는 단계;상기 시그니처 벡터에 기초한 노드 간의 유사도를 바탕으로 1차 매칭을 수행하는 단계; 및상기 1차 매칭에서 매칭된 노드 쌍을 시드(seed)로 활용하여 매칭이 안된 노드들을 매칭하는 단계를 포함하는 그래프 매칭 방법.

제1항에 있어서,상기 수행하는 단계는,상기 파티션 트리를 통해 노드 간의 유사도를 측정하여 상기 유사도로 선형 할당 문제(linear assignment problem)를 풀어 노드들을 매칭하는 단계를 포함하는 그래프 매칭 방법.

제5항에 있어서,상기 매칭하는 단계는,한 커뮤니티에 속한 노드들을 대상으로 노드 간의 유사도를 기초로 1차 매칭을 수행하는 단계; 및상기 1차 매칭에 따른 매칭 정보를 이용하여 상기 1차 매칭에서 매칭이 안된 노드를 매칭하는 2차 매칭을 수행하는 단계를 포함하는 그래프 매칭 방법.

제6항에 있어서,상기 2차 매칭을 수행하는 단계는,상기 1차 매칭을 통한 노드 쌍에 대한 업데이트 과정을 반복하는 정제 매칭(refinement matching)을 수행하는 단계를 포함하는 그래프 매칭 방법.

제6항에 있어서,상기 2차 매칭을 수행하는 단계는,상기 1차 매칭에서 매칭이 안된 노드를 대상으로 상기 1차 매칭에서 매칭된 노드 쌍을 시드로 활용하여 같은 거리에 있는 시드의 개수에 대한 통계적 계산을 통해 시드 매칭(seeded matching)을 수행하는 단계를 포함하는 그래프 매칭 방법.

그래프 매칭 방법을 컴퓨터에 실행시키기 위해 컴퓨터 판독가능한 기록 매체에 저장되는 컴퓨터 프로그램에 있어서,상기 그래프 매칭 방법은,커뮤니티 구조(community structure)를 이용한 파티션 트리(partition tree)를 기초로 저차 다항 시간(low-order polynomial time) 내 그래프 매칭을 수행하는 단계를 포함하는, 컴퓨터 프로그램.

컴퓨터 장치에 있어서,메모리에 포함된 컴퓨터 판독가능한 명령들을 실행하도록 구성된 적어도 하나의 프로세서를 포함하고,상기 적어도 하나의 프로세서는,커뮤니티 구조(community structure)를 이용한 파티션 트리(partition tree)를 기초로 저차 다항 시간(low-order polynomial time) 내 그래프 매칭을 수행하는 과정을 처리하는 컴퓨터 장치.

제10항에 있어서,상기 적어도 하나의 프로세서는,한 커뮤니티와 다른 커뮤니티 간에 주어진 정보의 통계적 계산을 통해 상기 파티션 트리를 만드는 것을 특징으로 하는 컴퓨터 장치.

제10항에 있어서,상기 적어도 하나의 프로세서는,상기 파티션 트리를 통해 노드 간의 유사도를 측정하여 상기 유사도로 선형 할당 문제(linear assignment problem)를 풀어 노드들을 매칭하는 것을 특징으로 하는 컴퓨터 장치.

제12항에 있어서,상기 적어도 하나의 프로세서는,한 커뮤니티에 속한 노드들을 대상으로 노드 간의 유사도를 기초로 1차 매칭을 수행하고,상기 1차 매칭에 따른 매칭 정보를 이용하여 상기 1차 매칭에서 매칭이 안된 노드를 매칭하는 2차 매칭을 수행하는 것을 특징으로 하는 컴퓨터 장치.

제13항에 있어서,상기 적어도 하나의 프로세서는,상기 1차 매칭을 통한 노드 쌍에 대한 업데이트 과정을 반복하는 정제 매칭(refinement matching)을 수행하는 것을 특징으로 하는 컴퓨터 장치.

제13항에 있어서,상기 적어도 하나의 프로세서는,상기 1차 매칭에서 매칭이 안된 노드를 대상으로 상기 1차 매칭에서 매칭된 노드 쌍을 시드로 활용하여 같은 거리에 있는 시드의 개수에 대한 통계적 계산을 통해 시드 매칭(seeded matching)을 수행하는 것을 특징으로 하는 컴퓨터 장치.