"Triangles, Communities, and Dense Subgraphs"

<<< All talks

"Triangles, Communities, and Dense Subgraphs"

When	Friday, April 4, 2025, 1:30 PM – 2:30 PM (MT)
Where	WEB L112

Abstract

In this talk, we will go over a few recent results on dense subgraph discovery. We aim to discover ‘many’ dense subgraphs of ‘reasonable size’ in real-world networks. We show that by leveraging triadic structure in graphs, one can do this efficiently without complicated distributional assumptions on the input. Our techniques bridge an important gap: most existing theory considers the setting where the number of pieces is a constant, whereas techniques that produce `satisfactory’ decompositions rarely have density guarantees (and indeed, often give sparse, poorly connected subgraphs). We offer a community detection flavor to our results: we provide a new metric for the ‘goodness’ of communities in terms of density and show that the spectrum of graph matrices implies the existence of communities.

A key goal of this talk is to unpack the several phrases in quotes in the preceding paragraph and offer some perspectives on why these are important (and sometimes difficult!). We also provide an algorithm that (provably) decomposes large social networks into dense subgraphs in minutes on regular laptops, and, time permitting, discuss the setting of overlapping subgraph detection using similar techniques.

Speaker

Tags: networks & graphs society & policy

---

Part of the Data Science & AI Lecture Series. Something wrong on this page? Edit _data/talks/2025-04-04-sabyasachi-basu.toml.