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 기법이 경미한 수준의 오차를 유발 한다는 것을 보여준다.
