서지주요정보
맵리듀스 상에서 Edge-Betweenness 기반의 커뮤니티 발견 알고리즘의 구현 = Implementation of a community detection algorithm using edge-betweenness on MapReduce
서명 / 저자 맵리듀스 상에서 Edge-Betweenness 기반의 커뮤니티 발견 알고리즘의 구현 = Implementation of a community detection algorithm using edge-betweenness on MapReduce / 문승현.
저자명 문승현 ; Moon, Seung-Hyeon
발행사항 [대전 : 한국과학기술원, 2013].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8025726

소장위치/청구기호

학술문화관(문화관) 보존서고

MKSE 13011

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

As social networking services (SNSs) such as Facebook and Twitter are getting more popular, analyzing social network data becomes one of the most important issues in various areas. Among those analytics tasks, community detection from social network data gains much attention from academia and industry since it has many real-world applications such as friend recommendation and target marketing. The Girvan-Newman (GN) algorithm is a divisive hierarchical clustering algorithm for community detection, which is regarded as one of the most popular algorithms. It exploits the concept of edge betweenness to divide a network into multiple communities. Though it is being widely used, it has limitations in supporting large-scale networks since it needs to calculate the shortest path between every pair of nodes in a network. In this paper, we develop a parallel version of the GN algorithm to support large-scale networks. To this end, we propose a new algorithm, which we call Shortest Path Betweenness MapReduce Algorithm (SPB-MRA), that utilizes the MapReduce model. This algorithm consists of four major stages, and all operations are executed in parallel. In addition, we suggest an approximation technique to further speed up community detection processes. We implemented the SPB-MRA on Hadoop, which is the most popular open-source platform for MapReduce, and then conducted performance tests for SPB-MRA on Amazon EC2 instances. The results showed that elapsed time decreases almost linearly as the number of reducers increases and the approximation technique introduce almost negligible errors.

Facebook 그리고 Twitter를 위시한 소셜 네트워킹 서비스들(SNSs)의 인기가 증가함에 따라, 소셜 네트워크 데이터를 분석하는 것은 다양한 분야에서 가장 중요한 이슈 중의 하나가 되었다. 여러 분석들 중에, 친구 추천과 타겟 마케팅등에 실질적으로 응용 가능한 소셜 네트워크 데이터로 부터 커뮤니티의 발견은 학계와 산업계로부터 많은 관심을 받고 있다. Girvan-Newman (GN) 알고리즘은 가장 유명한 divisive hierarchical 클러스터링 알고리즘들 중 하나이다. GN 알고리즘은 edge betweenness개념을 이용하여 하나의 네트워크를 복수 개의 커뮤니티로 분할 한다. GN 알고리즘은 널리 이용 됨에도 불구하고, 네트워크 상의 모든 Node쌍 간의 최단경로 계산을 요구하기 때문에 큰 규모의 네트워크에 적용하는 데에 한계가 있다. 이를 위하여, 우리는 맵리듀스 모델을 이용하는 Shortest Path Betweenness MapReduce Algorithm (SPB-MRA)라는 하나의 새로운 알고리즘을 제안한다. 이 알고리즘은 4단계로 구성되어 있으며 모든 연산이 병렬로 실행된다. 이 뿐만 아니라, 우리는 커뮤니티 발견의 더 큰 속도 향상을 위하여, 하나의 approximation 기법을 제안 한다. 우리는 SPB-MRA를 가장 인기 있는 맵리듀스 오픈 소스 플랫폼인 하둡 상에서 구현하고, Amazon EC2 인스턴스들 상에서 성능 평가를 수행 하였다. 실험 결과는 reducer의 개수가 증가함에 따라 소요 시간이 거의 선형적으로 줄어드는 것과 approximation 기법이 경미한 수준의 오차를 유발 한다는 것을 보여준다.

서지기타정보

서지기타정보
청구기호 {MKSE 13011
형태사항 iv, 35 p. : 삽도 ; 30 cm
언어 한국어
일반주기 저자명의 영문표기 : Seung-Hyeon Moon
지도교수의 한글표기 : 이재길
지도교수의 영문표기 : Jae-Gil Lee
학위논문 학위논문(석사) - 한국과학기술원 : 지식서비스공학과,
서지주기 참고문헌 : p. 31-33
주제 맵리듀스
커뮤니티 발견
알고리즘
하둡
엣지 비트윈니스
MapReduce
Community Detection
Algorithm
Hadoop
Edge Betweenness
QR CODE qr code