[논문]대용량 네트워크 압축 기반 클러스터링 알고리즘 개발

서동민; 유석종; 이민호

대용량 네트워크 압축 기반 클러스터링 알고리즘 개발
Development of Clustering Algorithm based on Massive Network Compression 원문보기

서동민 (한국과학기술정보연구원) , 유석종 (한국과학기술정보연구원) , 이민호 (한국과학기술정보연구원)

빅데이터란 대용량 데이터 활용 및 분석을 통해 가치 있는 정보를 추출하고, 이를 바탕으로 대응 방안 도출 또는 변화를 예측하는 기술을 의미한다. 그리고 빅데이터 분석에 활용되는 데이터인 페이스북과 같은 소셜 데이터, 유전자 발현과 같은 바이오 데이터, 항공망과 같은 지리정보 데이터들은 대용량 네트워크로 구성되어 있다. 네트워크 클러스터링은 서로 유사한 특성을 갖는 네트워크 내의 데이터들을 동일한 클러스터로 묶는 기법으로 네트워크 데이터를 분석하고 그 특성을 파악하는데 폭넓게 사용된다. 최근 빅데이터가 다양한 분야에서 활용되면서 방대한 양의 네트워크 데이터가 생성되고 있고, 이에 따라서 대용량 네트워크 데이터를 효율적으로 처리하는 클러스터링 기법의 중요성이 증가하고 있다. MCL(Markov Clustering) 알고리즘은 플로우 기반 무감독(unsupervised) 클러스터링 알고리즘으로 확장성이 우수해 다양한 분야에서 활용되고 있다. 하지만, MCL은 대용량 네트워크에 대해서는 많은 클러스터링 연산을 요구하며 너무 많은 클러스터를 생성하는 문제를 갖는다. 본 논문에서는 네트워크 압축을 기반으로 한 클러스터링 알고리즘을 제안함으로써 MCL보다 클러스터링 속도와 정확도를 향상시켰다. 또한, 희소행렬을 효율적으로 저장하는 CSC(Compressed Sparse Column) 자료구조와 MapReduce 기법을 제안한 클러스터링 알고리즘에 적용함으로써 대용량 네트워크에 대한 클러스터링 속도를 향상시켰다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 HEM을 개선시킨 네트워크 압축 기법을 제안하고 클러스터링 과정에 수행되는 일부 연산을 병렬처리 함으로써, 기존 클러스터링 알고리즘 대비 정확도와 속도를 향상시킨 클러스터링을 개발하였다. 향후에는 다양한 데이터 셋을 가지고 제안하는 알고리즘에 대한 성능평가를 수행할 것이며, 최근 Hadoop/ MapReduce를 기반으로 한 네트워크 분석 기법들이 연구되고 있기에 본 논문에서 개발한 알고리즘과의 성능평가를 통해 우수성을 입증할 계획이다.
본 논문에서는 대용량 네트워크 분석 지원을 위한 네트워크 압축을 기반으로 한 클러스터링 알고리즘을 개발했다. 또한, 희소행렬을 효율적으로 저장하는 CSC(Compressed Sparse Column) 자료구조와 MapReduce 기법을 개발한 클러스터링 알고리즘에 적용함으로써 대용량 네트워크에 대한 클러스터링 속도와 정확도를 향상시켰다.

제안 방법

그림 3에서 Coarsening(N0)는 주어진 네트워크를 압축하는 함수로, 그림 4에서와 같이 기존 대표 네트워크 압축 기법 중 하나인 HEM(Heavy Edge Matching)[4]에 대해 기존 압축에 참여한 노드에 대한 재압축을 허용함으로써 네트워크 압축률 및 정확도를 개선하였다. 그리고 제안하는 클러스터링 알고리즘에서는 희소행렬(sparse matrix)에 대한 저장 공간 활용을 개선하기 위해 [5]에서 소개된 CSC(Compressed Sparse Column) 자료구조를 통해 행렬을 관리했다. 또한, 그림 3에서 Inflate와 Prune 연산 방법은 MCL과 동일하나 병렬 수행될 수 있는 행렬 연산이기에 MapReduce를 통해 병렬 수행함으로써 클러스터링 연산 속도를 개선하였다.
그리고 제안하는 클러스터링 알고리즘에서는 희소행렬(sparse matrix)에 대한 저장 공간 활용을 개선하기 위해 [5]에서 소개된 CSC(Compressed Sparse Column) 자료구조를 통해 행렬을 관리했다. 또한, 그림 3에서 Inflate와 Prune 연산 방법은 MCL과 동일하나 병렬 수행될 수 있는 행렬 연산이기에 MapReduce를 통해 병렬 수행함으로써 클러스터링 연산 속도를 개선하였다.
본 논문에서는 대용량 네트워크 분석 지원을 위한 네트워크 압축을 기반으로 한 클러스터링 알고리즘을 개발했다. 또한, 희소행렬을 효율적으로 저장하는 CSC(Compressed Sparse Column) 자료구조와 MapReduce 기법을 개발한 클러스터링 알고리즘에 적용함으로써 대용량 네트워크에 대한 클러스터링 속도와 정확도를 향상시켰다.

후속연구

본 논문에서는 HEM을 개선시킨 네트워크 압축 기법을 제안하고 클러스터링 과정에 수행되는 일부 연산을 병렬처리 함으로써, 기존 클러스터링 알고리즘 대비 정확도와 속도를 향상시킨 클러스터링을 개발하였다. 향후에는 다양한 데이터 셋을 가지고 제안하는 알고리즘에 대한 성능평가를 수행할 것이며, 최근 Hadoop/ MapReduce를 기반으로 한 네트워크 분석 기법들이 연구되고 있기에 본 논문에서 개발한 알고리즘과의 성능평가를 통해 우수성을 입증할 계획이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

대용량 네트워크 압축 기반 클러스터링 알고리즘 개발
Development of Clustering Algorithm based on Massive Network Compression 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

대용량 네트워크 압축 기반 클러스터링 알고리즘 개발 Development of Clustering Algorithm based on Massive Network Compression 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

대용량 네트워크 압축 기반 클러스터링 알고리즘 개발
Development of Clustering Algorithm based on Massive Network Compression 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper