DSG Seminar Series • Hierarchical Dense Subgraph Discovery: Models, Algorithms, Applications

A. Erdem Sarıyüce, University at Buffalo

Abstract: Finding dense substructures in a network is a fundamental graph mining operation, with applications in bioinformatics, social networks, and visualization to name a few. Yet most standard formulations of this problem (like clique, quasi-clique, densest at-least-k subgraph) are NP-hard. Furthermore, the goal is rarely to find the “true optimum” but to identify many (if not all) dense substructures, understand their distribution in the graph, and ideally determine relationships among them. In this talk, I will talk about a framework that we designed to find dense regions of the graph with hierarchical relations. Our model can summarize the graph as a tree of subgraphs. With the right parameters, our framework generalizes two widely accepted dense subgraph models; k-core and k-truss decompositions. We present practical sequential and parallel local algorithms for our framework and empirically evaluate their behavior in a variety of real graphs. Furthermore, we adapt our framework for bipartite graphs which are used to model group relationships such as author-paper, word-document, and user-product data. We demonstrate how proposed algorithms can be utilized for the analysis of a citation network among physics papers and user-product network of the Amazon Kindle books. 

Bio: A. Erdem Sarıyüce is an Assistant Professor in Computer Science and Engineering at the University at Buffalo. Prior to that, he was the John von Neumann postdoctoral fellow at Sandia National Laboratories. Erdem received his Ph.D. in Computer Science from the Ohio State University. He conducts research on large-scale graph mining. In particular, he develops practical algorithms to explore and process the real-world networks. He received Best Paper Runner-up Award at the International World Wide Web Conference (WWW) in 2015. More details can be found at http://sariyuce.com.

Talk slides

Talk video