Computer Theory and Application Laboratory

SW스타랩

(SW스타랩) NP-hard 그래프 문제를 위한 실용적인 알고리즘 프레임워크

 

총수행기간
  •  2018. 04. 01. – 2025. 12. 31.
과제목표
  •  NP-hard 그래프 문제들을 대규모 그래프에서 풀 수 있는 세계 최고 성능의 알고리즘들을 개발하고, 이를 기반으로 NP-hard 그래프 문제들에 특화된 공개 SW 프레임워크를 개발한다. 주요 성능지표인 알고리즘 수행시간에 있어서 현존 최고 성능의 알고리즘 대비 개선율 100% 이상을 달성한다. 이를 통해 국제 산업계와 학계를 선도하는 기술을 확보하고, NP-hard 그래프 문제에 대한 연구 및 응용 SW 개발의 오픈 생태계를 구축한다.
개발내용
  • 본 과제에서 개발하는 “NP-hard 그래프 문제를 위한 알고리즘 프레임워크”는 자료구조/툴, 그래프 알고리즘, 응용 SW의 세 층으로 구성된다 (그림 1).

 

그림 1. NP-hard 그래프 문제를 위한 알고리즘 프레임워크 구조

 

(1) 대규모 그래프 처리를 위한 자료구조 및 그래프 생성/변환/분석 툴을 개발하고
(2) 중요 NP-hard 그래프 문제들(subgraph isomorphism, supergraph search, graph homomorphism, diversified top-k subgraph querying, graph similarity search)에 대하여 세계 최고 성능의 알고리즘을 개발하고
(3) 이를 기반으로 소셜 네트워크 분석 SW, protein-protein interaction 네트워크 분석 SW, RDF 쿼리 처리 SW, 화합물 검색 SW를 개발한다.

  • 개발된 소스코드 및 라이브러리를 순차적으로 공개하여 NP-hard 그래프 문제를 위한 오픈 생태계를 형성한다.
과제수행방법
  • 본 과제의 최종 목표 달성을 위해 (1) 알고리즘 연구 그룹, (2) SW 및 툴 개발 그룹, (3) 오픈 생태계 구성 그룹의 세 그룹으로 연구진을 구성하고 상호 협력 하에 연구를 진행한다 (그림 2).

 

그림 2. 연차별 과제 수행 방법

 

  • 본 과제의 결과물은 (1) 알고리즘 SW, (2) 자료구조 및 그래프 생성/변환/분석 툴, (3) 응용 SW로 이를 순차적으로 공개하여 NP-hard 그래프 문제에 대한 오픈 생태계를 구축한다.
  • 본 과제에서 개발된 우수한 SW를 기반으로 국내외 연구그룹과 공동연구를 수행하고, 국내외 기업과 응용 SW 개발에 대한 협력연구를 진행하여 NP-hard 그래프 알고리즘 분야를 선도한다.
공개 SW R&D 체계 및 활성화 전략
  • 중요 NP-hard 그래프 문제들에 대하여 세계 최고 성능의 알고리즘을 개발하며, 개발 초기단계에서부터 GitHub, BitBucket 등의 오픈소스 툴을 사용하여 알고리즘 소스코드를 관리한다. 연구결과를 우수 국제학술회의 및 국제학술지에 발표하고, 알고리즘 소스코드 및 라이브러리를 순차적으로 공개하여 핵심 SW 기술을 선도한다.
  • 현재 NP-hard 그래프 알고리즘에 대한 연구가 소스코드를 공개하지 않고 실행파일만 주고 받는 폐쇄적 형태로 진행되고 있는 만큼, 본 과제에서 개발된 우수한 알고리즘의 소스코드가 공개된다면 그 파급력은 클 것으로 예상된다. 따라서 본 과제의 공개 SW 프레임워크의 우수성을 공개 SW 포럼에서 홍보하고, 개발된 공개 SW를 기반으로 국내외 연구그룹과의 공동연구 및 국내외 기업과의 협력 연구를 진행하여 오픈소스 커뮤니티를 활성화 할 것이다.
  • 본 과제에서 개발된 오픈 SW를 Apache 2.0 라이선스 형태로 배포하여 NP-hard 그래프 알고리즘 분야의 공개 SW 개발이 가속화 되도록 한다.

 

그림 3. SW 개발 추진 체계

 

인력양성 전략
  • NP-hard 그래프 문제에 대한 실용적인 알고리즘을 설계하고 개발하는 것은 계산이론 분야에 대한 깊은 지식과 통찰력을 요구한다. 또한 NP-hard 그래프 알고리즘을 사용하는 응용 SW를 개발하기 위해서는 이론 분야뿐 아니라 응용 분야에 대한 지식도 요구된다. 따라서 체계적이고 효율적으로 인력을 양성해야 하고, 이를 위해 학부생 단계에서부터 인턴십 프로그램을 제공한다. 학사/석사/박사 과정에서 체계적인 알고리즘 교과과정을 운영하고, 알고리즘 구현 교육을 실시한다. 각 연차별 목표에 해당하는 NP-hard 그래프 알고리즘의 최신 논문을 분석 및 토론하고, 다양한 응용 분야와 공개 SW에 대한 지식을 공유하는 세미나를 정기적으로 진행한다. 또한 다양한 응용 분야의 연구집단과의 공동연구를 통해서 이론 분야와 응용 분야에 경쟁력을 갖춘 핵심인력을 양성한다.
결과활용계획
  • NP-hard 그래프 알고리즘은 social network 분석, RDF 쿼리 처리, 생물정보학, 데이터베이스 등 다양한 분야의 응용 SW에 사용된다. NP-hard 그래프 알고리즘에 대한 핵심 SW기술을 선도하고, 기존의 폐쇄적 개발 구조를 벗어나 본 과제에서 개발하는 오픈 알고리즘 프레임워크로 전환하면 해당 분야에 혁신적인 변화가 있을 것으로 기대된다.NP-hard 그래프 알고리즘의 오픈 소스 라이브러리가 국내외 기업의 응용 SW 개발에 사용될 수 있도록 한다. 또한 오픈 소스 라이브러리를 통해서 NP-hard 그래프 알고리즘에 대한 연구 및 응용 생태계가 활성화 되도록 한다.
최종결과물
  • Subgraph isomorphism 알고리즘 (SW) : 수행 시간 개선율 1000%, 재귀 횟수 개선율 2000%, 견고성 개선율 5% 이상
  • Supergraph search 알고리즘 (SW) : 수행 시간 개선율 100%, 인덱스 크기 개선율 20%, 필터링 정확성 개선율 20% 이상
  • Subgraph isomorphism, Supergraph search에 대한 병렬/분산 알고리즘 (SW) : 병렬/분산 수행 시간 개선율 100% 이상
  • RDF 쿼리 처리 알고리즘 (SW) : 수행 시간 개선율 100%, 견고성 개선율 5% 이상
  • Diversified top-k subgraph querying 알고리즘 (SW) : 수행 시간 개선율 100%, 견고성 개선율 5%, 커버리지 개선율 10% 이상
  • Graph similarity search 알고리즘 (SW) : 개발 수행 시간 개선율 100%, 견고성 개선율 5%, 인덱스 크기 개선율 20% 이상
  • RDF 쿼리 처리, Diversified top-k subgraph querying, Graph similarity search에 대한 병렬/분산 알고리즘 (SW) : 병렬/분산 수행 시간 개선율 100% 이상
  • NP-hard 그래프 알고리즘 SW, 자료구조 및 그래프 관련 툴, 응용 SW(소셜 네트워크 분석 SW, protein-protein interaction 네트워크 분석 SW, RDF 쿼리 처리 SW, 화합물 검색 SW)를 통합 프레임워크 형태로 개발하고 소스코드와 라이브러리를 Apache 2.0 라이선스 형태로 배포
  • 그래프 알고리즘 및 응용 분야에 경쟁력을 갖춘 핵심 인력 학사 14명, 석사 14명, 박사 8명을 양성
경제적 파급효과
  • 대규모 그래프 분석에 대한 핵심 원천 기술 보유로 우리나라 산업의 위상을 제고한다.
  • NP-hard 그래프 알고리즘을 사용하여 다양한 응용 SW를 개발하는 광범위한 미래 시장을 선도한다.
  • NP-hard 그래프 알고리즘 분야의 전문 인력 배출로 관련 산업에서 우리나라의 기술경쟁력을 확보한다.

 

그림 4. 맺음말