Efficient Enumeration and Search of Relaxed Cliques = 완화된 클리크의 효율적인 열거 및 탐색

국문 초록 (Abstract)

그래프에서 밀집 부분구조를 식별하는 것은 소셜 네트워크, 생물학적 시스템, 금융 네트워크 등 다양한 분야에서 응용되는 그래프 분석의 핵심 문제이다. 클리크는 모든 정점 쌍이 서로 인접하는 부분그래프로서 가장 밀집된 부분그래프를 나타내지만, 실제 데이터가 노이즈를 포함하거나 불완전한 경우가 많아 그 정의가 지나치게 제한적이다. 이러한 한계를 해결하기 위해 k-결함 클리크와 k-플렉스와 같은 완화된 클리크 모델이 제안되었다. 이러한 완화된 클리크 문제들에 대한 많은 알고리즘 연구에도 불구하고, 기존 알고리즘들은 대규모 그래프를 처리하는 데 있어 확장성이 제한적이다. 본 논문에서는 세 가지 중요하고 잘 알려진 완화된 클리크 문제인 극대 k-결함 클리크 열거, 최대 k-결함 클리크 탐색, 극대 k-플렉스 열거를 다룬다.

첫째, 극대 k-결함 클리크 열거와 최대 k-결함 클리크 탐색을 위한 이론적, 실용적으로 효율적인 알고리즘을 제안한다. 극대 k-결함 클리크 열거에 대해서 k가 상수일 때 탐색 공간이 최악의 경우 최적인 분기 한정 알고리즘을 개발하였으며, 이는 완화된 클리크 문제에서 최초의 결과이다. 또한 제안된 분기 한정 알고리즘을 기반으로 최대 k-결함 클리크 탐색을 위한 효율적인 프레임워크를 제안한다. 실제 벤치마크 데이터셋에 대한 방대한 실험을 통해 극대 k-결함 클리크 열거와 최대 k-결함 클리크 탐색 알고리즘 각각이 해당 기존 최신 알고리즘보다 처리 시간 면에서 최대 수만 배 빠름을 보였다.

둘째, 극대 k-플렉스 열거를 위한 빠르고 확장 가능한 알고리즘을 개발한다. 새로운 피벗 기법을 포함한 분기 한정 프레임워크와 간단하면서도 효과적인 축소 기법을 제안하며, 이 두 기법은 상호 보완적으로 탐색 공간을 대폭 줄인다. 실제 벤치마크 데이터셋에 대한 방대한 실험을 통해 제안된 접근법이 기존 최신 알고리즘보다 처리 시간 면에서 최대 수천 배 빠름을 보였다.

다국어 초록 (Multilingual Abstract)

Identifying dense substructures in graphs is a fundamental task in graph analysis with diverse applications in social networks, biological systems, and financial networks. While a clique, in which every pair of vertices is adjacent, represents the densest possible subgraph, its strict definition is often too restrictive for real-world applications where data is noisy or incomplete. To address this limitation, relaxed clique models such as k-defective cliques and k-plexes have been proposed. Despite extensive research on algorithms for these relaxed clique problems, existing algorithms still show limited scalability in handling large graphs. In this dissertation, we consider three important and well-known relaxed clique problems: maximal k-defective clique enumeration, maximum k-defective clique search, and maximal k-plex enumeration.

First, we propose theoretically and practically efficient algorithms for maximal k-defective clique enumeration and maximum k-defective clique search. For maximal k-defective clique enumeration, we develop a branch-and-bound algorithm whose search space is worst-case optimal when k is a constant, which is the first such result for relaxed clique problems. We also propose an efficient framework for maximum k-defective clique search based on our branch-and-bound approach. Experiments on real-world benchmark datasets show that our algorithms for maximal k-defective clique enumeration and maximum k-defective clique search are faster than the respective state-of-the-art algorithms by up to four orders of magnitude in terms of processing time.

Second, we develop a fast and scalable algorithm for maximal k-plex enumeration. We propose a novel branch-and-bound framework with a new pivoting technique and a simple yet effective reduction technique; these two techniques are complementary and substantially reduce the search space. Extensive experiments on real-world benchmark datasets show that our approach outperforms state-of-the-art algorithms by up to three orders of magnitude in terms of processing time.

목차 (Table of Contents)

• Abstract i
• Contents iii
• List of Figures v
• List of Tables vii
• 1 Introduction 1
• 1.1 Background 1
• 1.2 Contributions 4
• 1.3 Organization 5
• 2 Preliminaries 6
• 2.1 Notations 6
• 2.2 Problem Statements 10
• 2.3 Related Works 10
• 3 Enumeration and Search of Defective Cliques 13
• 3.1 A New Branch-and-Bound Algorithm 18
• 3.1.1 A Novel Clique-First Approach 18
• 3.1.2 A New Pivoting Technique for Defective Cliques 22
• 3.1.3 Theoretical Analysis 26
• 3.1.4 Using Diameter-Two Property 35
• 3.2 Maximum k-Defective Clique Search 37
• 3.2.1 Our Framework 37
• 3.2.2 Initial Solution and Graph Reduction 38
• 3.3 Performance Evaluation 43
• 3.3.1 Experimental Setup 43
• 3.3.2 Maximal k-Defective Clique Enumeration 47
• 3.3.3 Maximum k-Defective Clique Search 50
• 3.3.4 Effectiveness of Individual Techniques 52
• 3.3.5 Case Study 54
• 3.3.6 Parallelization 58
• 4 Enumeration of k-Plexes 60
• 4.1 A Novel Branch-and-Bound Framework 65
• 4.1.1 A Branch-and-Bound Algorithm 65
• 4.1.2 A New Pivoting Technique 68
• 4.1.3 An Effective Reduction Technique 75
• 4.2 Our Algorithm BPR 77
• 4.3 Performance Evaluation 78
• 4.3.1 Experimental Setup 79
• 4.3.2 Evaluation of Different Algorithms 80
• 4.3.3 Effectiveness of Individual Techniques 84
• 4.3.4 Case Study 86
• 5 Conclusion 90
• 5.1 Summary 90
• 5.2 Cross-Chapter Discussion 91
• 5.3 Future Directions 93
• 요약 111