• 전체
  • 전자/전기
  • 통신
  • 컴퓨터
닫기

사이트맵

Loading..

Please wait....

국내 학회지

홈 홈 > 연구문헌 > 국내 학회지 > 데이터베이스 연구회지(SIGDB)

데이터베이스 연구회지(SIGDB)

Current Result Document : 1 / 8   다음건 다음건

한글제목(Korean Title) 대용량 그래프에서 효율적인 동적 그래프 요약 기법
영문제목(English Title) An Efficient Dynamic Graph Summarization in Massive Graph
저자(Author) 서호진   김현욱   박기성   이영구   HoJin Seo   Hyunwook Kim   Kisung Park   Young-Koo Le  
원문수록처(Citation) VOL 32 NO. 01 PP. 0002 ~ 0012 (2016. 04)
한글내용
(Korean Abstract)
그래프 요약은 대용량 그래프에서 밀집도가 높은 부분그래프를 압축 표현하는 기법이다. 이러한 그래프 요약은 연결성, 정도 비대칭성 등과 같은 그래프가 갖는 고유한 구조적 정보를 분석하기 위해 사용된다. 기존 그래프 요약 기법은 그래프를 차수가 높은 허브 정점을 기준으로 다수의 부분 그래프들로 반복적으로 분할하고, 분할된 부분 그래프들을 각각 요약하였다. 그러나 동적 환경을 고려하지 않아 그래프가 변경될 때마다 전체 그래프에 대해 다시 요약 구조를 탐색해야하기 때문에 매우 오랜 수행시간을 갖게 된다. 본 논문은 대용량 그래프에서 효율적인 동적 그래프 요약 기법을 제안한다. 제안하는 기법은 허브 후보 집합과 이전 주기의 분할된 부분 그래프를 이용하여 전체 그래프에 대한 재분할 없이 효율적으로 이전 주기의 요약 구조를 갱신한다. 실험을 통하여 제안하는 기법이 기존의 기법보다 최대 57% 수행시간이 향상됨을 보인다.
영문내용
(English Abstract)
Graph summarization is a technique for compressing highly dense subgraphs in a massive graph. This technique can be utilized for analyzing the topological characteristics of graphs such as connectivity and skewness of graphs. The state-of-the-art graph summarization technique incrementally divides a large graph into subgraphs based on the hub nodes having higher degrees, and then summarizes each of the divided subgraphs. However, This summarization technique does not consider the frequent changes in a dynamic graph. Therefore, this technique requires a very long execution time since it must summarize the whole graph again whenever the graph changes. In this paper, we propose an efficient dynamic graph summarization technique for a massive graph. The proposed technique updates only the previously summarized subgraphs which are the subjects to be changed. Our technique can identify those summarized subgraphs using the set of hub node candidates without considering the whole graph. In our experiments, we observe that the proposed summarization technique can reduce the runtime by up to 57% compared to the state-of-the-art graph summarization technique.
키워드(Keyword) 그래프 요약   그래프 마이닝   동적 그래프   Graph Summarization   Graph Mining   Dynamic Graph  
파일첨부 PDF 다운로드