Dense subgraphs are a useful tool to understand the structure of graphs, and they often indicate interesting patterns or anomalies. In this talk, I will discuss several algorithms that I have developed for analyzing and identifying dense subgraphs in real-world graphs, which are large and dynamic (i.e., edges can be added or deleted). Specifically, I will introduce streaming algorithms for estimating the clustering coefficients (i.e., tendencies of nodes to form dense subgraphs) and approximation algorithms for identifying anomalous dense subgraphs in terabyte-scale data. I will also show applications of the algorithms in several domains, including online social networks, e-commerce, and network security.
Mr. Kijung Shin is a Ph.D. student in the Computer Science Department at Carnegie Mellon University. He received B.S. in Computer Science and Engineering from Seoul National University in 2015 and M.S. in Computer Science from Carnegie Mellon University in 2017. His research interests include graph mining and scalable machine learning.