The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:
Scalable Dense Subgraph Discovery
Speaker: Dr. Charalampos E. Tsourakakis
In this talk, we will focus on algorithm design for dense subgraph discovery in large networks. We shall discuss the k-clique densest subgraph problem, a recent generalization of the well-studied densest subgraph problem . We will present efficient exact and approximation algorithms, and experimental findings that illustrate its practical relevance with respect to detecting large near-cliques, namely subsets of vertices which are close to being cliques. Then, we will introduce the concept of densest subgraph sparsifiers, a randomized algorithm that allows scalable densest subgraph computations on multi-gigabyte (static) networks . We believe that our work is a significant advance in routines with rigorous theoretical guarantees for scalable extraction of large near-cliques from networks [1,2]. Furthermore, we will present state-of-the-art approximation algorithms for dense discovery in large-scale dynamic graphs . Our results achieve space, amortized time and query time efficiency, combining efficiency constraints from the streaming and dynamic algorithms' communities simultaneously. Finally, we will conclude with some open related problems.  Charalampos E. Tsourakakis The k-clique densest subgraph problem 24th International World Wide Web Conference (WWW 2015);  Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos E. Tsourakakis, Shen Chen Xu Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2015);  Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams 47th ACM Symposium on Theory of Computing (STOC 2015).
Dr. Charalampos Tsourakakis is currently a Postdoctoral Fellow in the School of Engineering and Applied Sciences (SEAS) at Harvard University. 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 in the School of Electrical and Computer Engineering (ECE) 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, and the latter was a research highlight of Microsoft Research. His research interests include algorithm design for large-scale datasets, data science and mathematical optimization.
Recorded Video available through
|Mailing List: https://listserv.cs.ucy.ac.cy/mailman/listinfo/cs-colloquium|
|Sponsor: The CS Colloquium Series is supported by a generous donation from