| 한글제목(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 다운로드
|
