Seminars

View all Seminars  |  Download ICal for this event

Covering a graph with dense subgraphs: theory and some practice

Series: Bangalore Theory Seminars

Speaker: Sabyasachi Basu, University of California, Santa Cruz

Date/Time: Aug 23 11:00:00

Location: CSA auditorium [Room No. 104], ground floor

Abstract:
We look at a problem of decomposing a graph into several disjoint subgraphs with strict guarantees of internal density. This relates to the rich community structure observed in real-world networks, particularly social networks. We present a spectral condition for the existence of a decomposition of a graph into such pieces and present algorithms to recover such dense subgraphs efficiently. The results require a structural assumption on the graph that relates to triadic closure/transitivity commonly observed in such networks; it is a distribution-free statement. Moreover, we present a new, stronger metric for assessing the -goodness- of communities and show that this presents several advantages over traditional notions of density; our decomposition outputs subgraphs that satisfy this notion.


Microsoft teams link:

Link



We are grateful to the Kirani family for generously supporting the theory seminar series


Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar