실세계 네트워크에서의 클리크 기반 커뮤니티 탐색 = Clique-Based Community Detection in Real-World Networks

국문 초록 (Abstract)

그래프에서 클리크 기반 커뮤니티를 찾는 문제는 네트워크 분석, 생물정보학, 소셜 네트워크 분석 등 다양한 분야에서 중요하게 사용된다. 본 논문에서는 두 가지 중요한 클리크 기반 커뮤니티 문제인 k-클리크 커뮤니티 탐색 문제와 k-클리크 밀집 부분그래프 문제를 효율적으로 해결하기 위한 알고리즘을 제시한다.
첫째, k-클리크 커뮤니티 탐색 문제를 위해 MEC(Memory-Efficient Community detection) 알고리즘을 제안한다. MEC은 최신의 고속 클리크 나열 알고리즘인 DIST를 적용하고, 불필요한 (k − 1)-클리크와 트라이 노드를 제거하여 메모리 사용량을 크게 줄인다. MEC은 기존 방법 대비 수행 시간과 메모리 사용량을 최대 2배 이상 개선했음을 입증하였다.
둘째, k-클리크 밀집 부분그래프 문제를 위해 H-Greedy++ 알고리즘을 제안한다. H-Greedy++는 이론적으로 제시된 알고리즘인 Super-Greedy++를 실제 구현하고, 최적값에 도달했음을 판단하여 스스로 정지하는 효과적인 정지 조건을 탑재하였다. H-Greedy++는 실험한 모든 데이터셋에서 최적값과 동일한 결과를 내놓으며, 기존 근사 알고리즘 대비 평균 5-10배 적은 시행으로 최적값에 도달하였음을 입증했다.

다국어 초록 (Multilingual Abstract)

The problem of finding clique-based communities in graphs is important in various fields, including network analysis, bioinformatics, and social network analysis. This paper presents algorithms for efficiently solving two important clique-based community problems: the k-clique community detection problem and the k-clique densest subgraph problem.
First, we propose the MEC (Memory-Efficient Community detection) algorithm for the k-clique community detection problem. MEC adopts the latest high-speed clique listing algorithm, DIST, and significantly reduces memory usage by removing unnecessary (k − 1)-cliques and trie nodes. MEC is shown to improve both running time and memory usage by up to more than twofold compared to existing methods.
Second, we propose the H-Greedy++ algorithm for the k-clique densest subgraph problem. H-Greedy++ implements the theoretically introduced algorithm, Super-Greedy++, in practice and incorporates an effective stopping criterion that determines when the optimal value has been reached. H-Greedy++ yields the same results as the optimal solution across all tested datasets and is shown to reach the optimal value with 5–10 times fewer iterations on average compared to existing approximation algorithms.

목차 (Table of Contents)

• 초록 i
• 목차 ii
• 그림 목록 iv
• 표 목록 v
• 제 1 장 서론 1
• 제 2 장 배경 지식 4
• 제 1 절 k-클리크 4
• 제 2 절 k-클리크 인접성 4
• 제 3 절 k-클리크 커뮤니티 4
• 제 4 절 k-클리크 밀도 5
• 제 3 장 k-클리크 커뮤니티 탐색 6
• 제 1 절 MEC 6
• 제 1 항 CPM 6
• 제 2 항 불필요한 (k−1)-클리크의 제거 8
• 제 3 항 DIST 트라이의 최적화 9
• 제 4 장 MEC 실험 설명 및 결과 11
• 제 1 절 실험 개요 11
• 제 2 절 실험 결과 11
• 제 3 절 트라이 최적화의 효율 12
• 제 5 장 k-클리크 밀집 부분그래프 16
• 제 1 절 H-Greedy++ 16
• 제 2 절 정지 조건 19
• 제 6 장 H-Greedy++ 실험 설명 및 결과 21
• 제 1 절 실험 개요 21
• 제 2 절 실험 결과 21
• 제 7 장 결론 24
• 참고문헌 25
• Abstract 28