DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kim, Myoung Ho | - |
dc.contributor.advisor | 김명호 | - |
dc.contributor.author | Seo, Jung Hyuk | - |
dc.date.accessioned | 2022-04-21T19:34:24Z | - |
dc.date.available | 2022-04-21T19:34:24Z | - |
dc.date.issued | 2020 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=964786&flag=dissertation | en_US |
dc.identifier.uri | http://hdl.handle.net/10203/295724 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전산학부, 2020.8,[iv, 66 p. :] | - |
dc.description.abstract | A community structure in a graph is defined as a set of nodes where nodes in the same community are densely connected by edges. In this dissertation, we present two methods of discovering community structures: 1) community detection that finds all community structures in a graph, and 2) community search that finds some community structures having particular properties. In recent years, the size of graph data has increased significantly. Most existing community detection algorithms do not consider the case where the size of main memory is not sufficient to handle large amount of graph data, and they incur excessive disk I/O and thrashing. In the first part, we propose an I/O-efficient community detection method for large-scale graph data. An input graph is partitioned into several subgraphs smaller than memory, local community structures are detected for each subgraph. And then the local communities from the subgraphs are merged so that global results can be obtained in the point of view of an original graph. We also propose a cluster maintenance method for large-scale dynamic graphs that change over time. The proposed method produces scalable performance even for very large graphs. In the second part of the dissertation, we propose an efficient method of searching influential communities that contain highly influential members. Although there are many metrics that describe influences of objects, the existing methods search for influential communities in terms of only one influence type without comprehensively considering other influence types. The influences are modeled as multidimensional vectors, where each dimension in the vectors explains each influence type. For properly ranking communities, we utilize the concept of the top-$\gamma$ dominating query for multi-dimensional point data. Extensive experiments show that our proposed method effectively finds influential communities based on multiple influence types, and is orders-of-magnitude faster than the baseline solution. | - |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Graph mining▼aLarge-scale graph data▼aCommunity detection▼aGraph clustering▼aIncremental update▼aCommunity search▼aInfluential community model | - |
dc.subject | 그래프 마이닝▼a대규모 그래프 데이터▼a커뮤니티 검출▼a그래프 클러스터링▼a점진적 업데이트 기법▼a커뮤니티 검색▼a영향력 커뮤니티 모델 | - |
dc.title | Efficient discovery of community structures in large-scale graph data | - |
dc.title.alternative | 대규모 그래프 데이터에 대한 커뮤니티 구조 검출 및 검색 기법 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 325007 | - |
dc.description.department | 한국과학기술원 :전산학부, | - |
dc.contributor.alternativeauthor | 서정혁 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.