Visiting Speaker
A. Erdem Sariyuce
University at Buffalo
Hierarchical Dense Subgraph Discovery: Models, Algorithms, Applications
Monday
Mar 18, 2019
Watch video
11:00 am
177 Huntington Ave
11th floor

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.

About the speaker
A. Erdem Sariyuce 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 and B.S. in Computer Engineering from Middle East Technical University. He conducts research on large-scale graph mining with a particular focus on practical algorithms to explore and process real-world networks. In the past, Erdem received the Best Paper Runner-up Award at the International World Wide Web Conference (WWW) in 2015.
Visiting Speaker
A. Erdem Sariyuce
University at Buffalo
Hierarchical Dense Subgraph Discovery: Models, Algorithms, Applications
Mon
Mar 18, 2019
11:00 am
177 Huntington Ave
11th floor
ADD to calendar

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.

about the speaker
A. Erdem Sariyuce 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 and B.S. in Computer Engineering from Middle East Technical University. He conducts research on large-scale graph mining with a particular focus on practical algorithms to explore and process real-world networks. In the past, Erdem received the Best Paper Runner-up Award at the International World Wide Web Conference (WWW) in 2015.