Preface......Page 6
Contents......Page 9
1.1.1 Graph Terminologies......Page 11
1.1.2 Real Graph Datasets......Page 13
1.1.3 Representation of Large Sparse Graphs......Page 14
1.2 Cohesive Subgraphs......Page 16
1.2.1 Cohesive Subgraph Computation......Page 17
1.2.2 Applications......Page 18
2.1 Linked List-Based Linear Heap......Page 19
2.1.1 Interface of a Linked List-Based Linear Heap......Page 20
2.1.2 Time Complexity of ListLinearHeap......Page 23
2.2 Array-Based Linear Heap......Page 24
2.2.1 Interface of an Array-Based Linear Heap......Page 25
2.3 Lazy-Update Linear Heap......Page 28
3.1 Preliminaries......Page 31
3.1.1 Degeneracy and Arboricity of a Graph......Page 32
3.2.1 The Peeling Algorithm......Page 33
3.2.2 Compute k-Core......Page 36
3.2.3 Construct Core Hierarchy......Page 37
3.2.3.1 Disjoint-Set Data Structure......Page 38
3.2.3.2 Core Hierarchy Tree......Page 39
3.2.3.3 Core Spanning Tree......Page 41
3.3.1 h-index-Based Core Decomposition......Page 42
3.3.1.1 An h-index-Based Local Algorithm......Page 43
3.3.1.2 An Optimization Algorithm......Page 44
3.3.2 Parallel/Distributed Core Decomposition......Page 46
3.3.3 I/O-Efficient Core Decomposition......Page 47
3.4 Further Readings......Page 49
4.1 Preliminaries......Page 50
4.1.1 Properties of Densest Subgraph......Page 51
4.2.1 A 2-Approximation Algorithm......Page 52
4.2.2 A Streaming 2(1+ฮต)-Approximation Algorithm......Page 54
4.3.1 Density Testing......Page 56
4.3.2 The Densest-Exact Algorithm......Page 59
4.4 Further Readings......Page 61
5.1.1 Triangle Enumeration Algorithms......Page 63
5.1.1.1 The K3 Algorithm......Page 64
5.1.1.2 A General Framework for Triangle Enumeration......Page 66
5.1.2.1 Extending K3 to k-Clique Enumeration......Page 70
5.1.2.2 Extending TriE to k-Clique Enumeration......Page 71
5.2.1 Truss Decomposition......Page 72
5.2.1.1 The Peeling Algorithm for Truss Decomposition......Page 74
5.2.2 Nucleus Decomposition......Page 76
5.2.2.1 The Peeling Algorithm for Nucleus Decomposition......Page 77
5.3.1 Approximation Algorithms......Page 79
5.3.2 Exact Algorithms......Page 81
5.4 Further Readings......Page 83
6.1 Preliminaries......Page 84
6.2.1 A Graph Partition-Based Framework......Page 86
6.2.2 Connectivity-Aware Two-Way Partition......Page 87
6.2.3 Connectivity-Aware Multiway Partition......Page 92
6.2.4 The KECC Algorithm......Page 95
6.3 Randomized k-Edge Connected Components Computation......Page 97
6.4 Edge Connectivity-Based Decomposition......Page 99
6.4.1 A Bottom-Up Approach......Page 100
6.4.3 A Divide-and-Conquer Approach......Page 102
6.5 Further Readings......Page 105
References......Page 106
Index......Page 111