Cohesive subgraph computation over large sparse graphs. Algorithms, data structures, and programming techniques
type: Item
instance of: scholarly article
title: Cohesive subgraph computation over large sparse graphs. Algorithms, data structures, and programming techniques
zbMATH Open document ID: 1409.05001
DOI: 10.1007/978-3-030-03599-0
author: Lijun Chang
author: Lu Qin
published in: Springer Series in the Data Sciences
publication date: 2019-01-10T00:00:00Z
review text: This thin book of 107 pages stands somewhere between an extended survey article and a tutorial. This makes it a good candidate as a basis for a course on graph analysis specialized to analyzing dense subgraphs. The choice of topics is geared towards variants of the problem that can be solved efficiently, i.e., for computationally hard problems, approximation algorithms are considered. After an introduction in Chapter 1, Chapters 2 and 3 make a gentle start by introducing the simple yet useful and efficiently computable framework of core-decompositions that can infer all subgraphs of minimum degree $k$ for all values of $k$ together in linear time. The book goes into a lot of detail here including guidelines on the implementation. The subsequent chapters introduce generalizations based on average degree (Chapter 4), enumeration of triangles and $k$-cliques (Chapter 5), and decomposition based on edge connectivity (Chapter 6). \par To better fill the targeted role as an extended survey, a more detailed review of advanced results and more difficult problems might have been useful. For the role as a tutorial, it would have been nice to also discuss widely used graph analysis frameworks such as NetworKit or graphtool and how to use them in a course.
reviewed by: Peter Sanders
Mathematics Subject Classification ID: 05-01
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C42
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6999562
zbMATH Keywords: graph analysis
zbMATH Keywords: dense subgraphs
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-030-03599-0
OpenAlex ID: W4251396722
description: scientific article; zbMATH DE number 6999562