Dense subgraph discovery in large-scale networks

Finding dense subgraphs in massive networks is a major problem with numerous applications, including anomaly detection in security, community detection in social networks, and mining the Web graph. How can we exploit properties of real-world networks in order to find large near-cliques? Can we find dense subgraphs in graph streams with a single pass over the stream?  Can we design real-time algorithms  for time-evolving networks? How can we find subgraphs in uncertain graphs that induce large weight in expectation and are associated with low risk? In this talk I will present state-of-the-art answers to these questions, and I will conclude with various open research directions.