DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kim, Sung-Ho | - |
dc.contributor.advisor | 김성호 | - |
dc.contributor.author | Kwon, Se-Jeong | - |
dc.contributor.author | 권세정 | - |
dc.date.accessioned | 2013-09-12T02:33:33Z | - |
dc.date.available | 2013-09-12T02:33:33Z | - |
dc.date.issued | 2012 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=487401&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/181604 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 수리과학과, 2012. 2, [ iv, 22 p. ] | - |
dc.description.abstract | In this paper, we introduce a simple and new idea of link partition algorithm, direct line graph partition(DLP), using line graph transformation and traditional partition method. Two well-known algorithms, CPM(Clique Percolation method) and link clustering(LC) method, are introduced and compared to DLP. Since a usual line graph has more edges and nodes than its original graph, we selected faster partition algorithms, Fastgreedy and Walktrap, for line-graph partition. To compare goodness of algorithms, we adopt Mov. DLP is faster than CPM and shows better goodness of overlapping clustering. Concept of pair-wise link similarity is also applied to improve goodness of DLP. However, WDLP takes more time than DLP and shows almost same Mov. Briey speaking, there`s no considerable improvement goodness. In addition, we propose an algorithm, Finding-Local-Optimum (FLO), that finds a clustering with a local optimum when an objective function is given. We have conducted a set of experiments on networks. The result shows that methods based on WDLP and DLP with FLO produces a higher accuracy compared to LC. It`s complexity is smaller than CPM. Since CPM`s definition is too strict, it rarely returns overlapping clusters which covers all nodes in network. If one wants to do overlapping clustering with every node in a given network, DLP and WDLP can be good candidates for this. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | 군집화 | - |
dc.subject | 중복허용 | - |
dc.subject | Clustering | - |
dc.subject | Ovelapping | - |
dc.subject | Link | - |
dc.subject | 연결 | - |
dc.title | Graph theoretic methods for clustering based on adjacency matrix and their comparison | - |
dc.title.alternative | 인접성 행렬을 이용한 그래프 이론적 집락화와 방법의 비교 | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 487401/325007 | - |
dc.description.department | 한국과학기술원 : 수리과학과, | - |
dc.identifier.uid | 020083030 | - |
dc.contributor.localauthor | Kim, Sung-Ho | - |
dc.contributor.localauthor | 김성호 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.