280 0

공간 변환을 이용한 효과적인 커뮤니티 검출 프레임워크

Title
공간 변환을 이용한 효과적인 커뮤니티 검출 프레임워크
Author
방재근
Advisor(s)
김상욱
Issue Date
2017-08
Publisher
한양대학교
Degree
Master
Abstract
소셜 네트워크 분석은 데이터 마이닝 및 머신러닝 분야에서 가장 주목받고 있는 문제 중 하나이다. 그 중 커뮤니티 검출은 그래프 내 노드들의 구조를 찾기 위한 중요한 기술 중에 하나이다. 커뮤니티란 그래프 내 노드들의 집합을 의미하는데, 같은 커뮤니티 내에 노드들은 밀도가 높은 특징을 가지고 있고, 커뮤니티 간에 노드들은 밀도가 낮은 특징을 지닌다. 기존 커뮤니티 검출은 크게 두 가지 방법이 존재한다. 먼저 그래프만 이용해 커뮤니티 검출을 수행하거나, 그래프의 노드 간 유사도를 이용해 커뮤니티 검출을 수행한다. 하지만, 일반적으로 커뮤니티 구조가 잘 드러나지 않는 그래프에서 커뮤니티 검출을 수행하기 때문에 특정 노드가 정확히 어느 커뮤니티에 속해야 하는지 애매한 상황이 발생할 수 있어, 커뮤니티 구조가 잘 드러나는 그래프를 만드는 것이 정확한 커뮤니티 검출에 도움이 될 것이다. 본 논문에서 우리는 커뮤니티 구조가 잘 드러나는 그래프를 만들기 위해 공간 변환(Space Transformation) 방법과 두 종류의 커뮤니티 검출 방법을 수행할 수 있는 프레임워크를 제안한다. 공간 변환은 그래프 공간에서 유사도 공간으로, 유사도 공간에서 그래프 공간으로 변환하는 것을 의미하고, 순차적으로 한 번씩 수행한다. 이 과정에서 그래프만 이용하는 커뮤니티 검출 방법(그래프 공간), 그래프 내 노드 간 유사도를 이용하는 커뮤니티 검출 방법(유사도 공간)을 모두 수행할 수 있다. 또한, 공간 변환을 여러 번 순차적으로 이용하면 기존 그래프보다 같은 커뮤니티 내에 있는 노드들은 밀도가 더 높아지고, 서로 다른 커뮤니티 간에 노드들은 밀도가 낮아진다. 따라서 기존 그래프 보다 커뮤니티 구조가 잘 드러나는 그래프를 만들게 되며 최종적으로 더 정확한 커뮤니티 검출을 수행할 수 있다. 마지막으로, 우리가 제안하는 프레임워크를 사용했을 때 얼마나 더 정확한 커뮤니티 검출을 수행하는지 real world, synthetic 데이터를 이용해 실험을 진행했다. 실험 결과, 모든 데이터와 기존 커뮤니티 검출 방법들을 우리가 제안하는 프레임워크를 이용했을 때, 커뮤니티 검출의 정확도가 최대 80%까지 향상하는 것을 보였다.
URI
http://hdl.handle.net/20.500.11754/33678http://hanyang.dcollection.net/common/orgView/200000431168
Appears in Collections:
GRADUATE SCHOOL[S](대학원) > COMPUTER SCIENCE(컴퓨터·소프트웨어학과) > Theses (Ph.D.)
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE