CS Colloquium Series @ UCY
Department of Computer Science - University of Cyprus
The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.
If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:
List
RSS
Directions
Colloquium Coordinator: Demetris Zeinalipour
Colloquium: Scalable Dense Subgraph Discovery, Dr. Charalampos E. Tsourakakis (Harvard University, USA), Tuesday, June 2, 2015, 11:00-12:00 EET.
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 |
Abstract:
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 [1]. 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 [2]. 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 [3]. 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.
[1] Charalampos E. Tsourakakis
The k-clique densest subgraph problem
24th International World Wide Web Conference (WWW 2015);
[2] 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);
[3] 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).
Short Bio:
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.
Multimedia File Available:
Multimedia File
Sponsor: The CS Colloquium Series is supported by a generous donation from  |