Clustering Graphs using Motifs

Abstract:
In this talk I will present data-driven algorithms for dense subgraph discovery, and community detection respectively. The proposed algorithms leverage graph motifs to attack the large near-clique detection problem, and community detection respectively. In my talk, I will focus on triangles within graphs, but our techniques extend to other motifs as well. The intuition, that has been suggested but not formalized similarly in previous works, is that triangles are a better signature of community than edges. For both problems, we provide theoretical results, we design efficient algorithms, and then show the effectiveness of our methods to multiple applications in machine learning and graph mining.

[Joint work with Michael Mitzenmacher, and Jakub Pachocki]

Short Bio:
Dr. Charalampos Tsourakakis is an Assistant Professor at Boston University, and a Harvard Associate. He received his Ph.D. from the Algorithms, Combinatorics and Optimization (ACO) program at Carnegie Mellon University (CMU). He also holds a Master of Science from the Machine Learning Department at CMU. He did his undergraduate studies at the National Technical University of Athens (NTUA). He is the recipient of a best paper award in IEEE Data Mining, and has designed two graph mining libraries for tera-scale graphs. The former has been officially included in Windows Azure, while the latter was a research highlight of Microsoft Research. His main research interests lie in designing scalable algorithms and mining tools for large-scale datasets.