Skip to main content
Presentation
Scalable Subgraph Counting: The Methods Behind The Madness
Companion Proceedings of the 2019 World Wide Web Conference (WWW '19 Companion)
  • Comandur Seshadhri, University of California, Santa Cruz
  • Srikanta Tirthapura, Iowa State University
Document Type
Conference Proceeding
Conference
The 2019 World Wide Web Conference
Publication Version
Published Version
Publication Date
5-1-2019
DOI
10.1145/3308560.3320092
Conference Title
The 2019 World Wide Web Conference
Conference Date
May 13–17, 2019
Geolocation
(37.7749295, -122.41941550000001)
Abstract

Subgraph counting is a fundamental problem in graph analysis that finds use in a wide array of applications. The basic problem is to count or approximate the occurrences of a small subgraph (the pattern) in a large graph (the dataset). Subgraph counting is a computationally challenging problem, and the last few years have seen a rich literature develop around scalable solutions for it. However, these results have thus far appeared as a disconnected set of ideas that are applied separately by different research groups. We observe that there are a few common algorithmic building blocks that most subgraph counting results build on. In this tutorial, we attempt to summarize current methods through distilling these basic algorithmic building blocks. The tutorial will also cover methods for subgraph analysis on “big data” computational models such as the streaming model and models of parallel and distributed computation.

Comments

This proceeding is published as Seshadhri, Comandur, and Srikanta Tirthapura. "Scalable Subgraph Counting: The Methods Behind The Madness." In Companion Proceedings of The 2019 World Wide Web Conference (WWW ’19 Companion), May 13– 17, 2019, San Francisco, CA, USA. New York, NY: ACM. (2019): 1317-1318. DOI: 10.1145/3308560.3320092. Posted with permission.

Creative Commons License
Creative Commons Attribution 4.0 International
Copyright Owner
IW3C2 (International World Wide Web Conference Committee)
Language
en
File Format
application/pdf
Citation Information
Comandur Seshadhri and Srikanta Tirthapura. "Scalable Subgraph Counting: The Methods Behind The Madness" San Francisco, CACompanion Proceedings of the 2019 World Wide Web Conference (WWW '19 Companion) (2019) p. 1317 - 1318
Available at: http://works.bepress.com/srikanta-tirthapura/49/