Graphs are ubiquitous data presentations that are usually used to model complex relations in a wide variety of applications, including biochemistry, neurobiology, ecology, social sciences, and information system. The recent explosion in the number of scale of these real-world structured data sets has created a need to efficiently process and analyze these massive graphs. Despite that graph algorithms are well studied over the past decades, most graph algorithms require to store the whole representations of graphs, i.e., adjacency matrices, in the memory and do an off-line computation. As a result it is difficult with these algorithms to handle massive graphs of more than 100 million nodes. Hence recent advance in studying graph algorithms is to design streaming and distributed algorithms. In this talk we discuss this line of research with our recent results on counting arbitrary subgraphs in massive graphs, and the load balancing problem in arbitrary networks.
Dr. He Sun received his PhD from Fudan University in 2010, and was a post-doc at Max Planck Institute for Informatics (MPII) from 2010 to 2012. Currently, he is a senior researcher at MPII, and leading the research group on Combinatorics, Computing, and Randomness. He has worked on a wide range of topics in theoretical computer science, including spectral graph theory, data streaming algorithms, distributed computing, and computational geometry.
1131 Kemper Hall