Linked e-resources
Details
Table of Contents
Intro; Preface; Contents; 1 Introduction; 1.1 Background; 1.1.1 Graph Terminologies; 1.1.2 Real Graph Datasets; 1.1.3 Representation of Large Sparse Graphs; 1.1.4 Complexity Analysis; 1.2 Cohesive Subgraphs; 1.2.1 Cohesive Subgraph Computation; 1.2.2 Applications; 2 Linear Heap Data Structures; 2.1 Linked List-Based Linear Heap; 2.1.1 Interface of a Linked List-Based Linear Heap; 2.1.2 Time Complexity of ListLinearHeap; 2.2 Array-Based Linear Heap; 2.2.1 Interface of an Array-Based Linear Heap; 2.2.2 Time Complexity of ArrayLinearHeap; 2.3 Lazy-Update Linear Heap
3 Minimum Degree-Based Core Decomposition3.1 Preliminaries; 3.1.1 Degeneracy and Arboricity of a Graph; 3.2 Linear-Time Core Decomposition; 3.2.1 The Peeling Algorithm; 3.2.2 Compute k-Core; 3.2.3 Construct Core Hierarchy; 3.2.3.1 Disjoint-Set Data Structure; 3.2.3.2 Core Hierarchy Tree; 3.2.3.3 Core Spanning Tree; 3.3 Core Decomposition in Other Environments; 3.3.1 h-index-Based Core Decomposition; 3.3.1.1 An h-index-Based Local Algorithm; 3.3.1.2 An Optimization Algorithm; 3.3.2 Parallel/Distributed Core Decomposition; 3.3.3 I/O-Efficient Core Decomposition; 3.4 Further Readings
5.1.2 k-Clique Enumeration Algorithms5.1.2.1 Extending K3 to k-Clique Enumeration; 5.1.2.2 Extending TriE to k-Clique Enumeration; 5.2 Higher-Order Core Decomposition; 5.2.1 Truss Decomposition; 5.2.1.1 The Peeling Algorithm for Truss Decomposition; 5.2.2 Nucleus Decomposition; 5.2.2.1 The Peeling Algorithm for Nucleus Decomposition; 5.3 Higher-Order Densest Subgraph Computation; 5.3.1 Approximation Algorithms; 5.3.2 Exact Algorithms; 5.4 Further Readings; 6 Edge Connectivity-Based Graph Decomposition; 6.1 Preliminaries; 6.2 Deterministic k-Edge Connected Components Computation
6.2.1 A Graph Partition-Based Framework6.2.2 Connectivity-Aware Two-Way Partition; 6.2.3 Connectivity-Aware Multiway Partition; 6.2.4 The KECC Algorithm; 6.3 Randomized k-Edge Connected Components Computation; 6.4 Edge Connectivity-Based Decomposition; 6.4.1 A Bottom-Up Approach; 6.4.2 A Top-Down Approach; 6.4.3 A Divide-and-Conquer Approach; 6.5 Further Readings; References; Index
3 Minimum Degree-Based Core Decomposition3.1 Preliminaries; 3.1.1 Degeneracy and Arboricity of a Graph; 3.2 Linear-Time Core Decomposition; 3.2.1 The Peeling Algorithm; 3.2.2 Compute k-Core; 3.2.3 Construct Core Hierarchy; 3.2.3.1 Disjoint-Set Data Structure; 3.2.3.2 Core Hierarchy Tree; 3.2.3.3 Core Spanning Tree; 3.3 Core Decomposition in Other Environments; 3.3.1 h-index-Based Core Decomposition; 3.3.1.1 An h-index-Based Local Algorithm; 3.3.1.2 An Optimization Algorithm; 3.3.2 Parallel/Distributed Core Decomposition; 3.3.3 I/O-Efficient Core Decomposition; 3.4 Further Readings
5.1.2 k-Clique Enumeration Algorithms5.1.2.1 Extending K3 to k-Clique Enumeration; 5.1.2.2 Extending TriE to k-Clique Enumeration; 5.2 Higher-Order Core Decomposition; 5.2.1 Truss Decomposition; 5.2.1.1 The Peeling Algorithm for Truss Decomposition; 5.2.2 Nucleus Decomposition; 5.2.2.1 The Peeling Algorithm for Nucleus Decomposition; 5.3 Higher-Order Densest Subgraph Computation; 5.3.1 Approximation Algorithms; 5.3.2 Exact Algorithms; 5.4 Further Readings; 6 Edge Connectivity-Based Graph Decomposition; 6.1 Preliminaries; 6.2 Deterministic k-Edge Connected Components Computation
6.2.1 A Graph Partition-Based Framework6.2.2 Connectivity-Aware Two-Way Partition; 6.2.3 Connectivity-Aware Multiway Partition; 6.2.4 The KECC Algorithm; 6.3 Randomized k-Edge Connected Components Computation; 6.4 Edge Connectivity-Based Decomposition; 6.4.1 A Bottom-Up Approach; 6.4.2 A Top-Down Approach; 6.4.3 A Divide-and-Conquer Approach; 6.5 Further Readings; References; Index