Finding large near-cliques in massive networks is a notoriously hard problem of great importance to many applications, including anomaly detection in security, community detection in social networks, and mining the Web graph. How can we exploit idiosyncrasies of real-world networks in order to solve this NP-hard problem efficiently?
Can we find dense subgraphs in graph streams with a single pass over the stream? Can we design near real time algorithms for time-evolving networks? In this talk I will answer these questions in the affirmative.
I will also present state-of-the-art exact and approximation algorithms for extraction of large near-cliques from large-scale networks, the k-clique densest subgraph problem, which run in a few seconds on a typical laptop. I will present graph mining applications, including anomaly detection in citation networks, planning a successful cocktail party, and engineering applications on Tera-scale networks. I will conclude my talk with some interesting research directions.
Charalampos Tsourakakis is an Assistant Professor at Boston University. He received his Ph.D. from the Algorithms, Combinatorics and Optimization (ACO) program at Carnegie Mellon University, and served as a Postdoctoral Fellow in Harvard University. He holds a Diploma in Electrical and Diploma Engineering from the National Technical University of Athens and a Master of Science from the Machine Learning Department at Carnegie Mellon University. Before joining Boston University, he worked as a researcher in the Google Brain team. He won a best paper award in IEEE Data Mining, has delivered three tutorials in the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, and has designed two graph mining libraries for large-scale graph mining, one of which has been officially included in Windows Azure. His research focuses on large-scale graph mining, and machine learning.
