DC Field | Value | Language |
---|---|---|
dc.contributor.author | Moon, Seunghyeon | ko |
dc.contributor.author | Lee, Jae-Gil | ko |
dc.contributor.author | Kang, Minseo | ko |
dc.contributor.author | Choy, Minsoo | ko |
dc.contributor.author | Lee, Jin Woo | ko |
dc.date.accessioned | 2016-10-07T09:32:55Z | - |
dc.date.available | 2016-10-07T09:32:55Z | - |
dc.date.created | 2014-12-24 | - |
dc.date.created | 2014-12-24 | - |
dc.date.created | 2014-12-24 | - |
dc.date.issued | 2016-07 | - |
dc.identifier.citation | DATA & KNOWLEDGE ENGINEERING, v.104, pp.17 - 31 | - |
dc.identifier.issn | 0169-023X | - |
dc.identifier.uri | http://hdl.handle.net/10203/213274 | - |
dc.description.abstract | Community detection from social network data gains much attention from academia and industry since it has many real-world applications. 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 vertices in a network. In this paper, we develop two parallel versions of the GN algorithm to support large-scale networks. First, we propose a new algorithm, which we call Shortest Path Betweenness MapReduce Algorithm (SPB-MRA), that utilizes the MapReduce model. Second, we propose another new algorithm, which we call Shortest Path Betweenness Vertex-Centric Algorithm (SPB-VCA), that utilizes the vertex-centric model. An approximation technique is also developed to further speed up community detection processes. We implemented SPB-MRA using Hadoop and SPB-VCA using GraphChi, and then evaluated the performance of SPB-MRA on Amazon EC2 instances and that of SPB-VCA on a single commodity PC. The evaluation results showed that the elapsed time of SPB-MRA decreased almost linearly as the number of reducers increased, SPB-VCA outperformed SPB-MRA just on a single PC by 4-6 times, and the approximation technique introduced negligible errors. (C) 2015 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | Parallel community detection on large graphs with MapReduce and GraphChi | - |
dc.type | Article | - |
dc.identifier.wosid | 000381589800003 | - |
dc.identifier.scopusid | 2-s2.0-84929256294 | - |
dc.type.rims | ART | - |
dc.citation.volume | 104 | - |
dc.citation.beginningpage | 17 | - |
dc.citation.endingpage | 31 | - |
dc.citation.publicationname | DATA & KNOWLEDGE ENGINEERING | - |
dc.identifier.doi | 10.1016/j.datak.2015.05.001 | - |
dc.contributor.localauthor | Lee, Jae-Gil | - |
dc.contributor.nonIdAuthor | Moon, Seunghyeon | - |
dc.type.journalArticle | Article; Proceedings Paper | - |
dc.subject.keywordAuthor | Clustering, classification, and association rules | - |
dc.subject.keywordAuthor | Mining methods and algorithms | - |
dc.subject.keywordAuthor | Community detection | - |
dc.subject.keywordAuthor | Social networks | - |
dc.subject.keywordAuthor | MapReduce | - |
dc.subject.keywordAuthor | Vertex-centric model | - |
dc.subject.keywordPlus | EDGE-BETWEENNESS | - |
dc.subject.keywordPlus | NETWORKS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.