Listing and Approximate Counting of k-Cliques in Real-World Networks = 실세계 네트워크에서의 k-클리크 열거 및 근사 계수

다국어 초록 (Multilingual Abstract)

Mining cohesive subgraphs is a fundamental problem in the analysis of real-world networks, with applications ranging from identifying protein complexes in biological networks to detecting communities in social networks. The k-clique, defined as a set of k pairwise adjacent vertices, serves as the most basic building block of cohesive structures. However, listing and counting k-cliques in large graphs remain computationally challenging tasks due to the combinatorial nature of the problems.

In this thesis, we present efficient algorithms for both the exact listing and approximate counting of k-cliques. First, we address the k-clique listing problem. Existing approaches for the k-clique listing problem are built upon a recursive framework, which often suffers from repeated computations of smaller cliques. In contrast, our algorithm computes each clique only once and stores it into a novel data structure called the Induced Subgraph Trie, which allows us to retrieve the cliques efficiently. Furthermore, we propose a simple yet effective pruning technique, which further improves the running time. Extensive experiments on real-world networks demonstrate that our algorithm achieves up to two orders of magnitude speedup over the state-of-the-art algorithm while using less memory.

Second, we present an efficient Monte Carlo algorithm for estimating the number of k-cliques with theoretical accuracy guarantees. We introduce a suite of novel techniques designed to obtain a small sample space and reduce the computational cost of sample trials. Additionally, we derive a new criterion for stopping sample trials while achieving the desired accuracy guarantee. Experimental results verify that our algorithm achieves up to two orders of magnitude speedup over the state-of-the-art algorithm while maintaining accuracy guarantees.

국문 초록 (Abstract)

응집 부분 그래프(cohesive subgraph)의 탐색은 실세계 네트워크 분석의 핵심적인 문제로, 생물정보학에서의 단백질 복합체 식별부터 소셜 네트워크에서의 커뮤니티 탐지에 이르기까지 다양한 응용 분야를 갖는다. 서로 인접한 k개의 정점 집합으로 정의되는 k-클리크(k-clique)는 응집 구조의 가장 기초적인 구성 요소이다. 그러나 대규모 그래프에서 k-클리크를 열거하고 계수하는 일은 이들의 조합적 특성으로 인해 여전히 어려운 문제로 남아있다.

본 학위논문에서는 k-클리크의 열거(listing)와 근사 계수(approximate counting)를 다룬다. 첫째, k-클리크 열거 문제에 대한 효율적인 알고리즘을 제시한다. 이 문제에 대한 기존 접근법들은 재귀적 프레임워크에 기반하고 있어, 작은 클리크들을 중복하여 찾는 일이 자주 발생한다. 대조적으로, 본 논문의 알고리즘은 각 클리크를 단 한 번씩만 찾고, 이들을 '유도 부분 그래프 트라이(Induced Subgraph Trie)'라는 새로운 자료구조에 저장하고 재사용한다. 더 나아가, 단순하지만 효과적인 가지치기(pruning) 기법을 제안하여 열거 과정을 가속한다. 실세계 네트워크에 대한 광범위한 실험을 통해, 본 알고리즘이 실행 시간과 메모리 사용량 측면에서 최신 경쟁 알고리즘보다 적은 메모리를 사용하면서도 최대 100배 이상의 속도 향상을 달성함을 보였다.

둘째, 이론적 정확도를 보장하면서 k-클리크를 근사 계수하는 효율적인 몬테 카를로 알고리즘을 제시한다. 본 논문에서는 작은 표본 공간을 구성하고 샘플 수행의 비용을 줄이기 위해 고안된 일련의 기법들을 소개한다. 또한, 이론적 정확도를 보장하면서 샘플 수행을 중지하기 위한 새로운 정지 기준을 제안한다. 실험 결과는 본 알고리즘이 최신 경쟁 알고리즘과 같은 수준의 정확도를 보장하면서도 최대 100배 이상의 속도 향상을 달성함을 보여준다.

목차 (Table of Contents)

• Abstract i
• Contents iii
• List of Figures v
• List of Tables vii
• 1 Introduction 1
• 1.1 Background 1
• 1.2 Organization 5
• 2 Preliminaries 6
• 2.1 Definitions and Notations 6
• 2.2 Problem Statement 9
• 2.3 Related Work 9
• 3 Listing k-Cliques 12
• 3.1 Overview of Algorithm 13
• 3.2 Induced Subgraph Trie 16
• 3.2.1 Preliminary Concepts 18
• 3.2.2 Data Structure 20
• 3.2.3 Algorithm 25
• 3.3 Pruning by Soft Embedding 29
• 3.4 Space Usage and Running Time of DIST 36
• 3.5 Performance Evaluation 42
• 3.5.1 Experimental Setup 42
• 3.5.2 Single-Threaded 44
• 3.5.3 Evaluation of Techniques 47
• 3.5.4 Parallelization 52
• 3.5.5 Space Usage of Induced Subgraph Trie 62
• 3.5.6 Listing all cliques 65
• 4 Approximate Counting of k-Cliques 66
• 4.1 Overview of Algorithm 71
• 4.2 Sample space refinement strategy 76
• 4.3 Star-based sampling approach 78
• 4.4 Combinatorial counting 81
• 4.5 Stopping Criterion for Stage 2 83
• 4.6 Running Time of CREST 85
• 4.7 Performance Evaluation 87
• 4.7.1 Experimental Setup 87
• 4.7.2 Comparison of individual techniques 91
• 4.7.3 Main experiment 96
• 5 Conclusion 99
• 5.1 Summary 99
• 5.2 Future Directions 100
• 요약 114