Cohesive subgraph computation over large sparse graphs : algorithms, data structures, and programming techniques /: algorithms, data structures, and programming techniques. (2018)
- Record Type:
- Book
- Title:
- Cohesive subgraph computation over large sparse graphs : algorithms, data structures, and programming techniques /: algorithms, data structures, and programming techniques. (2018)
- Main Title:
- Cohesive subgraph computation over large sparse graphs : algorithms, data structures, and programming techniques
- Further Information:
- Note: Lijun Chang, Lu Qin.
- Authors:
- Chang, Lijun
Qin, Lu - 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.3Intro; 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 … (more)
- Publisher Details:
- Cham : Springer
- Publication Date:
- 2018
- Extent:
- 1 online resource (xii, 107 pages), illustrations (some color)
- Subjects:
- 511/.5
Graph theory
Electronic books
Electronic books - Languages:
- English
- ISBNs:
- 9783030035990
3030035999 - Related ISBNs:
- 9783030035983
- Notes:
- Note: Online resource; title from PDF title page (SpringerLink, viewed January 11, 2019).
- Access Rights:
- Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
- Access Usage:
- Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD.DS.381956
- Ingest File:
- 02_369.xml