Cohesive Subgraph Computation over Large Sparse Graphs

Algorithms, Data Structures, and Programming Techniques

verfasst von: Lijun Chang, Lu Qin

Verlag: Springer International Publishing

Buchreihe : Springer Series in the Data Sciences

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is considered the first extended survey on algorithms and techniques for efficient cohesive subgraph computation. With rapid development of information technology, huge volumes of graph data are accumulated. An availability of rich graph data not only brings great opportunities for realizing big values of data to serve key applications, but also brings great challenges in computation. Using a consistent terminology, the book gives an excellent introduction to the models and algorithms for the problem of cohesive subgraph computation. The materials of this book are well organized from introductory content to more advanced topics while also providing well-designed source codes for most algorithms described in the book. This is a timely book for researchers who are interested in this topic and efficient data structure design for large sparse graph processing. It is also a guideline book for new researchers to get to know the area of cohesive subgraph computation.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

With the rapid development of information technology such as social media, online communities, and mobile communications, huge volumes of digital data are accumulated with data entities involving complex relationships. These data are usually modelled as graphs in view of the simple yet strong expressive power of graph model; that is, entities are represented by vertices and relationships are represented by edges.

Lijun Chang, Lu Qin

Chapter 2. Linear Heap Data Structures

Abstract

In this chapter, we present linear heap data structures that will be useful in the remainder of the book for designing algorithms to efficiently process large sparse graphs.

Lijun Chang, Lu Qin

Chapter 3. Minimum Degree-Based Core Decomposition

Abstract

In this chapter, we discuss efficient techniques for computing the minimum degree-based graph decomposition (aka, core decomposition). Preliminaries are given in Section 3.1. A linear-time algorithm is presented in Section 3.2, while h-index-based local algorithms that can be naturally made parallel are presented in Section 3.3.

Lijun Chang, Lu Qin

Chapter 4. Average Degree-Based Densest Subgraph Computation

Abstract

In this section, we study average degree-based densest subgraph computation, where average degree is usually referred to as the edge density in the literature. In Section 4.1, we give preliminaries of densest subgraphs. Approximation algorithms and exact algorithms for computing the densest subgraph of a large input graph will be discussed in Section 4.2 and in Section 4.3, respectively.

Lijun Chang, Lu Qin

Chapter 5. Higher-Order Structure-Based Graph Decomposition

Abstract

Higher-order structures, also known as motifs or graphlets, have been recently used to successfully locate dense regions that cannot be detected otherwise by edge-centric methods [8, 89, 90].

Lijun Chang, Lu Qin

Chapter 6. Edge Connectivity-Based Graph Decomposition

Abstract

In this chapter, we study edge connectivity-based graph decomposition; that is, each subgraph satisfies a certain edge connectivity requirement.

Lijun Chang, Lu Qin

Backmatter

Titel: Cohesive Subgraph Computation over Large Sparse Graphs
verfasst von: Lijun Chang
Lu Qin
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-03599-0
Print ISBN: 978-3-030-03598-3
DOI: https://doi.org/10.1007/978-3-030-03599-0