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:
mail List rss RSS Directions 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
Affiliation: Harvard University, USA
Category: Colloquium
Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Tuesday, June 2, 2015
Time: 11:00-12:00 EET
Host: Marios Dikaiakos (mdd-AT-cs.ucy.ac.cy)
URL: https://www.cs.ucy.ac.cy/colloquium/index.php?speaker=cs.ucy.2015.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 [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

  Web: https://www.cs.ucy.ac.cy/colloquium/
  Mailing List: https://listserv.cs.ucy.ac.cy/mailman/listinfo/cs-colloquium
  RSS: https://www.cs.ucy.ac.cy/colloquium/rss.xml
  Calendar: https://www.cs.ucy.ac.cy/colloquium/schedule/cs.ucy.2015.tsourakakis.ics

Sponsor: The CS Colloquium Series is supported by a generous donation from Microsoft