| 1 |
1
소셜 네트워크 서비스에 대응하는 그래프를 생성하는 그래프 생성부,생성된 상기 그래프에 포함되어 있는 정점들의 연결 관계에 기초하여 이웃한 두 정점의 친밀도를 산출하고, 이웃하지 않는 두 정점의 경로의 친밀도를 산출하는 친밀도 산출부,생성된 상기 그래프의 정점과 정점에 연결되어 있는 랜드마크의 최단 경로를 산출하는 전처리부,산출된 상기 최단 경로와 상기 최단 경로에 포함되어 있는 정점정보를 포함하는 정점별 경로정보를 저장하는 경로정보 저장부, 그리고상기 소셜 네트워크 서비스의 이용자로부터 질의가 수신되는 경우 상기 이용자에 대응하는 제1 정점과 상기 이용자의 목표 인물에 대응하는 제2 정점 사이의 경로에 대응하는 친밀도 산출 결과, 상기 제1 정점의 경로정보 및 상기 제2 정점의 경로정보에 기초하여 상기 제1 정점과 상기 제2 정점 사이의 최단 경로를 검색하는 경로 탐색부를 포함하는 근사 최단 경로 검색 시스템
|
| 2 |
2
제1항에서,상기 친밀도 산출부는, 아래의 수학식에 의해 이웃하는 정점 A와 정점 B의 친밀도를 산출하는 근사 최단 경로 검색 시스템
|
| 3 |
3
제1항에서,상기 전처리부는, 생성된 상기 그래프에 포함되어 있는 정점의 중심성 지수를 산출하고 산출된 중심성 지수에 기초하여 정점별 시드집합을 생성하며 생성된 상기 시드집합에서 하나의 랜드마크를 추출하여 정점과 추출된 상기 랜드마크 사이의 최단 경로를 산출하는 근사 최단 경로 검색 시스템
|
| 4 |
4
제1항에서,상기 경로 탐색부는, 저장되어 있는 상기 경로정보 중 출발지 정점에 대응하는 경로정보와 도착지 정점에 대응하는 경로정보에 기초하여 출발지 정점과 도착지 정점의 사이의 경로를 수집하고, 수집된 경로 중에서 친밀도가 최대인 경로를 검색하는 근사 최단 경로 검색 시스템
|
| 5 |
5
삭제
|
| 6 |
6
그래프 생성부에서 소셜 네트워크 서비스에 대응하는 그래프를 생성하는 단계,친밀도 산출부에서 생성된 상기 그래프에 포함되어 있는 정점들의 연결 관계에 기초하여 이웃한 두 정점의 친밀도를 산출하고, 이웃하지 않는 두 정점의 친밀도를 산출하는 단계,전처리부에서 생성된 상기 그래프에 포함되어 있는 정점의 중심성 지수를 산출하는 단계,상기 전처리부에서 산출된 상기 중심성 지수에 기초하여 정점별 시드집합을 생성하는 단계,상기 전처리부에서 생성된 상기 시드집합에서 하나의 랜드마크를 추출하고 정점과 추출된 상기 랜드마크 사이의 최단 경로를 산출하는 단계,경로정보 저장부에서 산출된 상기 최단 경로와 상기 최단 경로에 포함되어 있는 정점정보를 포함하는 정점별 경로정보를 저장하는 단계, 그리고경로 탐색부에서 저장되어 있는 상기 정점별 경로정보에 기초하여 두 개의 정점에 대응하는 최단 경로를 검색하는 단계를 포함하며,상기 최단 경로를 검색하는 단계는, 상기 소셜 네트워크 서비스의 이용자로부터 질의가 수신되는 경우 상기 이용자에 대응하는 제1 정점과 상기 이용자의 목표 인물에 대응하는 제2 정점 사이의 경로에 대응하는 친밀도 산출결과, 상기 제1 정점의 경로정보 및 상기 제2 정점의 경로정보에 기초하여 상기 제1 정점과 상기 제2 정점 사이의 최단 경로를 검색하는 근사 최단 경로 검색 방법
|
| 7 |
7
제6항에서,상기 최단 경로를 검색하는 단계는, 저장되어 있는 상기 정점별 경로정보 중 출발지 정점에 대응하는 경로정보와 도착지 정점에 대응하는 경로정보에 기초하여 출발지 정점과 도착지 정점의 사이의 경로를 수집하는 단계, 그리고 수집된 경로 중에서 친밀도가 최대인 경로를 검색하는 단계를 포함하는 근사 최단 경로 검색 방법
|
| 8 |
8
삭제
|
