소셜 네트워크에서 두 사람을 연결하는 근사 최단 경로 검색 시스템 및 방법

출원번호 : 10-2017-0003114 (출원일: 2017-01-09)

등록번호 : 10-1858178 (등록일: 2018-05-09)

특허권자 : 충남대학교산학협력단

요약 : 본 발명은 소셜 네트워크에서 두 사람을 연결하는 근사 최단 경로 검색 시스템 및 방법에 관한 것으로, 본 발명의 실시예에 따른 근사 최단 경로 검색 시스템은 소셜 네트워크 서비스에 대응하는 그래프를 생성하는 그래프 생성부, 생성된 그래프에서 이웃한 두 정점의 친밀도를 산출하는 친밀도 산출부, 생성된 그래프의 정점과 정점에 연결되어 있는 랜드마크의 최단 경로를 산출하는 전처리부, 산출된 최단 경로와 최단 경로에 포함되어 있는 정점정보를 포함하는 정점별 경로정보를 저장하는 경로정보 저장부, 그리고 저장되어 있는 정점별 경로정보에 기초하여 두 개의 정점에 대응하는 최단 경로를 검색하는 경로 탐색부를 포함한다.

대표청구항 : 소셜 네트워크 서비스에 대응하는 그래프를 생성하는 그래프 생성부,생성된 상기 그래프에 포함되어 있는 정점들의 연결 관계에 기초하여 이웃한 두 정점의 친밀도를 산출하고, 이웃하지 않는 두 정점의 경로의 친밀도를 산출하는 친밀도 산출부,생성된 상기 그래프의 정점과 정점에 연결되어 있는 랜드마크의 최단 경로를 산출하는 전처리부,산출된 상기 최단 경로와 상기 최단 경로에 포함되어 있는 정점정보를 포함하는 정점별 경로정보를 저장하는 경로정보 저장부, 그리고상기 소셜 네트워크 서비스의 이용자로부터 질의가 수신되는 경우 상기 이용자에 대응하는 제1 정점과 상기 이용자의 목표 인물에 대응하는 제2 정점 사이의 경로에 대응하는 친밀도 산출 결과, 상기 제1 정점의 경로정보 및 상기 제2 정점의 경로정보에 기초하여 상기 제1 정점과 상기 제2 정점 사이의 최단 경로를 검색하는 경로 탐색부를 포함하는 근사 최단 경로 검색 시스템.

상세링크 : http://newsd.wips.co.kr/wipslink/api/dkrdshtm.wips?skey=3518202001156